рекуррентное отношение для дерева

Question

предположим, что есть дерево с числом дочерних узлов, увеличивающимся с 2 до 4, затем 8 и т. Д. Как мы можем записать рекуррентное отношение для такого дерева.

Answer 1

• с использованием метода подстановки - T (n) = 2T (n / 2) + n = 2 [2T (n / 2 ^ 2) + n / 2] + n = 2 ^ 2T (n/ 2 ^ 2) + n + n = 2 ^ 2 [2T (n / 2 ^ 3) + n / 2 ^ 2] + n + n = 2 ^ 3T (n / 2 ^ 3) + n + n + n

  аналогичным образом подставляя k раз - мы получаем

  T (n) = 2 ^ k T (n / 2 ^ k) + nk рекурсия завершится, когда n / 2 ^ k = 1k = log n base 2.

  , таким образом, T (n) = 2 ^ log n (base2) + n (log n) = n + nlogn

  , таким образом, жесткая граница для повторения вышеотношение будет = n log N (основание log 2)

Answer 2

Взгляните на эту ссылку .

T(n) = 2 T(n/2) + O(n)         [the O(n) is for Combine]
T(1) = O(1)