Отношение рекурсивного вызова внутри другого - PullRequest
Новая
       11

Отношение рекурсивного вызова внутри другого

1 голос
/ 02 июня 2019

Я пытаюсь проанализировать стоимость этого кода: 

static int funct1(int x) {
     if (x<=1) return x;
     return funct1(funct1(x/2)) + 1;
}

Как я могу разрешить отношение повторения T(n)=T(T(n/2))+1?

1 Ответ

0 голосов
/ 02 июня 2019

Ваш анализ неверен.T(n) = T(f(n/2)) + T(n/2) + 1 (Вы пропустили T(n/2), но программа должна сначала вычислить T(n/2), а затем запустить T(f(n/2))).и это не T(T(n/2)).

Теперь попробуйте рассмотреть f(n) как значение функции funct1.Предположим, n = 2^k, f(2^k) = f(f(2^{k-1})) + 1 = f(f(2^{k-2}) + 1) + 1 = ... = f(f(f(...f(1) + 1..)+1)+1) + 1.f(1) = 1, f(2) = 2, f(3) = 2, f(4) = 3, f(8) = f(f(4)) + 1 = f(3) + 1 = 3, f(16) = f(f(8)) + 1 = f(3) + 1 = 3 и f(32) = f(f(16)) + 1 = f(3) + 1 = 3.Как видите, он повторяется для всех значений 2^k и f(2^k) = 3.

Следовательно, T(n) = T(3) + T(n/2) + 1 = O(log n).

...