Повторение T (n) = T (n ^ (1/2)) + 1

Question

Я смотрел на это повторение и хотел проверить, правильно ли я подходил.

T(n) = T(n^(1/2)) + 1
= T(n^(1/4)) + 1 + 1
= T(n^(1/8)) + 1 + 1 + 1
...
= 1 + 1 + 1 + ... + 1 (a total of rad n times)
= n^(1/2)

Таким образом, ответ пришел бы к тета-оценке n ^ (1/2)

Answer 1

Вот как вы можете найти ответ без каких-либо подсказок, просто используя математику.

Начните развертывание рекурсии: .

Рекурсия будетв какой-то момент остановитесь, поэтому мы должны найти разумную точку остановки.Пытаясь 0, 1, 2, вы можете видеть, что 2 выглядит хорошо, потому что вы можете легко решить уравнение: .

Решив его, вы получите .

Таким образом, рекурсия будет продолжаться log(log(n)) раз, и это сложность вашего времени.

PS было решено немного более трудное повторение здесь.

Answer 2

подсказка: предположим, что n = 2 ^{2 m} или m = log ₂ log ₂ n,и вы знаете, 2 ^{2 м-1} * 2 ^{2 м-1} = 2 ^{2 м} поэтому, если вы определите S (m) = T (n), ваш S будет:

S (м) = S (м-1) +1 → S (м)= Θ (m) → S (m) = T (n) = Θ (log ₂ log ₂ n)

расширить его для общегоcase.

В рекурсии типа T (n) = T (n / 2) + 1 в каждой итерации мы уменьшаем высоту дерева до половины.Это приводит к Θ (logn).В этом случае, однако, мы делим входное число на степень два (не на два), так что получается Θ (log log n).