求递归算法的时间复杂度:递归树
递归算法时间复杂度的一个递归方程:
在引入递归树之前可以考虑一个例子:
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)
2023-11-19 13:01:58
在引入递归树之前可以考虑一个例子:
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)
下一篇:树-二叉树的基本概念