复杂性的渐近性态及其阶

1、复杂性的渐近性态及其阶随着经济的发展、社会的进步、科学研究的深入，要求用计算机解决的问题越来越复 杂，规模越来越大。但是，如果对这类问题的算法进行分析用的是第二段所提供的方法，把 所有的元运算都考虑进去，精打细算，那么，由于问题的规模很大且结构复杂，算法分析的 工作量之大、步骤之繁将令人难以承受。因此，人们提出了对于规模充分大、结构又十分复 杂的问题的求解算法，其复杂性分析应如何简化的问题。我们先要引入复杂性渐近性态的概念。设丁(N)是在第二段中所定义的关于算法A的复 杂性函数。一般说来，当N单调增加且趋于8时,T(N)也将单调增加趋于“对于T(N)，如 果存在尸(N)，使得当N-8时有：(T

2、(N )-T,(N )/T(N) 0那么，我们就说厂(N)是T(N)当NT”时的渐近性态，或叫T(N)为算法A当N-8的渐近复 杂性而与T(N)相区别，因为在数学上，尸(N)是T(N)当NT”时的渐近表达式。直观上，T(N)是T(N)中略去低阶项所留下的主项。所以它无疑比T(N)来得简单。比如 当T(N)=3N 2+4Nlog2N +7时，厂(N)的一个答案是3N2，因为这时有：显然3N 2比3N 2 +4Nlog2N +7简单得多。由于当NT”时T(N)渐近于厂(N)，我们有理由用厂(N)来替代T(N)作为算法A在Nt” 时的复杂性的度量。而且由于于厂(N)明显地比T(N)简单，这种替代明显

3、地是对复杂性分析 的一种简化。进一步，考虑到分析算法的复杂性的目的在于比较求解同一间题的两个不同算法的效 率，而当要比较的两个算法的渐近复杂性的阶不相同时，只要能确定出各自的阶，就可以判 定哪一个算法的效率高。换句话说，这时的渐近复杂性分析只要关心厂(川)的阶就够了，不 必关心包含在厂(N)中的常数因子。所以，我们常常又对厂(N)的分析进-步简化，即假设算 法中用到的所有不同的元运算各执行一次，所需要的时间都是一个单位时间。综上所述，我们已经给出了简化算法复杂性分析的方法和步骤，即只要考察当问题的 规模充分大时，算法复杂性在渐近意义下的阶。与此简化的复杂性分析方法相配套，需要引 入五个渐近意义

4、下的记号：0、G、。、o和3。以下设f(N)和g(N)是定义在正数集上的正函数。如果存在正的常数C和自然数珞，使得当NN0时有f(N)1有3N1 时有 N+102410 时有 2N 2+11N -101有N2N0 时有N3C N2,即NN1， 有F(N)N2 有 G(N)N3有：F(N)C1 f(N)C1 h(N)C3h(N)类似地，有：G(N)C2g(N)C2h(N)C3h(N)因而O(f)+O(g) =F(N)+G(N)N0时有f(N)Cg(N)，则称函数f(N)当N充分大时下 有界，且g(N)是它的一个下界，记为f(N)=c(g(N)。这时我们还说f(N)的阶不低于g(N)的 阶。Q的这

5、个定义的优点是与0的定义对称，缺点是当/(对自然数的不同无穷子集有不 同的表达式，且有不同的阶时，未能很好地刻画出f(N)的下界。比如当：11006泌困为正偶数泌正奇数时，如果按上述定义 值。只能得到f(N)=Q(1)，这是一个平凡的下界，对算法分析没有什么价然而，考虑到。的上述定义有与0的定义的对称性，又考虑到常用的算法都没出现上 例中那种情况，所以本文还是选用它。我们同样也可以列举Q的一些运算规则。但这里从略，只提供一个应用的例子。还是 考虑算法Search在最坏情况下的时间复杂性函数Tmax(m)。由它的表达式(2.7)及已知a,s,t 均为大于0的常数，可推得，当m1时有：XTmax(

6、m)(m+1)a+(2m+V)tma+2mt=(a+2t)m，于是 T(m)=Q(m)omax我们同样要指出，用。评估算法的复杂性，得到的只是该复杂性的一个下界。这个下 界的阶越高，则评估就越精确，结果就越有价值。再则，这里的Q只对问题的一个算法而 言。如果它是对一个问题的所有算法或某类算法而言，即对于一个问题和任意给定的充分大 的规模N，下界在该问题的所有算法或某类算法的复杂性中取，那么它将更有意义。这时得 到的相应下界，我们称之为问题的下界或某类算法的下界。它常常与0配合以证明某问题 的一个特定算法是该问题的最优算法或该问题在某算法类中的最优算法。明白了记号0和Q之后，记号3将随之清楚，因为我们定义f(N)=Q(g(N)则f(N)=0(g(N) 且f(N)=Q(g(N)o这时，我们说f(N)与g(N)同阶。比如，对于算法Search在最坏情况下的 时间复杂性 Tmax(m)o 已有 Tmax(m)=0(m)和 Tmax(m)=Q(m)，所以有 Tmax(m)=6(m)，这是对 Tmax(m)的阶的精确估计。最后，如果对于任意给定的形0,都存在非负整数珞，使得当NN0时有f(N)eg(N), 则称函数f(N)当N充分大时比g(N)低阶，记