algorithm - 完全 K 叉树

Question

我在 n 个节点上有一个完整的 19 元树。我标记所有具有以下属性的节点，即它们的所有非根祖先都是最年长或最小的 child (包括根)。我必须为标记节点的数量给出一个渐近界限。

我注意到

• 第一层有一个标记节点(根(
• 第二名:19
• 第三:2 * 19
• 第四:2^2 * 19
• 第五:2^3 * 19
• ...
• 第 k : 2^(k-2) * 19

我的方法是先求出最后一层标记节点的个数，然后递归求出少一层的完整19元上标记节点的个数。

但这并不完全有效。我走的路对吗？

Answer 1

使用递归过于复杂。你有

1 + sum{i = 2 .. k} 19 ( 2 ^ (k-2) ) = 1 + 19 sum{j = 0 .. k-2} 2^j

求和只是将 2 的幂的范围相加。很明显 sum{j=0..n-1}2^j = 2^n-1。想想一个二进制数。任何 2 的幂都有一个 1 位。减去 1，得到 2 的所有低次幂之和!

所以使用这个恒等式，我们有

1 + 19 ( 2^(k-1) - 1 )

为了测试，我们可以尝试三层树，k=3，它产生 1 + 19 (4 - 1) = 1 + 19(3)。这与您显示为模式的系列相匹配。