算法分析基本概念.PPT

1.8.2 ?符号 ● INSERTIONSORT执行的比较次数（元运算）次数是(n2-n)/2,是n2阶的，故选择k为某个适当选择的正常数。则其运算次数比较最多是kn2 即：算法的运行时间是?(n2)。 ● 可作如下解释:只要当排序元素的个数等于或超过某个阈值n0时，那么对于某个常量k0，运行时间至多为kn2。 （强调：数据量较大） 注意：数据量很大时，也不能说运行时间总是恰好为kn2。这样, ?符号提供了一个运行时间的上界,它一般不是算法的实际运行时间。 给出?符号的数学定义： 定义1.2 令f(n)和g(n)是自然数集到非负实数集 的两个函数，如果存在一个自然数n0和一个常数 c0,使得?n?n0时f(n)?cg(n),则称f(n)为?(g(n))。 因此，如果limn??f(n)/g(n)存在，那么 limn??f(n)/g(n)?? =》 f(n)=O(g(n))。 ● 定义1.2说明f(n)不比g(n)的某个常数倍增长得更快; ?符号给出了算法运行时间的一个上界。 ● eg.f(n)=5n3+7n2-2n+13,可以写成: f(n)=5n3+?(n2). 这样表示对于低阶项不感兴趣。 1.8.3 ?符号 ● ?(读作“大omega”)符号在运行时间的一个常数因子内提供一个下界。 ● 例如算法INSERTIONSORT的运行时间是?(n)。 自底向上算法运算时间是?(nlogn) ● 可解释为：无论何时，当被排序的元素个数等于或超过某一个阈值n0时，那么对某个常数c0，运行时间至少是n的c倍。 自底向上的运行时间至少是nlogn的c倍。 ● ?符号也被广泛用于表示问题的下界，换句话说,它通常用来表示解决某一问题的算法的下界（最小运行时间）。 ?符号的定义： 定义1.3 令f(n)和g(n)是自然数集到非负实数集的两个函数,如果存在一个自然数n0和一个常数c0,使得 ? n?n0, f(n)?cg(n) 则称f(n)为?(g(n))。 因此，如果limn??f(n)/g(n)存在，那么 limn??f(n)/g(n)?0蕴含着f(n)=?(g(n))。 (也就是说：f(n)至少不比g(n)的某个倍数增长慢，起码是一样快的) ● 从定义1.2与1.3可以看出： f(n)为?(g(n))当且仅当g(n)为?(f(n))。 (即：f(n)是g(n)的上界，则g(n)就是f(n)的下界) 就像足球一样，中韩足球的成绩。冲出亚洲的过程中，我们现在找不到一个增长速率能够超越韩国足球的增长速率。 （为什么不说巴西、阿根廷、荷兰、西班牙呢，因为那不是紧挨着的上界，注意区分） “你问我中国足球何时得第一，别吓着上帝。” --《青花瓷-国足》 更深的理解： 如果一个算法的最小运算复杂度是?(g(n))，则认为基于该算法的核心思路（比较、选择）无法设计出渐进复杂性小于g(n)的程序。 1.8.4 ?符号 ● 选择排序算法比较次数是n(n-1)/2（没有最少和最多），所以该算法执行元运算次数总是和n2成正比，由于每一个元运算需要一个常量时间，我们说算法SELECTIONSORT的运行时间?(n2)(读做“theta n平方”)。 ● 可做如下解释： ● 这一符号是表示算法的精确阶的，它蕴含算法的运行时间有确切界限。 存在常数c1和c2，在n≥n0的任何大小的输入情况下： c1n2=runtime=c2n2。表明，对于任意正整数n, 算法SELECTIONSORT的运行时间为?(n2)。 ?符号的定义 定义1.4 ： 令f(n)和g(n)是自然数集到非负实数集的两个函数，如果存在一个自然数n0和两个正常数c1和c2,使得?n?n0时, c1g(n)?f(n)?c2g(n),则称f(n)为?(g(n))的。 因此如果limn??f(n)/g(n)存在，那么limn??f(n)/g(n)=c (其中c必须是一个大于0的常数)蕴含着f(n)=?(g(n))。 ●与前两个不同， ?符号给出了算法运行时间增长率的一个精确描述；可以认为，?类似于?, ?类似于?，而?类似于?。 ● 定义1.4的一个重要推论是:f(n)=?(g(n))当且仅当f(n)=?(g(n))并且f(n)=?(g(n))。 例如：虽然100n?n，但100n=?(n)(上界)；虽然n?100n，但n=?(100n)（下界）；虽然n?100n，但是n=?(100