Chapter-1 算法引论

南京理工大学算法设计与分析AlgorithmDesignandAnalysis孙廷凯[e-mail]南京理工大学课程内容(32学时)•常用的算法设计策略(包括分治策略、动态规划、贪心策略、回溯法、随机算法等)•算法复杂度分析方法(计算迭代次数、使用递归方程、频度分析等)南京理工大学课程要求•掌握常用的算法设计策略、算法复杂度分析方法•授课方式：讲授•考核方式：南京理工大学教材•《算法设计技巧与分析》，M.H.Alsuwaiyel著,电子工业出版社，吴伟昶等译，2004南京理工大学相关参考文献•AlgorithmDesignTechniquesandAnalysis,M.H.Alsuwaiyel.(影印本).电子工业出版社.2003•算法导论(第2版)，ThomasH.Cormen等著，潘金贵等译，机械工业出版社，2006.•计算机算法设计与分析(第3版),王晓东,电子工业出版社,2007.•算法设计与分析，王红梅编著，清华大学出版社，2006.南京理工大学1算法引论•历史背景•算法复杂度与渐近分析方法•如何估计算法的复杂度•算法复杂度分析的意义南京理工大学历史背景•阶段1：二十世纪30年代，能否使用一个有效的过程来求解一个问题(相当于现在算法的概念)一直是人们所关注的。当时的焦点是将问题进行分类：可解或是不可解。关注问题是否可以求解的领域称为可计算理论(computabilitytheoryortheoryofcomputation)。出现了一系列的计算模型，例如：calculusofChurch、PostmachinesofPost、TuringmachinesofTuring、RAMmodelofcomputation。•阶段2：随着数字计算机的出现，人们越来越关注于那些可求解的问题。一开始，人们满足于能够在一定的时间内解决一个特定的问题，而不去关注所需要的资源。慢慢地，人们需要考虑在有限资源的条件下高效地解决问题。这就导致了计算复杂度(computationalcomplexity)这一新学科的诞生。在这个领域，主要是研究解决可求解问题时所需要的资源，主要是时间和空间复杂性。有时候，其他的资源也需要考虑，例如，通信代价、需要使用的处理器的个数(使用并行计算模型)等等。南京理工大学引例：搜索问题•给定已经排好序(不妨假设为非降序)的n个元素A[1…n],现在要判定一个给定的元素x是否在此数组中出现。–方法1：顺序搜索–方法2：二分搜索南京理工大学二分搜索算法输入：非降序排列的数组A[1…n]和元素x输出：如果x=A[j],1jn,则输出j,否则输出0.1.low←1;high←n;j←02.while(lowhigh)and(j=0)3.mid←(low+high)/24.ifx=A[mid]thenj←mid5.elseifxA[mid]thenhigh←mid-16.elselow←mid+17.endwhile8.returnj南京理工大学分析•最好情形：比较1次•最坏情形：比较logn+1次–每次循环都要抛弃一些元素，例如第二次循环时，剩余元素为A[1…mid-1]或A[mid+1…n]，不妨设为A[mid+1…n]，则剩余的元素个数是n/2–第j次while循环时，剩余元素的个数是n/2j-1–或者找到x，或者程序在子序列长度达到1时终止搜索,此时n/2j-1=11n/2j-122j-1n2jlognjlogn+1j=logn+1南京理工大学算法及其性质•算法是对问题求解过程的准确描述，由有限条指令组成，这些指令能在有限时间内执行完毕并产生确定性的输出。•算法需满足的4个性质：–输入：零个或多个外部量作为输入。–输出：至少产生一个量作为输出,它(们)与输入量之间存在某种特定的联系。–确定性：组成算法的每条指令都是清晰、无歧义的。–有限性：每条指令的执行次数有限，执行每条指令的时间也有限。•程序与算法的区别：–程序是算法用某种程序设计语言的具体实现。–程序可以不满足算法的有限性性质。南京理工大学算法的复杂度•复杂度：算法运行时需要耗费计算机资源的量，可以分为时间复杂度和空间复杂度。•算法复杂度依赖于三个方面：待求解问题的规模、算法的输入和算法本身。•用n,I,A分别表示问题的规模、算法的输入和算法本身，用表示C复杂度，则有：C=F(n,I,A)。如果将时间复杂度和空间复杂度分开，则有T=T(n,I,A)和S=S(n,I,A)。通常，我们让A隐藏在复杂度函数名中，所以有T=T(n,I)和S=S(n,I)。•由于时间复杂度和空间复杂度概念类似，计量方法类似，且空间复杂度分析相对简单，因此本课程主要讨论算法的时间复杂度。南京理工大学T=T(n,I)的具体化•假设计算机提供k种元运算，分别记为O1,O2,…,Ok。所谓元运算指的是这样一类运算：不管使用什么样的算法和输入数据，该运算的上阶是一个常数时间(关于阶，参见后文描述)。例如，算术运算、比较、逻辑、赋值等。•元运算Oi每执行一次需要的时间为ti。•对于给定的算法A，已经知道用到的元运算Oi的执行次数为ei,i=1,...,k。很显然ei是n和I的函数，即ei=ei(n,I)。•至此，就有：1(,)(,)kiiiTnItenI南京理工大学分析•T(n,I)给出的是在问题规模为n，输入为I时的时间复杂度。但是我们不可能，也没必要对每种可能的输入都去求其时间复杂度。通常可以考虑3种情形下的时间复杂度：最坏情形、最好情形以及平均情形。**max11()max(,)(,)(,)nkkiiiiIDiiTntenItenITnI''min11()min(,)(,)(,)nkkiiiiIDiiTntenItenITnI1()()(,)()(,)nNkavgiiIDIDiTnPITnIPItenI实践表明：可操作性最强、最有实际价值的是算法最坏情形下的时间复杂度。南京理工大学使用算法的绝对运行时间来度量其时间复杂度？－NO•一个编程实现了的算法的具体运行时间，不仅仅和算法本身相关，还和很多其他因素密切相关：机器性能、编程语言、编译器、编程技巧等等。•在分析一个算法的运行时间时，通常将该算法和其他算法在同一问题、甚至是不同的问题上进行比较，因而运行时间只能是相对的，而不是绝对的。•希望算法的描述不仅独立于机器，并且可以以任何语言来加以描述，包括自然语言。•希望使用度量算法运行时间的准则不依赖于技术的进步。•不仅仅关注小规模输入下的，而且还关注在大规模输入下的情形。南京理工大学渐近分析(AsymptoticAnalysis)•对于T(n)，当n单调递增并趋于∞时，T(n)也是单调增加并趋于∞。为此,如果存在一个T*(n)，使得当n→∞时有(T(n)−T*(n))/T(n)→0,就称T*(n)是T(n)当n→∞的渐近性态，或称T*(n)是给定算法在n→∞时的渐近复杂度。•显然,T*(n)不是唯一的。我们可以尽可能的选择简单的T*(n)，然后使用T*(n)来替代T(n)作为n→∞的复杂度度量。渐近复杂度分析只要关心T*(n)的阶就可以了(在n充分大时)，不必关心其中的常数因子。南京理工大学4种阶：O,Ω,Θ,和o•假设：f(n)和g(n)是定义在正数集上的正函数。(此假设的实际意义?)•定义1(O)：如果存在正的常数C和自然数n0，使得当n≥n0时，有f(n)≤C·g(n)，则称函数f(n)在n充分大时有上有界，且g(n)是它的一个上界，记做f(n)=O(g(n))，并称f(n)的阶不高于g(n)的阶。南京理工大学例子•例：f(n)＝n2，g(n)＝n3。因为：存在n0＝1，C=1，当n≥n0时，有n2≤Cn3,所以：n2=O(n3)•例：f(n)＝n2，g(n)＝n2。因为：存在n0＝1，C=1,n≥n0时，有n2≤Cn2,所以：n2=O(n2)•例：f(n)＝n2+nlog(n)，g(n)＝n2。同样有n2+nlog(n)=O(n2)•例：f(n)＝an2+nlog(n)，g(n)＝n2。同样有an2+nlog(n)=O(n2)•例：f(n)＝an2+nlog(n)+c，g(n)＝n2。同样有an2+nlog(n)+c=O(n2)南京理工大学小结•在进行阶的运算时，常系数、低的阶以及常数项可以忽略。•根据O的定义，得到的是在问题规模充分大时，算法复杂度的一个上界。上界的阶越低则评估越有价值。•运算规则–O(f)+O(g)=O(max(f,g));–O(f)·O(g)=O(f·g);–O(C·f(n))=O(f(n));–f=O(f);南京理工大学Ω•定义2(Ω)：如果存在正的常数C和自然数n0，使得当n≥n0时，有f(n)≥C·g(n)，则称函数f(n)在n充分大时有下有界，且g(n)是它的一个下界，记做f(n)=Ω(g(n))，并称f(n)的阶不低于g(n)的阶。•下界的阶越高，则评估精度越高，也就越有价值。南京理工大学Θ和o•定义3(Θ)：f(n)=Θ(g(n))，当且仅当f(n)=O(g(n))，且f(n)=Ω(g(n))，称f(n)和g(n)是同阶。•定义4(o)：对于任意给定的ε0，存在正整数n0，使得当n≥n0时，有f(n)/g(n)≤ε，则称函数f(n)在n充分大时的阶比g(n)低，记为f(n)=o(g(n))。南京理工大学小结•进行算法的时间复杂度分析，就是求其T(n)，并用O、Ω或是Θ以尽可能简单的形式进行表示。•理想情况下，希望能够使用Θ表示算法的时间复杂性。退而求其次，可以使用O或是Ω。•使用O时，希望估计的上界的阶越小越好。•使用Ω时，希望估计的下界的阶越大越好。南京理工大学算法耗费时间随问题规模的变化Algorithm12345Timefunction(ms)33n46nlgn13n23.4n32nInputsize(n)Solutiontime100.00033sec.0.0015sec.0.0013sec.0.0034sec.0.001sec.1000.0033sec.0.03sec.0.13sec.3.4sec.41016yr.1,0000.033sec.0.45sec.13sec.0.94hr.10,0000.33sec.6.1sec.22min.39days100,0003.3sec.1.3min.1.5days108yr.TimeallowedMaximumsolvableinputsize(approx.)1second30,0002,00028067201minute1,800,00082,0002,20026026南京理工大学阶运算的几个实例)(nno!n()nno=(1)!(1)(2)1110nnnnnnnnnnnnnnnn!n=解：因为所以(2)log!(log)nnn解:a.因为log!lognnn有log!(log)nnOn/211log!loglog()/2log()22nnjjnnnjn/2log()/2nnn=b.又因为则有命题成立)log()2/log2/(!lognnnnnn南京理工大学11(log)ninnni(3)221111()1nniinnnOni解:因为(不准确)112111111lnnnniidxniixa.11111ln(1)nnidxnixb.所以11ln(1)1lnninni换底公式1log(1)1log1loglogninneie11(log)nini所以亦即x112nx112n+111(log)ninnni南京理工大学()(())()(())fNOgNfNogN()(())()(())fNogNfNOgN(4)()(())()(())fNogNgNfN