算法精解_C语言描述算法性能分析，如何评判算法！

无论是在设计还是应用一种广泛认可的算法时，我们必须了解算法的性能如何。

算法的性能可以通过运算速度和消耗空间来评判。

之所以要了解算法的性能，原因有很多方面。如，当要解决一个问题时，有很多算法可供选择，理解了算法的性能，有助于选择最合适的算法有效的解决我们的问题。

举例来说，垃圾回收算法，它用来回收从堆上分配的动态存储空间，并且需要相当长的时间来运行。认识到这一点，我们就能注意只在适当的时候运用此算法。

理解和确定算法性能的方法和维度包括：最坏情况分析、O表示法、计算复杂度。

通常用来评判算法性能的三种情况是：最佳情况、平均情况与最坏情况。

理解每种情况是如何产生的对于分析算法来说非常重要，因为算法在不同情况下的性能差异可能很大。例如，线性搜索是一种自然但效率低下的搜索技术，它简单的从数据集的头部遍历到尾部。最佳情况是要查找的元素处于数据集的第1个位置，这样仅在遍历一个元素之后就找到目标元素。最坏情况下，目标元素在数据集的最后一个位置，这样必须在遍历完所有元素之后才能找到目标元素。平均情况下，可能在数据集中间的某个位置找到目标元素。

为什么要做最坏情况分析

理解一种算法在各种情况下有怎么样的性能是非常重要的，但是通常情况下，我们更关心算法在最坏情况下的性能如何：

• 许多算法在最坏情况下会消耗相当长的时间。例如，搜索元素时，数据集中根本没有我们想要查找的那个元素。可以想象一下，这种情况在数据库查找应用中经常出现。
• 考虑算法在最佳情况下的性能没有太多意义，因为很多算法在最佳情况下的表现都相同。例如，在最佳情况下，几乎所有的算法都可以在一次查找中找到元素，而这并不能说明到底哪种算法更好。
• 分析算法平均情况下的性能往往不太容易。甚至我们很难去界定哪种情况属于“平均情况”。通常我们不能精确获得平均情况下的算法性能，这是因为我们无法准确控制算法的执行状态。
• 最坏情况可以告诉我们算法性能 的上限。分析一个算法的最坏情况，可以保证在任何情况下此算法的表现都不会比最坏情况差，而其他情况肯定比最坏情况要好。

虽然 我们把最坏情况当做很多算法性能的度量，但也有例外。因为有些时候我们也会平均情况来评判算法的性能。例如：随机算法中的快速排序算法，它使用了概率论理论的基础，从而有效地保证了平均情况下性能的准确性。

O表示法是用来表示算法性能的最常见正式的标记法。从形式上看在一定的条件因素下，O表示法指明了一个函数的上限值。具体来说，如果g(n)是f(n)的一个上限值，那么对于常数c，我们总是可以找到一个n（称为n₀），当n>=n₀时,f(n)<=g(n)。

通常我们以函数所处理的数据量来表示算法的性能。也就是对于大小为n的数据，我们用函数f(n)来表示它的算法性能。在很多情况下，我们可以完全确定f的具体值，但通常我们并不关注此具体值。我们需要关注的是当算法处理的数据变得无穷大时，算法的性能将趋近一个什么样的值。一个算法的增长速率或者说一个算法的增长规律非常重要，因为当输入数据量变得无穷大时，它可以用来描述算法的效率到底有多高。O表示法正是这样一种表示算法增长规律的方法。

当我们以增长率的角度去观察f(n)时， 有几件事就会变得非常明显。首先，我们可以忽略常数项，因为随着n的值变得越来越大，常数项最终变得可忽略不计。例如：如果T(n)=n+50表示一个计算运行时间的算法，当所要处理的数据n的大小仅仅为1024时，此表达式的常数项对运行时间的影响就已经不到5%了。其次，我们可以忽略常数因子，同样，随着n值逐渐变大，常数因子也可以忽略不计。例如：如果有两个都是用来计算运行时间的算法：T1(n)=n的2次方和T2(n)=10n，录T1表达式中的n大于10时，T1就会大于T2。最后，我们只需要考虑高阶项的因子。因为随着n的增加，高阶项因子的值会迅速超过低阶项因子的值。例如：如果T(n)=n的2次方+n 表示一个计算运行时间的算法，当n为1024时，表达式中低阶因子的值已经占不到运行时间值的0.1%了。这些简单的规则用O表示法列举出来如下：

• 常数项用O(1)表示。当分析一个算法的运行时间时，如果知道无论它处理多大的数据量，它都得至少消耗一段固定的时间，那么就可以用常数项表示此固定的时间。对某些常数c，正式地表述为：

        O(c)=O(1)

• 常量因子往往被忽略。当分析一个算法运行时间时，如果有某些任务都将执行相同数量的次数，就可以运用此规则。例如：有3个任务的运行时间为T(n)=n，运行结果表示为O(3n)，根据规则可以简化为O(n)。对于某些常量c，正式地表述为：

        O(cT)=cO(T)=O(T)

• 加法运算取最大值。当分析一个算法的运行时间时，如果一个任务在另一个任务之后顺序执行，可以运用此规则。例如，有两个顺序执行的任务，其运行时间分别为：T1(n)=n和T2(n)=n的2次方，运行结果表示为O(n)+O(n的2次方)，根据规则，可以简化为O(n的2次方)。正式地表述为：

        O(T1)+O(T2)=O(T1+T2)=max(O(T1),O(T2))

• 乘法结果不需要改变，但是往往可以用更紧凑的方法表示。如果一个任务的执行引起另一个任务的迭代执行，可以运用此规则。例如，在一个嵌套循环中，外层迭代为T1，内层迭代为T2，如果T1(n)=n,T2(n)=n,那么运行结果表示为O(n)O(n)或O(n的2次方）。正式地表述为：

        O(T1)O(T2)=O(T1T2)

假设某算法的运行时间由函数T(n)=3n²+10n+10来表示。若用O表示法，此函数可以简化为：

O(T(n)) = O(3n²+10n+10) = O(3n²)= O(n²)

这表明，当n增长到任意大时，算法的运行时间将主要由n²项来决定。我们可以通过每一项所占整个运行时间的百分比来证明这一点。例如，当n=10时，计算结果如下：

3n²:  3X10²/(3X10²+10²+10)=73.2%

10n:   10²/(3X10²+10²+10)=24.4%

10:     10/(3X10²+10²+10)=24.2%

我们已经看到了，n2占据了整个运行时间的大部分比例。现在，考虑当n=100时的结果，如下：

3n²:    3X100²/(3X100²+10X100+10)=96.7%(更大)

10n:   10X100/(3X100²+10X100+10)=3.2%（更小）

10:       10/(3X100²+10X100+10)<0.1%（更小）

 这里我们看到，n²项占据了几乎整个运行时间，同时其他项的影响力变得更小！

在谈起算法性能时，我们通常关注的是它的复杂度，复杂度与它处理数据量所需要的资源（通常是时间）的增长速率密切相关。

O表示法能够描述一个算法的复杂度。使用O表示法，通过观察算法的整体构造，我们很容易就能描述最坏情况下的算法复杂度。

我们来看一种推测算法所用资源的方法，以帮助我们理解复杂度。假设有一种算法，它由k条语句组成，每条语句都消耗C_i 资源（通常是时间）。如果要计算它的整个运行时间，无论每条语句以什么样的顺序执行，我们只需要将它们的运行时间相加求和即可，也就是说从C₁加到C_k。通常每条语句并不是简单的按照顺序执行的，所以在整个计算过程中必须考虑其他更复杂的情况。例如，有些语句是在循环中执行的，那么这样的一些语句所消耗的资源必须乘上迭代的次数。假设在这种算法中k=6，其中语句3~5均在循环中（1~n）执行，其他语句顺序执行，那么此算法的整体运行时间表示为：

T(n) = c₁+c₂+n(c₃+c₄+c₅)+c₆

在前面的例子中，它的复杂度O(n)并没有表明运行此算法实际需要多少时间。换句话说，一个增长率低的算法并不意味着它会消耗更少的资源。事实上，算法的复杂度并没有具体的计量单位。它只是表明当计算数据量的大小变化时，将如何影响算法所消耗的资源。例如，用O(n)表示T(n)复杂度只说明算法的运行时间与因素n成正比，在特定n的取值条件下，T(n)能够达到上限值。正式地说，当我们谈到T(n)<=cn时，随着数据的变化，C作为一个常量因子不会影响到算法的运行时间。这就像在某种类型的计算机上运行算法，编译器会生成与算法有关的机器码和相关常量。

很多时候，我们都会遇到很多复杂的计算，所以需要非常熟悉这些计算方法。表1列出了一些常见的复杂计算发生时的复杂度。表2列出了当n变化时，这些复杂度的增长速率是如何变化的。

就像一种算法的复杂度几乎不关注具体的运行时间，衡量算法的复杂度也没有高效与低效之说。虽然复杂度在一定程序上说明算法的运算效率，但一个特定的复杂度要根据具体的情况来衡量它是否高效。一般来说，在给定一定标准的情况下，能够使此算法表现最佳时，我们就认为此算法是高效的。通常在解决同一个问题时，如果一种算法的复杂度比其他算法都低，并且没有过多的常数项，我们就可以认为此算法是高效的。但也有一些棘手的问题，在这些问题中如果不设定一个近似值就无法找到一个“有效的”解决方案。这是一类特殊的问题，称为NP完全问题（NP-Complete Problem）。

虽然算法的复杂度是衡量算法性能的重要参考因素，但在实际应用中，我们通常还要考虑其他更多的因素。当两种算法有同样的复杂度时，就得考虑对算法影响不太大的条件和因素。例如，有种算法，数据量大小的变化对它的性能没有太大的影响，那么一个复杂度大且常量很小的算法所表现的性能可能比一个复杂度小但常量很大的算法所表现出的性能更好。其他一些值得考虑的因素包括：算法的复杂度会如何维持和发展，以及如何使一种算法在实际中更加的有效地实现。一个高效的实现并不能总是影响算法复杂度，但它可以降低常量因素的影响，从而使算法在实际应用中更加高效。

本节描述插入排序法在最坏情况下对运行时间的分析。

插入排序是一种简单的排序算法，它在一个有序的数据集中查找放置新元素的位置，并将新元素插入进去。

代码1：插入排序

/* issort.c */
#include 
#include 

#include "sort.h"

/* issort */
int issort(void *data,int size,int esize,int (*compare)(const void *key1,const void key2))
{
    char *a = data;
    void *key;
    int i,j;
    
    /*Allocate storage for the key element. */
    if((key=(char *)malloc(esize))==NULL)
        return -1;
    /* Repeatedly insert a key element among the sorted elements. */
    for(j=1; j=0 && compare(&a[i*esize],key)>0)
        {
            memcpy(&a[(i+1)*esize],&a[i*esize],esize);
            i--;
        }
        
        memcpy(&a[(i+1)*esize],key,esize);
    }
    
    /*Free the storage allocated for sorting */
    free(key);
    
    return 0;
}

O(T(n))=O(n²/2 + n/2 – n) = O(n²/2)= O(n²)