利用递归树进行算法复杂度分析
Recursion Tree
在使用分治法( Divide and Conquer ) 来求解问题的过程中不可避免会用到递归( Recursion ),这给算法的复杂度分析带来了麻烦。但是幸运的是,递归树这种方法总能有用;不幸的是,它将会用到我们一个又爱又恨的符号,也就是 “点点点” ( … )
下面将会使用归并排序 ( Merge Sort ) 说明这种方法。
Merge Sort
主函数代码如下:
def merge_sort(nums):
n = len(nums)
if n < 2:
return
else:
nums_left = merge_sort(nums[0 : n / 2])
nums_right = merge_sort(nums[n / 2 : n])
merge(nums_left, nums_right) #O(n)
Merge Sort 复杂度分析
-
设原问题的复杂度为 T(n)
-
Merge 左右两个顺序序列复杂度为 O(n)
则:
递归树
建立递归树
我们设完成所有任务所需要的总步骤为 T(n) = 2 * T(n / 2) + cn:
显然,我们把最后一次 Merge 数据的步骤数设为 cn.
根据上述递推式建立递归树:
表示我们需要的总步骤为整个树的节点之和,即 T(n) = cn + 2 * T(n / 2)
而: T(n / 2) = (cn / 2) + 2 * T(n / 4),所以我们继续补全递归树:
按照这个规则,最后到达最底部,整棵递归树完成:
分析递归树
观察整个递归树,发现以下信息:
- 这颗递归树叶节点就是全部待排序的数字,为 n,最底层计算量为 O(n)。
- 递归树的高度为 log(n)
- 每层的计算量均为 cn
结论
可以计算 T(n) = log(n) * cn + O(n)
因为 cn = O(n)
因此:
所以 Merge Sort 复杂度为 O(nlogn)
同样的,如果递归式为 T(n) = 4T(n / 2) + O(n) 我们也可以利用递归树分析出 (式子中的相等指渐进意义下):
因此,该算法复杂度为 O(n^2)
Newest Posts