Полное дерево K-ary

Question

У меня есть полное 19-арное дерево на n узлах. Я отмечаю все узлы, у которых есть свойство, что все их некоренные предки являются либо самыми старыми, либо младшими (включая root). Я должен дать асимптотическую оценку числа отмеченных узлов.

я заметил, что

• первый уровень имеет один отмеченный узел (корень (
• второй: 19
• третий: 2 * 19
• четвертый: 2^2 * 19
• пятый: 2^3 * 19
• ...
• k-th: 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 + 19 (2^(k-1) - 1) 

Для теста мы можем попробовать дерево три уровня, к = 3, который производит 1 + 19 (4 - 1) = 1 + 19 (3) , Это соответствует серии, которую вы показали как шаблон.