北京大学屈婉玲算法设计与分析必威体育精装版课件02.pdf

下载文档 降价啦

372
0
约2.51万字
约 40页
2017-10-05 发布于湖北
举报
版权申诉
保障服务

北京大学屈婉玲算法设计与分析必威体育精装版课件02.pdf

1、本文档共40页，可阅读全部内容。
2、有哪些信誉好的足球投注网站（book118）网站文档一经付费（服务费），不意味着购买了该文档的版权，仅供个人/单位学习、研究之用，不得用于商业用途，未经授权，严禁复制、发行、汇编、翻译或者网络传播等，侵权必究。
3、本站所有内容均由合作方或网友上传，本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺！文档内容仅供研究参考，付费前请自行鉴别。如您付费，意味着您自己接受本站规则且自行承担风险，本站不退款、不进行额外附加服务；查看《如何避免下载的几个坑》。如果您已付费下载过本站文档，您可以点击这里二次下载。
4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等，请点击“版权申诉”（推荐），也可以打举报电话：400-050-0827(电话支持时间：9:00-18:30)。

北京大学屈婉玲算法设计与分析必威体育精装版课件02

第2章分治策略（Divide and Conquer ） 22.11 分治策略的基本思想分治策略的基本思想 2.1.1 两个熟悉的例子 22.11.22 分治算法的分治算法的一般性描述般性描述 2.2 分治算法的分析技术 2.3 改进分治算法的途径 2.3.1 通过代数变换减少子问题个数 2.3.2 利用预处理减少递归内部的计算量 2.42.4 典型实例典型实例 2.4.1 快速排序算法 2.4.2 选择问题 2.4.3 n －1次多项式在全体2n次方根上的求值 1 2.1.1 两个熟悉的例子二分检索算法算法22.11 BinarySearchBinarySearch((TT, ll, rr, xx)) 输入：数组T，下标从 l 到 r ；数x 输出输出：jj //// 如果如果 xx 在在 TT 中中，jj 为下标为下标；否则为否则为00 1. l←1; r←n 22. whilhile ll≤≤ r ddo 3. m←⎣(l+r)/2⎦ 44. ifif TT[[m]]=x ththen retturn m //// x恰好等于中位元素恰好等于中位元素 5. else if T[m]m then r ← m−1 66. ellse ll←m+11 7. return 0 二分归并排序分归并排序 MergeSort （见第1章） 2 时间复杂度分析二分检索最坏情况下时间复杂度W(n)满足 ⎧⎧ ⎢ n ⎥ ⎪W (n) W (⎢ ) + 1 ⎨ ⎣ 2 ⎦⎥ ⎪⎪ W (1) 1 ⎩⎩ 可以解出可以解出W((n))=⎣⎣loggn⎦⎦ ＋1. 二分归并排序最坏情况下时间复杂度W(n)满足 ⎧ n ⎪W (n) 2W ( ) + n − 1 ⎨⎨ 22 ⎪⎪ W (1) 0 ⎩ 可以解出可以解出WW((nn))=nnloglognn−nn ＋＋1.1. 2.1.2 分治算法的一般性描述分治算法 Divide-and-Conquer(P) 1. if |P | ≤ c then S(P). 2. divide P into P , P , …, P . 1 2 k 3. for i = 1 to k 4. y = Divide-and-Conquer(P ) i i 5 ．Return Merge(y , y , …, y ) 1 2