算法设计讲——.pptVIP

关于O、Ω 、Θ记号举例 关于O、Ω 、Θ记号举例 关于O、Ω 、Θ记号举例 关于O、Ω 、Θ记号举例 练习： 关于o记号举例 算法复杂度分析的常用方法 算法复杂度分析的常用方法 算法复杂度分析的常用方法 算法复杂度分析的常用方法 循环次数的统计 循环次数的统计 循环次数的统计 循环次数的统计 循环次数的统计 循环次数的统计 循环次数的统计 * 定义2.1 设算法的执行时间为T(n)，如果存在T*(n)，使： 称T*(n)为算法的渐进时间复杂度。 在算法分析中用渐进时间复杂性来衡量一个算法的时间复杂性。 在百钱买百鸡问题中： (1)算法1的时间复杂性为T1*(n)，它的阶是n3 (2)算法2的时间复杂性为T2*(n)，它的阶是n2 表示时间复杂性的阶有： 表1：不同时间复杂性下不同输入规模的运行时间 时间复杂度 假定在计算机C1和C2上运行这些算法 （1）C2机的速度是C1机的10倍。 （2）这些算法在C1机上的运行时间为T，可处理的输入规模是n1 （3）在C2机上运行同样的时间T，可处理的规模为n2 表2：计算机速度提高，不同算法复杂性求解规模的扩大 假定A1,A2,A3, …,A6是求解同一个问题的6个算法，它们的时间复杂度分别为： 时间复杂度 前4种时间复杂性： 与输入规模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记号： 因此，如果存在 则： 即意味着：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))。 运行时间的下界，Ω记号： 因此，如果存在 则： 即意味着：f(n) = Ω(g(n)) 这个定义表明：f(n)的增长至少象g(n)的增长那样快。这时称Ω (g(n))是f(n)的下界。 举 例 运行时间的准确界，Θ记号： 在百钱买百鸡问题的算法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(