Вопрос по algorithm, big-theta, math, recurrence – Решить повторение: T (n) = T (n ^ (1/2)) + Θ (lg lg n) [закрыто]

Вот как это решить, используя математику. Я буду использоватьlnln(n) вместоO(lnln(n)), Это в основном для уменьшения длины формул, и вы можете сделать то же самое с big-O. Так:

Который означает, что:

,

Теперь, чтобы преобразовать это большое суммирование, что

Целыйlnln(n) сумма может быть преобразована как:

И наша единственная проблема - найти какую-то связь междуn а такжеk, который может быть легко получен из последнихT(...) срок.

---

Для этого нам нужно найти разумное обязательное условие на последний срок. Это можно сделать, попробовав пару целых чисел, таких как0, 1, 2, С2 у тебя есть:

---

Подставляя k в наше предыдущее уравнение, вы увидите, что самый большой член равен:

и, следовательно, сложность:

P.S. вы можете увидеть решение аналогичного повторенияВот

Один трюк, который может быть полезен, состоит в том, чтобы преобразовать n во что-то другое, например, скажем, 2^k, Если мы сделаем это, вы можете переписать вышеуказанное как

T(2^k) = T(2^k/2) + Θ(log log 2^k)

= T(2^k) = T(2^k/2) + Θ(log k)

Теперь это похоже на повторение, которое мы могли бы реально решить, так как мы можем расширить это как

T(2^k) = T(2^k/2) + log k = T(2^k/4) + log (k/2) + log k

Если мы расширим это раз, мы получим

T(2ⁱ) = T(2^k/2i) + log k + log (k/2) + log (k/4) + ... + log (k/2ⁱ)

Это повторение заканчивается, когда 2^k/2i & # X2264; 2 (скажем, в этом случае мы достигаем базового случая), который происходит, когда

2^k/2i = 2

k / 2ⁱ = 1

k = 2ⁱ

i = lg k

Другими словами, если мы можем написать n = 2^kтогда чистый результат будет

T(n) = lg k + lg (k/2) + log (k/4) + log(k/8) + ... 1

lg k + (lg k) - 1 + (lg k) - 2 + (lg k) - 3 + ... + (lg k) - lg k

= Θ((lg k)²)

И так как мы знаем, что п = 2^k, это означает, что k = & # x398; (log n), поэтому подставляя это в, получаем, что T (n) = & # x398; ((log log n)²).

Основным трюком здесь было переписать как 2^k, Остальное - стандартная техника.

Так имеет ли это смысл? Что ж, если подумать, log log n - это, помимо прочего, количество бит, необходимое для записи log n. На каждой итерации вы берете квадратный корень из числа, что вдвое уменьшает число бит в его представлении. Это уменьшает количество битов, необходимых для записи количества битов, в единицу. Следовательно, первая итерация будет записывать в журнал log n битов, вторая (log log n) - 1, третья (log log n) - 2 и т. Д. В целом это суммирование равно & # x398; ((log log n)²), что соответствует интуиции.

Надеюсь это поможет!