Как рассчитать верхнюю границу временной сложности («большой O») рекурсивной функции?

Предположим, у меня есть рекурсивная функция T, и я хочу вычислить верхнюю границу сложности таймера этой функции.

T(1) = 3

T(n) = 3T(n/3) + 3.

Как найти верхнюю границу временной сложности T(n)?


algorithm time-complexity asymptotic-complexity
person Billie    schedule 29.11.2013    source источник

Ответы (2)


arrow_upward
3
arrow_downward

Используйте основную теорему в случае formula где a=3, b=3, c=0.

solution

Я настоятельно рекомендую лекции Массачусетского технологического института по алгоритмам. Вы можете узнать больше о теореме Мастера в лекция 2

person pgpb.padilla    schedule 29.11.2013

arrow_upward
0
arrow_downward

предположим, что n = 3^k

F(0) = 3

F(k) = 3 * F(k-1) + 3

 = 3^2 * F(k-2) + 3^2 + 3

 = ...

 = 3^k * F(0) + 3^k + 3^(k-1) + ... + 3

 = 3^(k+1) + 3^k + ... + 3^2 + 3

 = [3^(k+2) - 3] / 2

T(n = 3^k) = F(k) = (9 * n - 3) / 2 = O(n)

person xbob.ym    schedule 29.11.2013