如何计算递归函数的上界时间复杂度（`“大O”）？

Question

假设我有一个递归函数T，我想计算这个函数的上限定时器复杂度。

T（1）= 3

T（N）= 3T（N/3）+ 3

我怎样才能找到的上界T（n）的时间复杂度的？

Answer 1

使用master theorem的情况其中a = 3，b = 3，c = 0。

我强烈建议对算法的MIT讲座。您可以在lecture 2

中了解更多关于主定理的知识

Answer 2

假设中，n = 3-1K-

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）