Как решить нижеприведенное соотношение?

Question

рассмотрим уравнение повторения, приведенное в ссылке . Это не вписывается в форму, требуемую основной теоремой. я не хочу использовать метод подстановки, так как это отнимает много времени. Также я устал от изменения переменной (k = 2 ^ m), но не смог.

Как решить эту проблему с помощью дерева рекурсии или метода итерации ?

 T(n) =n^0.5  T(n^0.5) + n 

пс: ожидаемое решение: O (nlglgn)

Answer 1

Пусть U (n) = T (n) / n.

Тогда U (n) = n ^1/2 T (n ^1/2 ) / n + 1 и т. д.

U (n) = T (n ^1/2 ) / n ^1/2 + 1

U (n) = U (n ^1/2 ) + 1

Достаточно легко определить методом итерации, что U (n) <= log log n + U (2), потому что именно столько раз вы можете получить квадратный корень из n, прежде чем доберетесь до 2 (используя основание журнала 2). Затем вы можете доказать это индуктивно для всех n> 2, если требуется.

Следовательно, вы имеете T (n) = U (n) * n <= n (log log n + T (2) / 2),и это в O (n log log n) </p>