Рекуррентное соотношение T (n) = T (n^(1/2)) + T (nn^(1/2)) + n

Question

Мы с моим другом нашли эту проблему, и мы не можем понять, как ее решить , Его нетривиальный и стандартный метод подстановки на самом деле не работает (или мы не можем его правильно применять). Это должно быть быстрым с помощью опорных точек в ранге.

Вот повторение:

Т (п) = Т (п^(1/2)) + T (пп^(1/2)) + п

Любая помощь будет намного оценили. Благодаря!

Answer 1

Сначала успокойтесь:

Т (п) = Т (пп^(1/2)) + п, число итераций равно п^(1/2), в каждой итерации вы будете иметь nk sqrt (n) временная сложность, поэтому общая временная сложность составляет: ∑ nk sqrt (n) для 0 < = k < = sqrt (n), которая равна n^(3/2).

Теперь решить собственную проблему:

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

снова рассчитать количество шагов до прибытия к нулю или 1: первая часть `T (п^(1/2)) занимает O (журнал журнал п) , а вторая часть занимает O (sqrt (n)) раз до достижения нуля или 1 (см. мой answer к соответствующему вопросу). Таким образом, вторая часть доминирует над первой частью. Также в каждом итерационном времени сложность второй части вызывает sqrt (n) дополнительный элемент, который не влияет на сложность первого частичного времени (n-sqrt (n)), поэтому ваша общая продолжительность выполнения - n * sqrt (n).