算法导论-庄连生

IntroductiontoAlgorithms算法导论算法导论主讲人庄连生主讲人庄连生Si2009USTCSpring2009,USTC教学内容yPart1基础知识¾算法基础¾算法分析基础排序和顺序统计学yPart2排序和顺序统计学¾归并排序、堆排序、快去排序数排序数排序桶排序¾计数排序、基数排序、桶排序yPart3数据结构¾红黑树、数据结构的扩张yPart4算法设计策略¾分治法、动态规划法、贪心法、回溯法、分枝限界法yPart5算法研究问题¾NP完全问题，有关数论的算法，……第二节算法入门教学目标：¾如何描述算法？¾如何描述算法？¾如何分析算法？算法策分法¾算法设计策略之——分治法两个例子：插入排序和归并排序插入排序问题:把一系列数据按非递增的顺序排列输入个输入数输入:n个输入数输出:输入系列的一个排序（重新排序），使得12,,,naaa'''12,,,naaa'''12naaa≤≤≤4插入排序y利用伪代码来描述算法y伪代码(Pseudocode)在很多方面和C、Pascal、Java等高级语言比较类似在很多方面和C、Pascal、Java等高级语言比较类似y与真实代码(realcode)的差异:y与真实代码(realcode)的差异:①对特定算法的描述更加的清晰与精确；②不需要考虑太多技术细节（数据抽象、模块、错误处理等）；③用伪代码可以体现算法本质；④永远不会过时；插入排序INSERTION-SORT(A)1for(j=2;j=length[A];j++)//loopheader2{key=A[j]{y[j]3//InsertA[j]intothesortedsequenceA[1..j-1]4i←j-15while(i0&&A[i]key)([]y)6{A[i+1]=A[i]7i=i-18}8}9A[i+1]=key10}//loopbodybelow6插入排序z书写上的“缩进”(缩排)表示程序中的分程序（程序块）结构；z循环结构(while,for,repeat)和条件结构(if,then,else)与Pascal,C语言类似；“//”“”来表释z“//”or“”来表示注释；z利用i←j←e来表示多重赋值，等价于j←e和i←j.z变量是局部于给定过程的。z数组元素的访问方式:A[i];A[1..j]=A[1],A[2],…,A[i]z符合数据一般组织成对象，由属性（attribute）或域(field)所组成；域的访问是由域名后跟方括号括住的对象名形式来表示。如length[A].参z参数采用按值传递方式；z布尔操作“and”和“or”具有短路能力:如“xand(or)y”:无论y的值如何，必须首先计算的值7须首先计算x的值。算法分析1.算法分析是指对一个算法所需要的资源进行预测；y资源：9内存9内存、9通信带宽、9计算机硬件9计算时间是最关心的（CPU、I/O等）y对于一个问题，分析几个候选的算法，选择一个最有效的算法找出不止一个候选算法通常都要去掉几个较差的算法。找出不止一个候选算法，通常都要去掉几个较差的算法。8算法分析2.计算模型：包括所描述所用的资源及其代价的模型。yRAM（Random-accessMachine,随机存储机）计算模型①指令一条接一条地执行，没有并发操作；②包含了真实计算机中常见的指令，每条指令所需要的时间为常量；③数据类型包括整数类型浮点实数类型③数据类型包括整数类型、浮点实数类型；④没有试图对当代计算机常见的存储器层次进行建模9算法分析3.运行时间y影响因素：输入规模，输入数据分布：y算法运行时间：在特定输入时，所执行的基本操作数（或步数）。算法运行时间：在特定输时，所执行的基本操作数（或步数）。满足如下一致性原则：①基本操作独立于机器；①基本操作独立于机器；②执行第i条指令的时间为常数时间Ci；10算法分析算法分析4.插入排序算法分析INSERTION-SORT(A)costtimes1for(j=2;j=length[A];j++)c1n2{key=A[j]c2n-123//InsertA[j]intothesortedsequenceA[1..j-1]0n-14i=j-1c4n-15while(i0&&A[i]key)c5while(i0&&A[i]key)c56{A[i+1]=A[i]c67i=i-1c78}9A[i+1]=keyc8n-110}1245678222()(1)(1)(1)(1)(1)nnnjjjjjjTncncncnctctctcn====+−+−++−+−+−∑∑∑}11jjj算法分析1245678222()(1)(1)(1)(1)(1)nnnjjjjjjTncncncnctctctcn=+−+−++−+−+−∑∑∑¾如果数组是排好序的，则会出现最好情况：222jjj===()(1)(1)(1)(1)T12458124582458()(1)(1)(1)(1)=()()Tncncncncncncccccnccccanb=+−+−+−+−++++−+++=+¾如果数组是逆序排序的，则会出现最差情况：此时必须将每个元素A[j]与整个已排序的子数组A[1..j-1]中的每一个元素进行比较对j=23n有t=j则有，对j=2,3,…,n,有tj=j.则有：2(1)1,2njnnj=+=−∑2(1)(1)2njnnj=−−=∑总时间：12452(1)()(1)(1)(1)2(1)(1)()()(1)nnTncncncncnnnncccnanbnc+=+−+−+−−−+++=++12678()()(1)22cccnanbnc+++−=++算法分析5.对于规模为n的任何输入，一般考察算法的最坏运行时间：①最坏情况运行时间是在任何输入情况下的一个上界；①最坏情况运行时间是在任何输入情况下的一个上界；②对于某些算法来说，最坏情况出现还是比较频繁的，如信息检索（信息经常不存在）；③大致上看，“平均情况”通常和最坏情况一样差。6.平均运行时间（期望运行时间）①概率分析技术(probabilisticanalysis)②随机化算法(didlih)②随机化算法(randomizedalgorithm)7增长的量级7.增长的量级①抽象简化。忽略每条语句的真实代价，用常量ci来表示；进一步忽略了抽象的代价；13了抽象的代价；②增长率或增长量级。只考虑公式中的最高项，并且忽略系数。算法设计y对于一个问题，可以有很多中解决方法。因此，算法设计策略也有很多策略也有很多。y排序问题：‹Bubblesort:bubbling‹Insertionsort:incrementalapproach(增量靠近)‹Mergesort:divide-andconquer(分而治之)‹Quicksort:location(元素定位)……y分治法最差的时间比插入排序法差得多14231Thedivide-and-conquerapproach（分治法）y核心思想：分而治之，各个击破；2.3.1Thedivideandconquerapproach（分治法）y递归结构:为了解决一个给定的问题，算法要一次或多次地递归调用其自身来解决相关的子问题。y分治策略：将原问题划分为n个规模较小而结构与原问题相似的子问题；递归地解决这些子问题，然后再合并其结果，就得到原问题的解。决再合并其果就到原y三个步骤：三个步骤：①分解（Divide）：将原问题分成成一系列子问题；②解决（Conquer）：递归地解各个子问题。若子问题足够小，则直接求解；q③合并（Combine）：将子问题的结果合并成原问题的解。152.3.1Thedivide-and-conquerapproach（分治法）y归并排序算法（Mergesortalgorithm）2.3.1Thedivideandconquerapproach（分治法）①分解：把n个元素分成各含n/2个元素的子序列；②解决：用归并排序算法对两个子序列递归地排序；③合并：合并两个已排序的子序列以得到排序结果。2381457623814576?在对子序列排序时，其长度为1时递归结束。2381457623458176单个元素被视为是已排好序的。24873516162.3.1Thedivide-and-conquerapproach（分治法）yMERGE(A,p,q,r)：归并排序算法的关键步骤，合并步骤中合并两个已经排序好的子序列。A是个数组数组中元素的下标且≤‹A是个数组，p,q,r数组中元素的下标，且p≤qr.‹该过程假设子数组A[p..q]和A[q+1..r]是有序的，并将它们合并成一个已排好序的子数组代替当前子数组A[p..r]。‹合并过程:?TheproceduretakestimeΘ(n)n=r-p+1。910JQK78910J17TheproceduretakestimeΘ(n),nr-p+1。2.3.1Thedivide-and-conquerapproach（分治法）MERGE(A,p,q,r)1n1←q-p+12n2←r-q3createarraysL[1..n1+1]andR[1..n2+1]4fori←1ton15dL[i]A[+i1]5doL[i]←A[p+i-1]6forj←1ton27doR[j]←A[q+j]8L[n+1]←∞//Toavoidhavingtocheckwhethereitherpileisemptyineach8L[n1+1]←∞//Toavoidhavingtocheckwhethereitherpileisemptyineach9R[n2+1]←∞//basicstep,asentinelcardisputonthebottomofeachpile.10i←111j←111j112fork←ptor13doifL[i]≤R[j]14thenA[k]←L[i]15i←i+116elseA[k]←R[j]17j←j+1Howdoesthesubroutinework?NextPage18g2.3.1Thedivide-and-conquerapproach（分治法）MERGE(A,p,q,r)1n1←q-p+12n2←r-q3createarraysL[1..n1+1]andR[1..n2+1]4fori←1ton15doL[i]←A[p+i-1]6forj←1ton27doR[j]←A[q+j]8L[+1]8L[n1+1]←∞9R[n2+1]←∞10i←111j←111j←112fork←ptor13doifL[i]≤R[j]14thenA[k]←L[i]14thenA[k]L[i]15i←i+116elseA[k]←R[j]17j←j+1192.3.1Thedivide-and-conquerapproach（分治法）MERGE(A,p,q,r)costtimes1n1←q-p+1c12n2←r-qc13createarraysL[1..n1+1]andR[1..n2+1]c14fori←1ton1cn1+1dr-p+1=n1+n2=n5doL[i]←A[p+i-1]cn16forj←1ton2cn2+17doR[j]←A[q+j]cn28L[n+1]←∞c1n1+n2n1=x=n18L[n1+1]←∞c19R[n2+1]←∞c110i←1c111j←1c1Θ(n1+n2)=Θ(n)11j←1c112fork←ptorcr-p+213doifL[i]≤R[j]cr-p+114thenA[k]←L[i]cx12[][]15i←i+1cx16elseA[k]←R[j]cr-p+1-x17j←j+1cr-p+1-x202.3.1Thedivide-and-conquerapproach（分治法）z将MERGE过程作为合并排序中的一个子过程来使用。下面过序程MERGE-SORT(A,p,r)对子数组A[p..r]进行排序.如果p≥r,则该子数组中至多只有一个元素，当然就是已排序的。分解步算个标A[]分成A