Как рассчитать скорость роста этой функции: T (n) = 2T (n ^ (1/2)) + 2 (n ^ (1/2))

Question

Мне нужно рассчитать темп роста этой функции для моей домашней работы:

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

Другими словами:

T(n) = 2T( sqrt(n) ) + 2( sqrt(n) )

Может помочь изменение переменных (что-то вроде n = 2^m)

Я нашел ответ log(n)*log(log(n)), но я знаю, что это неверно.

Answer 1

n = 2^m действительно правильная замена переменных для использования. Определить функцию S(m):

S(m) = T(n) = T(2^m)

T(sqrt(n)) = T(2^[m/2]) = S(m/2)

S(m) = 2S(m/2) + 2^[m/2+1]

Расширение:

S(m) =  4*S(m/4)  + 2*2^[m/4+1]  + 2^[m/2+1]
     =  8*S(m/8)  + 4*2^[m/8+1]  + 2^[m/4+2] + 2^[m/2+1]
     = 16*S(m/16) + 8*2^[m/16+1] + 2^[m/8+3] + 2^[m/4+2] + 2^[m/2+1]
     = ...

2^[m/2] будет доминировать над всеми другими терминами, поэтому:

S(m) = O(2^[m/2])

*********************
*                   *
* T(n) = O(sqrt(n)) *
*                   *
*********************

Вышеизложенное также можно получить с помощью Основной теоремы (Случай 3).