Как решить повторение T (n) = 4T (sqrt (n)) + sqrt (n)?

Question

Рекурсия:

T(n) = 4T(sqrt(n)) + sqrt(n)

Я не совсем уверен, могу ли я использовать основную теорему, чтобы решить эту проблему, заменив часть рекурсии.

Моя идея заключалась бы в том, чтобы сказать

S(n) = T(2^n) = 4T(2^(n/2)) + 2^(n/2) = 4S(n/2) + 2^(n/2)

С основной теоремой я бы сделал вывод

S(n) = O(2^n) -> T(n) = O(n)

Но я не уверен, верна ли такая замена.

Надеюсь, вы можете помочь мне с этим.

Answer 1

Хмм, правая граница равна Θ (√n), поскольку √n ≤ n / 100 для n ≥ 10 ⁴ , а основная теорема решает T '(n) = 4T' (n / 100) + √n как Θ (√n), и T (n) = O (T '(n)). Соответствующая нижняя граница Ω (√n) очевидна.

Часть, где ваш аргумент не является точным, заключается в записи S ​​(n) = O (2 ⁿ ), что верно поскольку 2 ^{n / 2} = O (2 ⁿ ), но основная теорема дает вам лучшую оценку S (n) = Θ (2 ^{n / 2} ). Это важно, потому что это разница между записью T (n) = S (2 ^{lg (n)} ) = Θ (2 ^{lg (n) / 2} ) = Θ (√n) по сравнению с тем, что вы написали: T (n) = S (2 ^{lg (n)} ) = O (2 ^{lg (n)} ) = O (n).

(В Stack Overflow таких вопросов много, но они больше подходят для math.SE .)