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

3

Начал изучать алгоритмы. Я понимаю, как найти тета-нотацию из «регулярного повторения»; лайкT(n) = Tf(n) + g(n), Но я потерян с этимповторение: проблема 1-2e:

T(n) = T(√n) + Θ(lg lg n)

Как выбрать метод для поиска тета? И что это за повторение? Я просто не совсем понимаю, что такое нотация внутри рекуррентности.

Ух ты, какой взрыв из прошлого! Это общий вопрос информатики (измерение тета-нотации для алгоритмов), куда его нужно переместить? Это не относится к математике, поскольку это не вопрос математики. О, и я вижу похожие вопросы в прямом эфире на StackOverflow -stackoverflow.com/questions/3255/…. Ruslan Osipov
Да, извините за это. Парень задал похожий вопрос низкого качества. Его вопрос был закрыт как не по теме. В отместку он процитировал твой вопрос, и ты увлекся им. jww
Stack Overflow - сайт для вопросов программирования и разработки. Этот вопрос кажется не по теме, потому что он не касается программирования или разработки. УвидетьWhat topics can I ask about here в справочном центре. возможноMathematics Stack Exchange было бы лучше спросить. jww

Ваш Ответ

2   ответа
2

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

enter image description here

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

enter image description here,

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

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

enter image description here

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


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


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

enter image description here

и, следовательно, сложность:enter image description here

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

Круто !!!! какое решение (Y)
6

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

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

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

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

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

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

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

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

2k/2i = 2

k / 2i = 1

k = 2i

i = lg k

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

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)

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

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

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

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

Я понял, что до этого (LG K) - 1 + (LG K) - 2 + ... + (LG K) - (LG K), = (LG K) + (LG K) + ..... + (LG K) - (1 + 2 + 3 + 4 + ....) = (LG K) + (LG K) + ..... + (LG K) - м (м + 1) / 2 Как вы можете связать m = log k? (Вот)
из LG K + (LG K) - 1 + (LG K) - 2 + (LG K) - 3 + ... + (LG K) - LG K Как вы получили & # x398; ((LG K) 2 )
@AkhilNadhPC Обратите внимание, что (lg k) - 1 + (lg k) - 2 + ... + (lg k) - (lg k), записанное в обратном порядке, равно 0 + 1 + 2 + ... + (lg k) - 2 + (LG K) - 1 + LG K.
Это следует из суммы1 + 2 + 3 + ... + n = n(n+1)/2, подключив n = LG K.
Извините, я все еще не понял это правильно. Можете ли вы обеспечить пошаговое сокращение от lg k + (lg k) - 1 + (lg k) - 2 + (lg k) - 3 + ... + (lg k) - lg k pls? Да, я знаю это суммирование. Но как вы можете уменьшить это все же? Пожалуйста, сделайте это ясно

Похожие вопросы