算法设计：第二讲――2013

定义2.1设算法的执行时间为T(n)，如果存在T*(n)，使：0)()()(lim*nTnTnTn•称T*(n)为算法的渐进时间复杂度。•在算法分析中用渐进时间复杂性来衡量一个算法的时间复杂性。在百钱买百鸡问题中：(1)算法1的时间复杂性为T1*(n)，它的阶是n3(2)算法2的时间复杂性为T2*(n)，它的阶是n2表示时间复杂性的阶有：nnnnnnn2,,,log,,log32表1：不同时间复杂性下不同输入规模的运行时间时间复杂度假定在计算机C1和C2上运行这些算法（1）C2机的速度是C1机的10倍。（2）这些算法在C1机上的运行时间为T，可处理的输入规模是n1（3）在C2机上运行同样的时间T，可处理的规模为n2表2：计算机速度提高，不同算法复杂性求解规模的扩大假定A1,A2,A3,…,A6是求解同一个问题的6个算法，它们的时间复杂度分别为：!,2,,,log,32nnnnnnn时间复杂度前4种时间复杂性：32,,log,nnnnn!,2nn与输入规模n的一个确定的幂同阶，计算机运算速度的提高，可以使阶梯规模以一个常数因子的倍数增加。通常把这类算法称为多项式时间算法。后2种时间复杂性：称为指数时间算法。时间复杂度运行时间的上界，O记号：在百钱买百鸡问题中：（1）算法1执行基本操作的步骤至多为C1*n3，当n的规模增大时，常数C1对运行时间的影响不大，则算法1的运行时间的上界写成：O(n3)（2）同理，算法2的的运行时间的上界写成：O(n2)运行时间的上界，O记号：在一般情况下，当输入规模大于或等于某个阈值n0时，算法运行时间的上界是某个正常数c的g(n)倍，就称算法的运行时间至多是O（g(n))。O记号的定义如下：定义：令N为自然数集合，R+为正实数集合。函数f：N→R+，函数g：N→R+，若存在自然数n0和正常数c，使得对所有的n≧n0，都有f(n)≦cg(n)，就称函数f(n)的阶至多是O(g(n))。运行时间的上界，O记号：因此，如果存在则：)(/)(limngnfn)()(limngnfn即意味着：f(n)=O(g(n))这个定义表明：f(n)的增长至多象g(n)的增长那样快。这时称O(g(n))是f(n)的上界。举例运行时间的下界，Ω记号：在百钱买百鸡问题中：（1）第11、12、13、14行，仅在条件成立时才执行，其执行次数未知。（2）假定条件都不成立，这些语句一次也没有执行，该算法的执行时间至少为：算法执行时间计算运行时间的下界，Ω记号：在一般情况下，当输入规模大于或等于某个阈值n0时，算法运行时间的下界是某个正常数C的g(n)倍，就称算法的运行时间至少是Ω(g(n))。Ω记号的定义如下：定义：令N为自然数集合，R+为正实数集合。函数f：N→R+，函数g：N→R+，若存在自然数n0和正常数c，使得对所有的n≧n0，都有f(n)≧cg(n)，就称函数f(n)的阶至少是Ω(g(n))。运行时间的下界，Ω记号：因此，如果存在则：)(/)(limngnfn即意味着：f(n)=Ω(g(n))这个定义表明：f(n)的增长至少象g(n)的增长那样快。这时称Ω(g(n))是f(n)的下界。举例0)()(limngnfn运行时间的准确界，Θ记号：在百钱买百鸡问题的算法2中：（1）运行时间的上界是13n2，下界是n2。（2）这表明不管输入规模如何变化，该算法的运行时间都介于n2和13n2之间。（3）这时，用记号Θ来表示这种情况，认为这个算法的运行时间是Θ(n2)。（4）Θ记号表明算法的运行时间有一个较准确的界。运行时间的准确界，Θ记号：在一般情况下，当输入规模大于或等于某个阈值n0时，算法运行时间以c1g(n)为其下界，以c2g(n)为其上界，其中（0≦c1≦c2）,就认为算法的运行时间是Θ(g(n))。Θ记号的定义如下：定义：令N为自然数集合，R+为正实数集合。函数f：N→R+，函数g：N→R+，若存在自然数n0和两个正常数0≦c1≦c2，使得对所有的n≧n0，都有c1g(n)≦f(n)≦c2g(n)，则函数f(n)的准确阶是Θ(g(n))。复杂性类型和o记号定义：令N为自然数集合，R+为正实数集合。函数f：N→R+，函数g：N→R+，若存在自然数n0和正常c，使得对所有的n≧n0，都有f(n)＜cg(n)，就称函数f(n)的阶是o(g(n))。复杂性类型和o记号因此，如果存在则：)(/)(limngnfn即意味着：f(n)=o(g(n))这个定义表明：随着趋于非常大，f(n)相对于g(n)变得不重要。0)()(limngnfn举例复杂性类型和o记号可以用偏序关系来表示f(n)=o(g(n))在算法分析中，经常遇到如下一些类型的复杂性，它们的复杂性关系为：)()(ngnf22!2loglogloglog124/3nnnnnnnnnnn证明：f(n)=Θ(g(n))关于O、Ω、Θ记号举例238)(2nnnf2)(nng线性函数：()52fnn()gnn平方函数：结论：令关于O、Ω、Θ记号举例0)(0111kkkkkaananananf则有：，且，因此有：)()(knOnf)()(knnf)()(knnf课后练习例4：指数函数：例5：对数函数：关于O、Ω、Θ记号举例225)(nnfnnng2)(2log)(nnfnnglog)(结论：在一般情况下，对任何正常数k，都有)log(lognnk例6：函数：关于O、Ω、Θ记号举例njjnf1log)(nnnglog)(1：证明下面的关系成立(1)(2)(3)(4)练习：)log(!lognnn)(302nini)(6522nnn)2(21nn证明：f(n)=o(g(n））例1：f(n)=2ng(n)=n!关于o记号举例结论：f(n)=o(g(n)),当且仅当f(n)=O(g(n)),而g(n)≠O(f(n))算法所需要的资源（时间、空间）数量，经常以和的形式或以递归公式的形式表示。需要用到一些基本的数学工具，以便在算法分析和处理时，对这些和数或递归函数进行处理。算法复杂度分析的常用方法常用的函数及公式整数函数对数函数排列组合二项式定理算法复杂度分析的常用方法级数求和算术级数平方和几何级数调合级数算法复杂度分析的常用方法非递归函数的分析循环次数的统计基本操作频率统计计算步的统计算法复杂度分析的常用方法算法的运行时间经常与算法中的循环次数成正比，而循环次数又经常和算法的输入规模存在着某种联系。算法的时间复杂度是由嵌套层数最多的循环语句中，最内层语句的频度决定。如果算法的执行时间不是随着问题规模n的增加而增长，则该算法的时间复杂度为O（1）例如：for(i=1;i=10000;i++)循环次数的统计循环次数直接依赖规模nx=0;for(k=1;k=n;k++)x=x+1;for(i=1;i=n;i++)for(j=1;j=n;j++)y=y+1;循环次数的统计最内层语句执行次数：n2时间复杂度：O(n2)举例：计算多项式循环次数的统计0111)(axaxaxaxPnnnn用Horner法则把上式改写成：011))(()(axaxaxaxPnn算法设计循环次数间接依赖规模nx=1;for(i=1;i=n;i++)for(j=1;j=i;j++)for(k=1;k=j;k++)x=x+1;循环次数的统计执行次数：[n(n+1)(2n+1)/6+n(n+1)/2]/2时间复杂度：O(n3)举例1：使用冒泡法，把数组中的n个元素由小到大进行排序算法设计循环次数的统计内部for循环的循环体执行次数呈一种递减的变化规律。举例2：选手的竞技淘汰比赛有n=2k位选手进行竞技淘汰比赛，最后决出冠军的选手。假定函数：intcomp(Typemem1,Typemem2)模拟两位选手的比赛，若mem1胜则返回1，否则返回0。并假定可以在常数时间c内完成函数comp的执行。算法设计循环次数的统计举例3：对n张牌进行n次洗牌，洗牌规则如下：在第k次洗牌时（k=1,…,n），对第i张牌（i=1,…,n/k）随机地产生一个小于n的正整数d，互换第i张牌和第d张牌的位置。算法设计循环次数的统计