Неприятное уравнение повторения: T(n) = 2*T(ceil((sqrt(n)))+1

Question

Недавно я столкнулся с проблемой повторения:

T (n) = 2 * T (ceil ((sqrt (n))) + 1

Т (1)=1;

Я не могу видеть, как эта функция завершается вообще, когда я рисую свое дерево повторений. Общая форма узла в дереве (n^1/2i) становится 1 только тогда, когда 1/2ⁱ становится 0. Это означает, что я должен стремиться к бесконечности.

Answer 1

Вы правы, что если sqrt является потолком квадратного корня, то вы никогда не достигнете 1, многократно применяя квадратные корни. Я собираюсь предположить, что вы намеревались использовать слово, что означает, что вы действительно в конечном итоге нажмете 1, когда повторение раскручивается.

В этом случае ваше повторение будет более правильным

T (1) = 1

T (n) = 2T (⌊√n⌋) + 1

Стандартный метод решения повторений с использованием квадратных корней - это замена. Давайте определим новое значение k такое, что n = 2^k. Обратите внимание, что √n = (2^k)^1/2 = 2^{k / 2}. Другими словами, получение квадратного корня из n эквивалентно уменьшению вдвое значения k. Благодаря этому мы можем преобразовать вышеупомянутое повторение, которое включает в себя квадратные корни, в новое повторение, которое будет более точно соответствовать форме, используемой в основной теореме и других методах решения повторения. В частности, давайте определим S (k) = T (2^k). Тогда мы получаем повторение

S (0) = 1

S (k) = 2S (⌊k / 2⌋) + 1

Намного легче увидеть, как решить эту проблему. Распознав это повторение из другого места или используя основную теорему, мы получим, что S(k) = Θ(k). Теперь мы хотели решить для T (n), поэтому мы можем использовать тот факт, что S (k) = T (2^k) = T (n). Поскольку S (k) = Θ(k), теперь мы видим, что T(n) = Θ(k). Поскольку мы выбрали k такое, что 2^k = n, это означает, что k = lg n. Следовательно, T(n) = Θ(log n), поэтому рекуррентность получается равной Θ(log n).

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