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

算法分析与计算复杂性理论第一页，共三十七页，2022年，8月28日2课程简介

课程名称

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

AnalysisofAlgorithmsandTheoryofComputationalComplexity

基本目的掌握组合算法设计的基本技术掌握算法分析的基本方法掌握计算复杂性理论的基本概念学习应用算法理论处理实际问题第二页，共三十七页，2022年，8月28日3课程内容顺序算法设计的基本技术

分治策略动态规划回溯算法贪心法概率算法顺序算法分析的基本方法

评价算法的标准

算法复杂性的估计问题复杂性的下界算法分析的实例计算复杂性理论

Turing机计算复杂性的概念

NP完全性理论及其应用

NP完全理论的拓广第三页，共三十七页，2022年，8月28日预计进度安排内容学时内容学时1前言19Turing机22数学基础210计算复杂性理论23分治策略411NP完全性理论24动态规划412Cook定理15回溯与分支估界413NP完全性证明56贪心法414NP完全理论应用27概率算法315NP完全理论的拓广28算法分析技术616小结1第四页，共三十七页，2022年，8月28日5教材与参考书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.第五页，共三十七页，2022年，8月28日学习安排成绩评定：小论文：结合研究工作，50%期末笔试：50%

第六页，共三十七页，2022年，8月28日7引言:理论上的可计算与现实上的可计算

算法研究的重要性理论上的可计算

——可计算性理论现实上的可计算

——计算复杂性理论

第七页，共三十七页，2022年，8月28日8投资问题问题：

m元钱，投资给n个项目，效益函数fi(x)，表示第i个项目投入x元钱的效益，i=1,2,…,n.如何分配每个项目的钱数使得总效益最大？采用什么算法？效率怎样？令xi是第i个项目的钱数第八页，共三十七页，2022年，8月28日9蛮力算法的代价Stirling公式：非负整数解<x1,x2,…,xn>的个数估计：蛮力算法——穷举法代价太大能否利用解之间的依赖关系找到更好的算法？结论：需要算法设计技术第九页，共三十七页，2022年，8月28日10

T(n)=2T(n1)+1，T(1)=1，ABC思考：是否存在更好的解法？Reve难题：Hanoi塔变种，柱数增加，允许盘子相等.

其他变种：奇偶盘号分别放置解得T(n)=2n

1

1秒移1个，64个盘子要多少时间？（5000亿年）Hanoi塔问题第十页，共三十七页，2022年，8月28日11其他问题搜索问题

输入：排好序的数组L，x

输出：x是否在L中？如果在输出它的下标排序问题输入：n个数输出：按递增顺序排好的n个数选择问题输入：n个数的集合S，正整数k（1kn)

输出：S中第k小的数需要：现有的算法中哪个算法最好？是否存在更有效的算法？第十一页，共三十七页，2022年，8月28日12Algorithm+DataStructure=Programming好的算法提高求解问题的效率节省存储空间需要解决的问题问题寻找求解算法算法设计技术算法算法的评价算法分析技术算法类问题复杂度的评价问题复杂性分析问题类能够求解的边界计算复杂性理论

第十二页，共三十七页，2022年，8月28日13算法研究的重要性算法设计与分析技术在计算机科学与技术领域有着重要的应用背景算法设计分析与计算复杂性理论的研究是计算机科学技术的核心研究领域1966-2005期间，Turing奖获奖50人，其中10人以算法设计，7人以计算理论、自动机和复杂性研究领域的杰出贡献获奖计算复杂性理论的核心课题“P=NP?”是本世纪7个最重要的数学问题之一通过算法设计与分析课程的训练对提高学生的素质和分析问题解决问题的能力有着重要的作用第十三页，共三十七页，2022年，8月28日14理论上的可计算：可计算性理论研究目标确定什么问题是可计算的，即存在求解算法合理的计算模型已有的：递归函数、Turing机、演算、Post系统等条件：计算一个函数只要有限条指令每条指令可以由模型中的有限个计算步骤完成指令执行的过程是确定的核心论题：Church-Turing论题如果一个函数在某个合理的计算模型上可计算，那么它在Turing机上也是可计算的可计算性是不依赖于计算模型的客观性质第十四页，共三十七页，2022年，8月28日15算法至少具有指数时间：理论上可计算——难解的多项式时间的算法：现实上可计算——多项式时间可解的对数多项式时间的算法：高度并行可解的理论上可计算

理论上不可计算现实可计算高度并行可计算理论上与现实上的可计算性第十五页，共三十七页，2022年，8月28日16计算复杂性理论内容算法复杂度——算法所使用的时间、空间的估计问题复杂度——估计问题的难度术语和概念问题算法算法的时间复杂度函数的阶多项式时间的算法与指数时间的算法问题的复杂度分析第十六页，共三十七页，2022年，8月28日17例1

货郎担问题问题：有穷个城市的集合C={c1,c2,…,cm},

正整数d(ci,cj)=d(cj,ci),1

i<j

m.

解：使得k1,k2,…,km是1,2…,m的置换且满足

问题问题：需要回答的一般性提问，通常含有若干参数问题描述所包含的内容：对问题参数的一般性描述，解满足的条件问题的实例：对问题的参数的一组赋值

第十七页，共三十七页，2022年，8月28日1853c1c4c3c210969实例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)=3第十八页，共三十七页，2022年，8月28日19算法非形式定义有限条指令的集合指令集确定了解决某个问题的运算或操作的序列输入个数大于等于0

输出个数大于0形式定义对所有的有效输入停机的Turing机算法A解问题P

把问题P的任何实例作为算法A的输入，A能够在有限步停机，并输出该实例的正确的解第十九页，共三十七页，2022年，8月28日20算法的描述：伪码保持程序的主要结构类C,Pascal赋值语句：分支语句：if…then…[else…]循环语句：while,for，repeat..until转向语句：goto调用注释：//…允许使用自然语言常忽略数据结构、模块、异常处理等细节常忽略变量说明第二十页，共三十七页，2022年，8月28日21伪码的例子：插入排序算法INSERTION-SORT(A)1.forj

2tolength[A]2.dokeyA[j]//将A[j]插入排好序的序列A[1..j–1]3.ij–14. whilei>0andA[i]>key5.doA[i+1]A[i]6.ii–17.A[i+1]key

第二十一页，共三十七页，2022年，8月28日22算法的时间复杂度最坏情况下的时间复杂度

算法求解输入规模为n的实例所需要的最长时间W(n)平均情况下的时间复杂度算法求解输入规模为n的实例所需要的平均时间A(n)复杂度表示针对问题选择基本运算将基本运算次数表示为输入规模的函数第二十二页，共三十七页，2022年，8月28日23实例搜索问题输入：非降顺序排列的数组L，元素数为n；数x输出：j.若x在L中，j是x首次出现的序标；否则j

＝0算法顺序搜索假设

x在L中的概率为p

x在L中不同位置是等概分布的，则第二十三页，共三十七页，2022年，8月28日24函数渐近的界设f和g是定义域为自然数集N上的函数

(1)f(n)=O(g(n))

若存在正数c和n0使得对一切nn0有0f(n)cg(n)(2)f(n)=(g(n))

若存在正数c和n0使得对一切nn0有0cg(n)f(n)(3)f(n)=o(g(n))

对所有正数c<1存在n0使得对一切nn0有0f(n)<cg(n)(4)f(n)=(g(n)).

对所有正数c<1存在n0使得对一切nn0有0cg(n)<f(n)(5)f(n)=(g(n))f(n)=O(g(n))且f(n)=(g(n))(6)O(1)表示常数函数第二十四页，共三十七页，2022年，8月28日25函数渐近的界的基本性质定理1.1

设f和g是定义域为自然数集N上的函数.(1)如果存在，并且等于某个常数c>0，那么

f(n)=(g(n)).(2)如果，那么

f(n)=o(g(n)).(3)如果,那么

f(n)=(g(n)).第二十五页，共三十七页，2022年，8月28日证明(只证明第一种情况)(1)根据极限定义，对于给定的正数=c/2,存在某个n0，只要nn0，就有对所有的nn0，f(n)2cg(n).从而推出f(n)=O(g(n))

对所有的nn0，f(n)(c/2)g(n)，从而推出f(n)=(g(n)),于是

f(n)=(g(n))第二十六页，共三十七页，2022年，8月28日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).函数渐近的界的基本性质第二十七页，共三十七页，2022年，8月28日28基本函数类阶的高低

至少指数级：2n,3n,n!,…

多项式级：n,n2,nlogn,n1/2,…

对数多项式级：logn,log2n,…

第二十八页，共三十七页，2022年，8月28日例题29例1

设，证明f(n)=

Θ(n2).根据定理1.1有f(n)=

Θ(n2).

第二十九页，共三十七页，2022年，8月28日30例题例2

PrimalityTest(n)（素数检测）输入：n,n为大于2的奇整数输出：true或者false1．s

2．forj2tos3．ifj整除n

4．thenreturnfalse5．returntrue假设计算可以在O(1)时间完成，可以写O(),不能写()，因为所需的测试次数小于等于之第三十页，共三十七页，2022年，8月28日多项式时间的算法31多项式时间的算法

时间复杂度函数为O(p(n))的算法，其中p(n)是n的多项式不是多项式时间的算法

不存在多项式p(n)使得该算法的时间复杂度为O(p(n))包含指数时间甚至更高阶的算法第三十一页，共三十七页，2022年，8月28日多项式函数与指数函数时间复杂度函数问题规模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－3