递归树

求递归算法的时间复杂度:递归树

递归算法时间复杂度的一个递归方程:

递归树

在引入递归树之前可以考虑一个例子:

T(n) = 2T(n/2) + n2;

迭代2次可以得:

T(n) = n2 + 2(2T(n/4) + (n/2)2)

还可以继续迭代,将其完全展开可得:

T(n) = n2 + 2((n/2)2 + 2((n/22)2 + 2((n/23) 2 + 2((n/24)2 +…+2((n/2i)2 + 2T(n/2i+1)))…))))  ……(1)

上一篇:python数据结构树和二叉树简介


下一篇:树-二叉树的基本概念