求递归算法的时间复杂度
求递归算法的时间复杂度
使用公式法求解
这个方法针对形如：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);
需要注意的是，上面的公式并不包含所有的情况但是公式的不包含的情况，我们很少很少碰到，上面的公式适用范围很广泛的。
参考： 解递归方程时间复杂度.
这个方法针对形如：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);
需要注意的是，上面的公式并不包含所有的情况但是公式的不包含的情况，我们很少很少碰到，上面的公式适用范围很广泛的。
参考： 解递归方程时间复杂度.