算法基础：分治模式，归并排序ΘΘΘΘΘΘ知识小结
浏览数：20 /
时间：2015年06月08日
-
1.分治模式在每层递归时都有三个步骤：分解，解决，合并
- 2.归并排序算法完全遵循分治模式：
- 分解：分解待排序的n个元素的序列成各具n/2个元素的两个子序列
- 解决：使用归并排序递归的排序两个子序列
- 合并：合并两个已排序的子序列以产生已排序的答案
- 3.分析分治算法所需要的时间计算：
- 假设T(n)是规模为n的一个问题的运行时间，若问题足够小，如对某个常量c,n≦c,则直接求解需要常量时将，我们将其写作Θ(1).假设吧原问题分解成a个子问题，每个子问题的规模是原问题的1/b(对归并排序，a和b都为2，然而，我们将看到在许多分治算法中a≠b)为了求解一个规模为n/b的子问题，需要T(n/b)的时间，所以需要aT(n/b)的时间n来求解a个子问题，如果分解问题成子问题需要时间D(n),合并子问题的解成原问题的解需要时间C(n) 那么得到递归式：
- T(n)={Θ(1) 若,n≦c
- aT(n/b)+D(n)+C(n) 其他
- 4.归并排序算法
分析建立归并排序n个数的最坏情况运行时间T(n)的递归式，归并排序的一个元素需要常量时间，当有n>1
我们元素分解运行时间如下：
分解：分解步骤仅仅计算子数组的中间位置，需要常量时间，因此D(n)=Θ(1)
解决：我们递归的求解两个规模均为n/2的子问题，将贡献2T(n/2)的运行时间
合并：我们已经注意到在一个具有n个元素的字数组上过程MERGE需要Θ(n)的时间，所以C(n)=Θ(n)
当分析归并排序而把函数D(n) 与C(n)相加时，我们是在吧一个Θ(n)函数与另一个Θ(1)函数相加，相加的和是n的一个线性函数，即Θ(n)，把它与来自“解决”步骤的2T(n/2)相加，
将给出归并排序的最坏情况运行时间T(n)的递归式
Θ(1)
若n=1
T(n)={ 2T(n/2)+Θ(n)
若n>1
在第4章，我们将看到“主定理” ，可以用改定理来证明T(n)为Θ(nlgn),其中lgn代表㏒2n,因为对数函数比任何线性函数增长要慢，所以对足够大的输入，在最坏的情况下运行实际为Θ(nlgn)的归并排序将优于运行时间为Θ(n2)的插入排序
重写归并排序算法：
c 若n=1
T(n)={ 2T(n/2)+cn 若n>1
(常量c代表求解规模为1的问题所需的时间以及在分解步骤与合并步骤处理每个数组元素所需的时间)
lgn
+1 代表层，cn 为每层贡献总代价
cnlgn
+ cn=cn(lgn +1) 忽略低阶项和常量c便给出了期望的结果 Θ(nlgn)
郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。
