求递归算法的时间复杂度

使用公式法求解

这个方法针对形如：T(n) = aT(n/b) + f(n)的递归方程。其中a是子问题的个数。n/b是子问题的规模。f(n)是本轮操作的复杂度。可采用如下公式。
在这里插入图片描述
如：T(n）=4T(n/2)+O(n)，
a=4，b=2，d=1，
a>b^d,
T(n)=O(n^2);

需要注意的是，上面的公式并不包含所有的情况但是公式的不包含的情况，我们很少很少碰到，上面的公式适用范围很广泛的。

参考： 解递归方程时间复杂度.

版权声明：本文为匿名原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
本文链接：