算法分析与计算复杂性理论

1算法分析与计算复杂性理论2课程简介课程名称算法分析与计算复杂性理论AnalysisofAlgorithmsandTheoryofComputationalComplexity基本目的掌握组合算法设计的基本技术掌握算法分析的基本方法掌握计算复杂性理论的基本概念学习应用算法理论处理实际问题3课程内容顺序算法设计的基本技术分治策略动态规划回溯算法贪心法概率算法顺序算法分析的基本方法评价算法的标准算法复杂性的估计问题复杂性的下界算法分析的实例计算复杂性理论Turing机计算复杂性的概念NP完全性理论及其应用NP完全理论的拓广预计进度安排内容学时内容学时1前言19Turing机22数学基础210计算复杂性理论23分治策略411NP完全性理论24动态规划412Cook定理15回溯与分支估界413NP完全性证明56贪心法414NP完全理论应用27概率算法315NP完全理论的拓广28算法分析技术616小结15教材与参考书1.AlgorithmDesign,JonKleinberg,EvaTardos,Addison-Wesley,清华大学出版社影印版，2006.2.IntroductiontoAlgorithms（SecondEdtion）,ThomasH.Cormen,CharlesE.Leiserson,RonaldL.Rivest,TheMITPress2001.高教出版社影印版，2002.3.计算机和难解性:NP完全性理论导引,M.R.加里,D.S.约翰逊,张立昂等译，科学出版社,1987.*4.计算复杂性导论，堵丁柱，葛可一，王洁，高教出版社2002.*5.LimitstoParallelComputation:P-CompletenessTheory,RaymondGreenlaw,H.JamesHoover,WalterL.Ruzzo,OxfordUniversityPress,1995.学习安排成绩评定：小论文：结合研究工作，50%期末笔试：50%7引言:理论上的可计算与现实上的可计算算法研究的重要性理论上的可计算——可计算性理论现实上的可计算——计算复杂性理论8投资问题问题：m元钱，投资给n个项目，效益函数fi(x)，表示第i个项目投入x元钱的效益，i=1,2,…,n.如何分配每个项目的钱数使得总效益最大？N,,)(max11iniiniiixmxxf采用什么算法？效率怎样？令xi是第i个项目的钱数9蛮力算法的代价Stirling公式：非负整数解x1,x2,…,xn的个数估计：蛮力算法——穷举法代价太大能否利用解之间的依赖关系找到更好的算法？结论：需要算法设计技术))1(()!1(!)!1(11nmmnmΩnmnmC))1(1()(2!nΘennnn10T(n)=2T(n1)+1，T(1)=1，ABC思考：是否存在更好的解法？Reve难题：Hanoi塔变种，柱数增加，允许盘子相等.其他变种：奇偶盘号分别放置解得T(n)=2n11秒移1个，64个盘子要多少时间？（5000亿年）Hanoi塔问题11其他问题搜索问题输入：排好序的数组L，x输出：x是否在L中？如果在输出它的下标排序问题输入：n个数输出：按递增顺序排好的n个数选择问题输入：n个数的集合S，正整数k（1kn)输出：S中第k小的数需要：现有的算法中哪个算法最好？是否存在更有效的算法？12Algorithm+DataStructure=Programming好的算法提高求解问题的效率节省存储空间需要解决的问题问题寻找求解算法算法设计技术算法算法的评价算法分析技术算法类问题复杂度的评价问题复杂性分析问题类能够求解的边界计算复杂性理论13算法研究的重要性算法设计与分析技术在计算机科学与技术领域有着重要的应用背景算法设计分析与计算复杂性理论的研究是计算机科学技术的核心研究领域1966-2005期间，Turing奖获奖50人，其中10人以算法设计，7人以计算理论、自动机和复杂性研究领域的杰出贡献获奖计算复杂性理论的核心课题“P=NP?”是本世纪7个最重要的数学问题之一通过算法设计与分析课程的训练对提高学生的素质和分析问题解决问题的能力有着重要的作用14理论上的可计算：可计算性理论研究目标确定什么问题是可计算的，即存在求解算法合理的计算模型已有的：递归函数、Turing机、演算、Post系统等条件：计算一个函数只要有限条指令每条指令可以由模型中的有限个计算步骤完成指令执行的过程是确定的核心论题：Church-Turing论题如果一个函数在某个合理的计算模型上可计算，那么它在Turing机上也是可计算的可计算性是不依赖于计算模型的客观性质15算法至少具有指数时间：理论上可计算——难解的多项式时间的算法：现实上可计算——多项式时间可解的对数多项式时间的算法：高度并行可解的理论上可计算理论上不可计算现实可计算高度并行可计算理论上与现实上的可计算性16计算复杂性理论内容算法复杂度——算法所使用的时间、空间的估计问题复杂度——估计问题的难度术语和概念问题算法算法的时间复杂度函数的阶多项式时间的算法与指数时间的算法问题的复杂度分析17例1货郎担问题问题：有穷个城市的集合C={c1,c2,…,cm},正整数d(ci,cj)=d(cj,ci),1ijm.解：使得k1,k2,…,km是1,2…,m的置换且满足问题问题：需要回答的一般性提问，通常含有若干参数问题描述所包含的内容：对问题参数的一般性描述，解满足的条件问题的实例：对问题的参数的一组赋值mkccckk,,,2111)),(),(min(11mikkkkccdccdmii1853c1c4c3c210969实例C={c1,c2,c3,c4},d(c1,c2)=10,d(c1,c3)=5,d(c1,c4)=9d(c2,c3)=6,d(c2,c4)=9,d(c3,c4)=319算法非形式定义有限条指令的集合指令集确定了解决某个问题的运算或操作的序列输入个数大于等于0输出个数大于0形式定义对所有的有效输入停机的Turing机算法A解问题P把问题P的任何实例作为算法A的输入，A能够在有限步停机，并输出该实例的正确的解20算法的描述：伪码保持程序的主要结构类C,Pascal赋值语句：分支语句：if…then…[else…]循环语句：while,for，repeat..until转向语句：goto调用注释：//…允许使用自然语言常忽略数据结构、模块、异常处理等细节常忽略变量说明21伪码的例子：插入排序算法INSERTION-SORT(A)1.forj2tolength[A]2.dokeyA[j]//将A[j]插入排好序的序列A[1..j–1]3.ij–14.whilei0andA[i]key5.doA[i+1]A[i]6.ii–17.A[i+1]key22算法的时间复杂度最坏情况下的时间复杂度算法求解输入规模为n的实例所需要的最长时间W(n)平均情况下的时间复杂度算法求解输入规模为n的实例所需要的平均时间A(n)复杂度表示针对问题选择基本运算将基本运算次数表示为输入规模的函数23ninpnpnpnpinAnnW1)1(2)1()1()()(实例搜索问题输入：非降顺序排列的数组L，元素数为n；数x输出：j.若x在L中，j是x首次出现的序标；否则j＝0算法顺序搜索假设x在L中的概率为px在L中不同位置是等概分布的，则24函数渐近的界设f和g是定义域为自然数集N上的函数(1)f(n)=O(g(n))若存在正数c和n0使得对一切nn0有0f(n)cg(n)(2)f(n)=(g(n))若存在正数c和n0使得对一切nn0有0cg(n)f(n)(3)f(n)=o(g(n))对所有正数c1存在n0使得对一切nn0有0f(n)cg(n)(4)f(n)=(g(n)).对所有正数c1存在n0使得对一切nn0有0cg(n)f(n)(5)f(n)=(g(n))f(n)=O(g(n))且f(n)=(g(n))(6)O(1)表示常数函数25函数渐近的界的基本性质定理1.1设f和g是定义域为自然数集N上的函数.(1)如果存在，并且等于某个常数c0，那么f(n)=(g(n)).(2)如果，那么f(n)=o(g(n)).(3)如果,那么f(n)=(g(n)).0)()(limngnfn)()(limngnfn)()(limngnfn证明(只证明第一种情况)(1)根据极限定义，对于给定的正数=c/2,存在某个n0，只要nn0，就有对所有的nn0，f(n)2cg(n).从而推出f(n)=O(g(n))对所有的nn0，f(n)(c/2)g(n)，从而推出f(n)=(g(n)),于是f(n)=(g(n))ccngnfccngnfccngnf223)()(2)()(|)()(|27定理1.2设f,g,h是定义域为自然数集合的函数，(1)如果f=O(g)且g=O(h)，那么f=O(h).(2)如果f=(g)且g=(h)，那么f=(h).(3)如果f=(g)和g=(h)，那么f=(h).定理1.3假设f和g是定义域为自然数集合的函数，若对某个其它的函数h,我们有f=O(h)和g=O(h)，那么f+g=O(h).推论假设f和g是定义域为自然数集合的函数，且满足g=O(f)，那么f+g=(f).函数渐近的界的基本性质28基本函数类阶的高低至少指数级：2n,3n,n!,…多项式级：n,n2,nlogn,n1/2,…对数多项式级：logn,log2n,…)1(,loglog,log,log,log,2),log()!log(,),()(log,)2/3(,2,!,2log/12log3logloglog2ΘnnnnnnnnΘnnnΘnnnnnnnnnn例题29例1设，证明f(n)=Θ(n2).21321lim)(lim222nnnnnfnn根据定理1.1有f(n)=Θ(n2).nnnf321)(230例题例2PrimalityTest(n)（素数检测）输入：n,n为大于2的奇整数输出：true或者false1．s2．forj2tos3．ifj整除n4．thenreturnfalse5．returntrue假设计算可以在O(1)时间完成，可以写O(),不能写()，因为所需的测试次数小于等于之nnnn多项式时间的算法31多项式时间的算法时间复杂度函数为O(p(n))的算法，其中p(n)是n的多项式不是多项式时间的算法不存在多项式p(n)使得该算法的时间复杂度为O(p(n))包含指数时间甚至更高阶的算法多项式函数与指数函数时间复杂度函数问题规模102030405060n10－52*10－53*10－54*10－55*10－56*10－5n210－44*10－49*10－416*10－425*10－436*10－4n310－38*10－327*10－364*10－3125*10－3216*10－3n510－13.224.31.7分5.2分13.0分2n.001秒1.0秒17.9分12.7天35.7年366世纪3n.059秒58分6.5年3855世纪2*108世纪1.3*1013世纪33时间复杂度函数1小时可解的问题实例的最大规模计算机快100倍的计算机快1000倍的计算机nN1100N11000N1n2N210N231.6N2n3N34.64N310N3n5N42.5N43.98N42nN5N5+6.64N5+9.973nN6N6+4.19N6+6.29多项式函数与指数函数34问题的复杂度分析多项式时间可解的问题与难解的问题多项式时间可解的问题P存在着解P的多项式时间的算法难解的问题P不存在解P的多项式时间的算法