算法设计技巧与分析算法基本概念之算法复杂度概要.pptx

算法设计技巧与分析算法设计技巧与分析Algorithms Design Techniques and Analysis 南方医科大学医工学院南方医科大学医工学院 信息技术系信息技术系 第第1 1章章 算法分析基本概念算法分析基本概念Contento算法与程序算法与程序o简单的算法实例简单的算法实例o计算复杂性计算复杂性n时间复杂性时间复杂性n空间复杂性空间复杂性o分析计算方法分析计算方法o算法的复杂性分为算法的复杂性分为 o设计算法追求的目标设计算法追求的目标o选用算法的准则选用算法的准则 时间复杂性时间复杂性 需要的时间资源的量需要的时间资源的量空间复杂性空间复杂性 需要的空间资源的量需要的空间资源的量设计出复杂性尽可能低的算法设计出复杂性尽可能低的算法选择已有算法中复杂性最低者选择已有算法中复杂性最低者不是所有能计算的都有价值，不是所有有价值的都能被计算。不是所有能计算的都有价值，不是所有有价值的都能被计算。阿尔伯特阿尔伯特.爱因斯坦爱因斯坦Algorithm ComplexityTime Complexityo1 估计估计算法运行的时间范围。算法运行的时间范围。o2 估算估算随着输入的增长，运算时间的增长率。随着输入的增长，运算时间的增长率。1）有些计算机需要用户提供程序运行时）有些计算机需要用户提供程序运行时间的上限，一旦达到这个上限，程序间的上限，一旦达到这个上限，程序将被强制结束。将被强制结束。2）正在开发的程序可能需要提供一个满）正在开发的程序可能需要提供一个满意的实时响应。意的实时响应。Asymptotic Run Timeo令算法的输入为令算法的输入为n，若算法的运行时间，若算法的运行时间f(n)为为n的的m阶函数，则称阶函数，则称f(n)是是m阶阶的。的。o一旦去除了表示算法运行时间的函数中的低一旦去除了表示算法运行时间的函数中的低阶项和首项常数，就称我们是在度量算法的阶项和首项常数，就称我们是在度量算法的渐进运行时间渐进运行时间。o分析算法的复杂性的目的分析算法的复杂性的目的:n比较求解同一问题的两个不同算法的效率，而比较求解同一问题的两个不同算法的效率，而当要比较的两个算法的渐进复杂性的阶不相同当要比较的两个算法的渐进复杂性的阶不相同时，只要能确定出各自的阶就可以判定哪一个时，只要能确定出各自的阶就可以判定哪一个算法的效率高。算法的效率高。Figure 1.5MarkoO：运行时间的上界运行时间的上界o：在运行时间的一个常数因子内提供一个在运行时间的一个常数因子内提供一个下界下界o：算法的精确阶算法的精确阶o：说明两个函数属于不同的复杂性类说明两个函数属于不同的复杂性类Symbol Oo定义定义1.2 1.2 令令f(n)和和g(n)是从自然数集到非负实是从自然数集到非负实数集的两个函数，如果存在一个自然数数集的两个函数，如果存在一个自然数n0和一和一个常数个常数c 0，使得：，使得：对于所有的对于所有的nn0，有，有f(n)cg(n)，则称则称f(n)为为O(g(n)，记作：记作：f(n)=O(g(n)。Ultimate Formo如果如果 存在，那么存在，那么蕴含着蕴含着Symbol o定义定义1.3 1.3 令令f(n)和和g(n)是从自然数集到非负实是从自然数集到非负实数集的两个函数，如果存在一个自然数数集的两个函数，如果存在一个自然数n0和一和一个常数个常数c 0，使得：，使得：对于所有的对于所有的nn0，有，有f(n)cg(n)，则称则称f(n)为为(g(n)，记作：记作：f(n)=(g(n)。Ultimate Formo如果如果 存在，那么存在，那么蕴含着蕴含着o推论：推论：f(n)是是(g(n)，当且仅当，当且仅当g(n)是是O(f(n)。Symbol o定义定义1.4 1.4 令令f(n)和和g(n)是从自然数集到非负实数是从自然数集到非负实数集的两个函数，如果存在一个自然数集的两个函数，如果存在一个自然数n0和两个正和两个正常数常数c1和和c2，使得：，使得：对于所有的对于所有的nn0，有，有c1 g(n)f (n)c2 g(n)，则称则称f(n)为为(g(n)，记作：记作：f(n)=(g(n)。Ultimate Formo如果如果 存在，那么存在，那么蕴含着蕴含着o推论：推论：f(n)是是(g(n)，当且仅当，当且仅当f(n)=O(g(n)并并且且f(n)=(g(n)。FigureExample1.5o设设：由于对由于对 ,因此有因此有 ；由于对由于对 ,因此有因此有 。此外此外,由于对由于对 ,因此有因此有 。o极限方式极限方式：由于由于 ，因此有，因此有 和和 。Example1.12o考虑级数考虑级数 ，显然，显然 n1log jjO(n log n)=即即又又=那么那么同理得到同理得到输入输入:正整数正整数 n 2。输出输出:如果如果 n 是素数则输出为真，否则为假是素数则输出为真，否则为假。1、s 2、for j 2 to s3、if j 划分 n then return false4、end for5、return trueAnalysiso假定假定：可以在可以在O(1)时间内计算出来时间内计算出来；o对任意的素数对任意的素数n n：循环执行次数为：循环执行次数为 -1，则算法是则算法是O()；o考察对象考察对象1 1：算法中循环的执行次数；：算法中循环的执行次数；o对任意的对任意的n n值值(如如n n为偶数为偶数)：循环执行次数为：循环执行次数为 1，则算法是，则算法是(1)；o推论：推论：蛮力算法既不是蛮力算法既不是()也不是也不是(1)。Complexity Typeso令令R为复杂性函数集合上由下列条件定义的为复杂性函数集合上由下列条件定义的关系：关系：f R g当且仅当当且仅当f(n)=(g(n)。由。由这个关系导出的等价类称为这个关系导出的等价类称为复杂性类复杂性类。o例如：例如：n所有的二次多项式属于同一个复杂性类所有的二次多项式属于同一个复杂性类n2。o问题：问题：如何区分属于不同复杂性类的两个函数？如何区分属于不同复杂性类的两个函数？o定义定义1.5 1.5 令令f(n)和和g(n)是从自然数集到非负实数集是从自然数集到非负实数集的两个函数，如果对每一个常数的两个函数，如果对每一个常数c 0，存在一个正，存在一个正整数整数n0，使得：，使得：对于所有的对于所有的nn0，都有，都有f(n)cg(n)，则称则称f(n)是是o(g(n)的的，即，即f(n)=o(g(n)记作：记作：f(n)g(n)。Symbol Ultimate Formo如果如果 存在，那么存在，那么蕴含着蕴含着o推论：推论：f(n)=o o(g(n)，当且仅当，当且仅当f(n)=O(g(n)并且并且g(n)O(f(n)。Complexity Types RelationSpace Complexityo1.多用户系统中运行时，需指明多用户系统中运行时，需指明分配给该程序的内存大小。分配给该程序的内存大小。o2.想提前知道是否有足够可用的内想提前知道是否有足够可用的内存来运行该程序。存来运行该程序。o3.一个问题可能有若干个内存需求一个问题可能有若干个内存需求各不相同的解决方案，从中择取。各不相同的解决方案，从中择取。o1 估算估算一个程序所能解决的问题的最大规模。一个程序所能解决的问题的最大规模。Space Usedo算法使用的空间算法使用的空间：n为了求解问题的实例而执行的计算步骤所需要为了求解问题的实例而执行的计算步骤所需要的内存空间数目，不包括分配用来存储输入的的内存空间数目，不包括分配用来存储输入的空间。空间。n写入每一个内存空间都至少需要一定的时间。写入每一个内存空间都至少需要一定的时间。o推论：推论：令令T(n)和和S(n)分别代表算法的时间复杂性和空分别代表算法的时间复杂性和空间复杂性，则有间复杂性，则有S(n)=O(T(n)。Example1.17 1.18 1.19算法算法空间复杂度空间复杂度LINEARSEARCH(1)(1)MERGE(n)(n)BOTTOMUPSORT(n)(n)考虑：算法考虑：算法SELECTIONSORT和和INSERTIONSORT的空间复杂性？的空间复杂性？Tradeoffo许多问题需要在时间与空间之间权衡。许多问题需要在时间与空间之间权衡。o迄今为止讨论过的大多数算法中，增加空间迄今为止讨论过的大多数算法中，增加空间并没有导致明显的速度加快，相反却往往成并没有导致明显的速度加快，相反却往往成立，即减小空间会导致算法速度的降低。立，即减小空间会导致算法速度的降低。Optimal Algorithmo如果可以证明任何一个求解问题如果可以证明任何一个求解问题的算法必的算法必定是定是(f(n)，那么我们把在，那么我们把在O(f(n)时间内时间内求解问题求解问题的任何算法都称为问题的任何算法都称为问题的的最优最优算法算法。