T (n) = T (n / 2) + T (n / 4) + O (1), что такое T (n)?

Question

Как решить это повторение: T(n) = T(n/2) + T(n/4) + O(1)

Не похоже, что Мастер Метод поможет, поскольку это не в форме T(n) = aT(n/b) + f(n). И я застрял довольно долго.

Answer 1

Akra Bazzi гораздо более мощный метод, чем метод Master.

Так как термин «нерекурсивный» равен O (1), это равносильно решению уравнения

1/2^p + 1/4^p = 1

И ответ, который вы получите, будет T(n) = Theta(n^p)

Я полагаю, что решение вышеуказанного (квадратичного в 1/2^p) дает нам p = log_2 phi, где фи - золотое сечение.

Вычисления, которые дают нам T(n) = Theta(n^0.694...)