【牛客左神的算法课笔记】
若递归可以写成如下形式：
T
(
n
)
=
a
T
(
n
b
)
+
O
(
n
d
)
T(n) = aT(\frac{n}{b})+O(n^d)
T(n)=aT(bn)+O(nd)
则时间复杂度计算如下：
- if log b a > d \log_ba > d logba>d ，复杂度为 O ( N log b a ) O(N^{\log_ba}) O(Nlogba)
- if log b a = d \log_ba = d logba=d ，复杂度为 O ( N d ∗ l o g N ) O(N^{d*logN}) O(Nd∗logN)
- if log b a < d \log_ba < d logba<d ，复杂度为 O ( N d ) O(N^d) O(Nd)
其中，a表示初始迭代的子算法有几个，b表示初始将数组分成了几个部分，d表示递归完成后还要进行的复杂度。
举例，用递归求解一个数组的最大值，采用分治方法将数组均分为两部分左和右，分别计算两部分的最大值，其中最大的那个就是全数组的最大值。
代码如下：
# 递归分治求最大值 找到左边的最大值和右边的最大值，再比较
def getMax(alist,L,R):
if L==R:
return alist[L]
mid = int((L+R)/2)
maxLeft = getMax(alist,L,mid)
maxRight = getMax(alist,mid+1,R)
ans = max(maxLeft,maxRight)
return ans
alist = [3,2,1,6,8,4]
a = getMax(alist,0,len(alist)-1)
递归的时间复杂度可以写成
T
(
n
)
=
2
T
(
n
2
)
+
O
(
1
)
T(n)=2T(\frac{n}{2})+O(1)
T(n)=2T(2n)+O(1)
其中算法分成了左和右两个子算法，所以a=2；
数组被均分成了两部分，所以b=2；
递归完成后只做了比较运算，时间复杂度为O(1)，所以d=0
因此
log
b
a
>
d
\log_ba>d
logba>d，时间复杂度为
O
(
n
)
O(n)
O(n)