算法分析与设计ss lecture1

计算思维的提计算思维的提2006年3月，周以真M.Wing，卡内基梅隆大学计算机系系主任)：“计算思维是运用计算机科学的基础概念进行问题求解、系统设计以及人类行为一系列思维活动。”本质是抽象和自动化••2007年美国科学基金会启动“大学计算教育振思维（ComputationalThinking）2计算思维与人才培计算思计算思维与人才培计算思维：数学思维与工程思维的互补与融抽象与实思维：认知、方法能力：做得技能：会编优化程方法确三种基本的思三种思维的共同特点用语言三种基本的思三种思维的共同特点用语言文字表达、有语法与语义规则、推理逻•4实验理论计算起物理数计算机科步导出数量关实验验定义提出定给出证自动化实现特预见新的现公理实现机械算法与计算思•算算法与计算思•算法课程是训练计算思维的重要课程；涉及到问题的抽象，建模，设计好的求解方法，复杂的控制•可计算性与计算复杂性性，抽象与逻辑证形式化、确定性、有•算法设计与分析：抽象建模、归约、正确性证、效率分析、5课程简课程名称课程简课程名称算法分析与设课号基本目的了解计算复杂性理论的基本概念及其应6课程主要内问题处理策计算复杂性理课程主要内问题处理策计算复杂性理NP算法分析方算法设计技基础知7教材主教材算法设计与分教材主教材算法设计与分析屈婉玲,田张立昂王捍贫，清华大学出版社，2011，2013重印.辅导教材算法设计与分析习题解答与张习指导，屈婉玲刘田昂王捍贫，清华大学出版社8参考Jon参考JonKleinberg,EvaTardos,AlgorithmDesign,Addison-Wesley,清华大学出版社影印版，2006.ThomasH.Cormen,CharlesE.Leiserson,RonaldL.Rivest,IntroductiontoAlgorithms(SecondEdtion),TheMITPress2009. 张立昂，可计算性与计算复杂性导引（第版），北京大学出版社，堵丁柱，葛可一，王洁，计算复杂性导论，高教出版5*.SanjeevArora,BoazBarak,ComputationalComplexity:AModernApproach,CambridgeUniversityPress，2009.9学习安学习安教学方式书面作成绩评定平时成绩期末笔试视频答视频答定期安排时白上传文PPT播视频教视频教室界引为什引为什么要学算几个例算法研究的内容和目算法分析方算法研究的重要几个例.例1：求解调度几个例.例1：求解调度问任务集S={12j项加工时间:tj,Z+j=1,2一个可行调度方案：1,2,n的排i1i2求：总等待时间最少的调度方案，即nkS的排列i1i2in使(nk}求解方贪心策略：加工时间短的先例2：投资问问题m元钱，投资给n例2：投资问问题m元钱，投资给n个项目，效益函fi(x)，表i个项投入x元钱的效益得总效益最大如何分配每个项目的钱数i个项目的钱maxfi(xiin令xi是nxii采用什么算法？效率怎样蛮力算法的代n1Stirling公式： )(1蛮力算法的代n1Stirling公式： )(1 nen非负整数<x1x2xn的个数估计1)!Ω((1)mn1(mCmmm!(n蛮力算法——穷举法代价太能否利用解之间的依赖关系找到更好的算法结论：需要算法设计技例Hanoi塔问ABCT(n)=2nT(n2T(例Hanoi塔问ABCT(n)=2nT(n2T(n1)1，T(11，解秒移个，6（亿次秒，.思考：是否存在更好的解法Reve难题：Hanoi塔变种，柱数增加，允许盘子相等其他变种：奇偶盘号分别放例排序算例排序算法的评已有的排序算法：考察元素比较次插入排序、冒泡排序：最坏和平均状况下都为)堆排序、二分归并排序：最坏和平均状况下都为…问那个排序算法效率最高是否可以找到更好的算法？排序问题的计算难度如何估计例5货郎问货郎问题有穷个城市的集合Cc1例5货郎问货郎问题有穷个城市的集合Cc1c2cm距d(ci,cj)=1i<j求12m的排列k1k2km使mmin{di)d , ,现状：至今没有找到有效的算法存在大量问题与它难度等问题：是否存在有效算法如何处理这类问题9563c3cc429Algorithm+DataAlgorithm+Data=好的算需要解决的问算法类问题复杂度的评问题类能够求解的边算法设计技算法分析方计算复杂性理理论上理论上的可计算可计算性理研究目确定什么问题是可计算的，即存在求解算合理的计算模核心论题：Church-Turing论如果一个函数在某个合理的计算模型上可计算，那么它Turing机上也是可计算可计算性是不依赖于计算模型的客观性理论上与现实上可计算 理论上与现实上可计算 算法至少具有指数时间：理论上可计算——难解多项式时多项式时间的算多项式时间的算不是多项式时间的算包含指数时间甚至更高阶的算多项式函数与指数函问题规n多项式函数与指数函问题规n.0011.017.912.735.7366世.059586.53855世2*108世1.3*1013世多项式函数与指数函1小时可解的问题实例的最大规多项式函数与指数函1小时可解的问题实例的最大规计算快100倍的计算快1000倍的计算n10010001031.64.64102.53.98N5+N5+N6+N6+10亿次/秒机器求解的问•快速排序算10亿次/秒机器求解的问•快速排序算法给10万个数据排序运算量约仅需1.7106/109=1.710-3秒•Dijkstra算法求解1万个顶点的图的单源最短路径问题运算量约为约需108/109=0.1秒•回溯法解100个顶点的图的最大团问题运算,=4.01015年,4千万亿年1分钟能解多大的问题1分钟60秒这台计算机可做用快速排序算法可给2109(即,20亿)个数据排序,用•题而用回溯法一天只能解41个顶点的图的最大团问两种选两种选问题的复杂度分问题的复杂度分P多项式时间可解的问存在着解不存在解的多项式时间的算的多项式时间的算实际上可计算的问多项式时间可解的问计算复计算复杂性类的谱计计算法与算法与计算复杂性理论进算概率算计算复杂参数复杂通信复杂算法研究的重要算法设计与分析技术在计算机科学与技术领域有着重要的算法研究的重要算法设计与分析技术在计算机科学与技术领域有着重要的应用背景算法设计分析与计算复杂性理论的研究是计算机科学技术的核心研究领域以算法1966-2005期间，Turing奖获奖50人，其中10计，计算复杂性理论的核心课题要的数学问题之是本世纪7个最第1基第1基础知1.1算法的基本概算算法的时间复杂算法的伪码表递推方程求1.1算法的基1.1算法的基本概问题：需要回答的一般性提问，通常含有若干参数，对参数的一组赋值就得到问题的一个实例.算法：是有限条指令的序列，这个指令序列确定了解决某个问题的一系列运算或操作.算法A解问题P：把问题的任何实例作为算法A的输入，A够在有限步停机，并输出该实例的正确的解算法的时间复杂度：针对问题指定基本运算，计数算法所做的基本运算次数最坏情况下的时间复杂度：算法求解输入规模为需要的最长时间平均情况下的时间复杂度：在指定输入的概率分布下，算法求解输入规模为的实例所需要的平均时间A检索问题的时间估检索问输入：非降顺检索问题的时间估检索问输入：非降顺序排列的数组L，元素数为数输出j.若x在L中，jx首次出现的序标；否j算法：顺序搜最坏情况下时间平均情况：假xL的概率为p，xL不同位置等概分布.实例S，实例IS的概率pI,算法对I的基本运算次数为A(n)A(n)inpn(1p)n(12算法的算法的伪码描赋值语句分支语句：if…then循环语句：while,for，repeat调用：直接写过程的名注释实例：求最大公实例：求最大公约算法1.1输入：非负整n，其中m与n不全为输出：m与n的最大公约whilem>0rnmodreturn实例：改进的顺序检实例：改进的顺序检算法1.2输入：数输出：若L[1..n]，其元素按照从小到大排列，L中，输x的位置下标j；否则输出whilejnandx>L[j]doifx<L[j]orj>nthenj0returnj1.3数学基函1.3数学基函数的渐近的定义1.1f和g是定义域为自然数N上的函数若存在正cn0使得对一nn0有0f(ncg(n成立,f(n)的渐近的上界g(n)，记作f(n)=若存在正cn0，使得对一nn00cg(n成立,则称f(n)的渐近的下界是g(n)，记f(n)(3若对于任意正c都存n0，使得nn00cg(n成立则记f(n)=函数的渐近的函数的渐近的界（续cg(n)<f(n)成立,则记作f(n)=(5f(nO(g(nf(n(g(n则记ff(n)=n2+n，0有关定定理1.1fg有关定定理1.1fg是定义域为自然数集合的函数fngn存在且等于某个常c0,那f(n)=(1)如nnfn)/gn)0，那f(n)=(2如f(n)/g(n，那nf(n)=证明定理1.1c/2,存在某n0，只要nn0，就有证明定理1.1c/2,存在某n0，只要nn0，就有f(n)cf(n)cc|cf(n)3c22对所有的nn0f(n)2cg(n).从而f(n)(c/2)g(n)，从而推出对所有的f(n定理h是定义域为自然数集合的定理h是定义域为自然数集合的函数定理1.2如如如f=O(g)且g=O(h)，那且g=(h)，那么和g=(h)，那定理假fg是定义域为自然数集合的函数，若对个其它的函h,我们f=O(h)g=O(h)，那f+g=例：函数的例 设f(n)=n23例：函数的例 设f(n)=n23n，证明f(n)证因1f(n)22根据定理1.1f(n)可以证明：多项式函数，幂函数的阶低于指数函nd=o(rn)，r>1，d>基本函数阶的高至少指数级：2n3n基本函数阶的高至少指数级：2n3nn多项式级：nn2nlogn对数多项式级nn3Θ(nloglognnn2n(logn)log,log(n!)loglogloglogn1/log对数函符号logn对数函符号lognlog2logkn(logn)k(lgnlogloglognlog(log性质logbno(nαalogb nlogblogknΘ(logα阶n1Stirling公2n )(1 n阶n1Stirling公2n )(1 nenn!=o(nn)，n!=log(n!)=log(n!)logknnlogn-1123451loge(nlnnnΩ(nlog阶乘（续n1 45阶乘（续n1 45nlog(n!)logklogxdxO(nlogk2例2：函数的按照阶从高到低对以下函数排序n1/lognn2n例2：函数的按照阶从高到低对以下函数排序n1/lognn2n(3/2)nnloglogn2logn(logn)lognnnloglogn,n3logloglog结果nnloglogn n2n(3/2)n(logn3 log(n!)Θ(nlognΘ(2lognlogloglog2loglogn1/log函数阶的渐近性例输入：nn为大函数阶的渐近性例输入：nn为大2的奇整数输出：true或者false1．sn2．forj2toifjthenreturn5．return不能写可以在O(1)时间完成，可以写nn取整函x：表示小于等于x的最大的整x：表示大于等于x的最小的整取整取整函x：表示小于等于x的最大的整x：表示大于等于x的最小的整取整函数具有下述性x1<xxx<x+nx+n,x+nx+n，其中n为整nn2nnannabab b 求和公基本求和公n(a1anna，{ak}为等差数k2k求和公基本求和公n(a1anna，{ak}为等差数k2ka(1qn11xn1nnaqx,,11kkkka(qk）1n1klnn估计和式上界的方放大法nkak估计和式上界的方放大法nkak假设存在常r<1，使k0ak+1/akr成kknkarkrak001求和实求例n1 k(kkkt2tt求和实求例n1 k(kkkt2ttkk(111k)解k(kkkkn1 n111k1kk1 kk求和实kktt(2tt2t求和实kktt(2tt2t2t1(2kkt2tt2ttkk(t1)2tt2tkkkt2t2t2tttk2k(2k1)(k1)2k实n例5估计 的上界kkk解由 ,akk3kk1a实n例5估计 的上界kkk解由 ,akk3kk1ak12得ak3k3kn1 12)k(2331k33k估计和式渐近的n1的渐近的界kkn1kxn估计和式渐近的n1的渐近的界kkn1kxn1kln(nnkn1k111kkxn11lnn递推方程递推方程的求设序列a0,a1,…,an,…,简记为{an},一个把an与某些个联系起来的等式叫做关于序列求解方法迭代直接迭代：插入排序最坏情况下时间分迭代模型：递归尝试法：快速排序平均情况下的时间分析定理：递归算法的分的递推方例6：Hanoi算法例6：Hanoi算法将A的n个盘子按要求移到ifn=1thenmoveA,C)将A的1个盘子移到elseT(n)=2T(n1)+1，T(1)==2n1T(1)+2n2+2n=2n1+2n1=2n直接迭代：插入排算法1.4直接迭代：插入排算法1.41.forj2to//A为n个数的数 行3到行7把A[j]插入A[1..j1]之whilei>0andx<A[i]W(n)W(n1)nW(1)二分归并排算法1.5二分归并排算法1.51.if归并排序数组thenq(p+r)/2W(n)2W(n/2)nW(1)归并过将排序数组A[p..q]与A[q+1,r]合归并过将排序数组A[p..q]与A[q+1,r]合算法1.xqp+1,xy分别为两个子数组的元素数2.将A[p..q]复制到i1,j1,whileixandjydoifB[i]C[j]12.//B已经是空数//C已经是空数i>xthen将C[j..y]复制到13.else将B[i..x]复制到换元迭W(n)2换元迭W(n)2W(2k1)2k2[2W(2k2)2k11]2k22W(2k2)2k22kW(n)2W(n/2)nnW(1)22[2W(2k3)2k21]22k(2k12k2kW(1)kk2k2knlognn...2使用迭代法，对解可以通过数学归纳法验差消化简后迭T(i)i2T(n)n快速排差消化简后迭T(i)i2T(n)n快速排序平均时间分nnT(n2T(icn2c为某个常i2T(i) inT(n)(n1)T(n1)Lc[ 1...1]T(1)T(n)T(n1) nn1nnn321...1Θ(logn)，T(n)Θ(nlog13n迭代模型：递归nnnnn22n-nnnnn迭代模型：递归nnnnn22n-nnnnn4444n111111n-W(n)2W(n/2)n1,n2kW(n)n1n2...nkn(2k1)nlognnW(1)W(n/4)W(n/4)W(n/4)生成过递归树的应用实nnn3n3n9n99递归树的应用实nnn3n3n9n9991n(2/3)k=1(3/2)k=n层数尝试法：快速排T(n)2T(i)尝试法：快速排T(n)2T(i)T(n)=C为常函数，左边n2C(n1)i右边n2C2Cn(2T(n)=cn,左边2nci右边i2c(1n1)(n1)n2cnc尝试法：快速排2(3T(n)=cn2,左边T(n) T(i)nni尝试法：快速排2(3T(n)=cn2,左边T(n) T(i)nni2n1=右2i322cO(n)]O(n)2[ 3(4T(n)=cnlogn,左边ilogi右边nilognO(nlogn)][ 4lncnlognO(n)O(log以积分作为求和的近nnxxlogxdxln2ln22nxx1lnx4ln22以积分作为求和的近nnxxlogxdxln2ln22nxx1lnx4ln22411lnnln2ln24ln24ilogi2nlogn O(nlogn)4ln22主定主定主定理：设则有以下结果若f(nO(nlogba),0,那么T(nΘ(nlogba若f(nΘ(nlogba),那么T(nΘ(nlogba若f(nΩ(nlogba),0,且对于某个常c1和充分大的n有af(n/b)cf(n)，那T(n)=(f(n))迭设nT(n)aT )fba[aT(n)f(n)]f迭设nT(n)aT )fba[aT(n)f(n)]f(n)a2T(n)af(n)fbbakT(n)akn)...af(n)bffbkkbjknajfjcT(1)log)b11bf(n)O(nlogba情况knafT(n)logj)bbjlogbnf(n)O(nlogba情况knafT(n)logj)bbjlogbnO(aj)logbalogcb1bjlogba(blogba)O(nlogbalog)cb1jlogb(b)jlogaO(nlogb cb1jblogblogaO(nlogba)cb1O(nlogban)O(nlogba cb1f(n)Θ(nlogba情况kn fT(n) j)bbjlogbf(n)Θ(nlogba情况kn fT(n) j)bbjlogb nΘ(aj )logbacb1bjjaΘ(n a)cb1aj aclogb1alog情况Ω(n af(n))bkn fT(n) 情况Ω(n af(n))bkn fT(n) j)bbjlogbnc(af )cf cfb1bjcl