程序性能2--时间复杂性

阅读《数据结构算法与应用：C++描述》第二章程序性能所做的笔记。

第2章程序性能的所有笔记如下：

1. 程序性能1—空间复杂性
2. 程序性能2—时间复杂性
3. 程序性能3—渐进符号

时间复杂性

时间复杂性的组成

影响一个程序空间复杂性的因素也能影响程序的时间复杂性。

一个程序P所占用的时间T(P) = 编译时间 + 运行时间。编译时间与实例的特征无关。另外，可以假定一个编译过的程序可以运行若干次而不需要重新编译。因此我们将主要关注程序的运行时间，运行时间通常用”$t_p$(实例特征)”来表示。

存在这一个事实：一个算术操作所需要的时间取决于操作数的类型(int,float,double等),这个事实增加了获得一个精确的计算公式的烦琐程度。所以必须按照数据类型对操作进行分类。

有两个更可行的方法可用来估算运行时间：

1. 找出一个或更多的操作，确定这些关键操作所需要的执行时间；
2. 确定程序总的执行步数。

操作计数

估算一个程序或函数的时间复杂性的一种方式就是首先选择一种或多种操作(如加、乘和比较等),然后确定这种(些)操作分别执行了多少次。这种方法是否成功取决于识别关键操作的能力，这些关键操作对时间复杂性的影响最大。下面的几个例子都采用了这种方法。

例1 多项式求值

考察多项式$P(x) = \sum_{i=0}^n c_i x^n$。如果$c_n \neq 0$,则P是一个n维多项式。

下列程序实现了多项式求值。

/*多项式求值*/
template<class T>
T PolyEval(T coeff[], int n, const T&x){
    // 计算n次多项式的值，coeff[0:n]为多项式的系数
    T y = 1, value = coeff[0];
    for (int i = 1; i < n; i++){
        y *= x;
        value += y*coeff[i];
    }
    return value;
}

这里的for循环中的循环条件，书中代码是有点错误的，应该是i<n,不能带上等于。

在这个例子中，假定根据for循环内部所执行的加和乘的次数来估算时间复杂性。可以使用维数n作为实例特征。进入for循环的总次数为n，每次循环执行1次加法和乘法(这种操作计数不包含循环控制变量i每次递增所执行的加法)。加法的次数为n，乘法的次数为2n。

第二种求解多项式的方法是使用Horner法则，它是采用如下的分解式计算一个多项式：

$$P(x) = (\ldots(c_n*x+c_{n-1})*x+c_{n-2})*x+c_{n-3})*x+\ldots)*x+c_0$$

代码实现如下：

/*使用Horner法则求解多项式*/
template<class T>
T Horner(T coeff[], int n, const T&x){
    T value = coeff[n-1];
    for (int i = 2; i <= n; i++){
        value = value*x + coeff[n - i];
    }
    return value;
}

书中的代码也是有些问题，n应该代表的是coeff这个数组的大小，所以首先是T value = coeff[n-1];这句代码，书中是直接等于coeff[n]，这里应该是coeff[n-1],然后就是for循环的初始条件，是i=2，而不是i=1。

使用Horner后，加法还是需要n次，但是乘法也只需要n次即可。因此，使用这个函数会比PolyEval函数更快。

例2 计数排序

这里通过两段代码实现计数排序的方法。

元素在队列中的名次（ r a n k）可定义为队列中所有比它小的元素数目加上在它左边出现的与它相同的元素数目。
例如，给定一个数组 a=[4, 3, 9, 3, 7]作为队列，则各元素
的名次为r =[2, 0, 4, 1, 3]

这里我的实现的代码方法跟书本有所不一样，如下所示：

template<class T>
void Rank(T a[], int n, int r[]){
    // 计算a[0:n-1]中n个元素的排名
    for (int i = 0; i < n; i++)
        r[i] = 0;       // 初始化排名数组
    // 逐对比较所有的元素
    for (int i = 0; i < n; i++){
        for (int j = i+1; j < n; j++){
            if (a[i] <= a[j])
                r[j]++;
            else
                r[i]++;
        }
    }
}

书中给出的代码，其比较次数是1+2+3+···+n-1 = $(n-1)n\over 2$
而我给出的代码实现，其比较总次数也是相同的，$(n-1)n\over 2$,差别应该是在比较是(n-1)+(n-2)+···+2+1.

根据例2中计算出数组中每个元素的名次，就可以利用元素名次按照递增的次序对数组中的元素进行重新排列，使得$a[0]\le a[1]\le \ldots \le a[n-1]$

下面代码是使用了一个附加的数组u实现按名次排序。

/*利用Rank函数中得到的每个元素的名次，对数组重新排序*/
template<class T>
void Rearrange(T a[], int n, int r[]){
    // 按顺序重排数组a中的元素，使用附加数组u
    T *u = new T[n];
    // 在u中移动到正确的位置
    for (int i = 0; i < n; i++)
        u[r[i]] = a[i];
    // 移回到a中
    for (int i = 0; i < n; i++)
        a[i] = u[i];
    delete[] u;
}

这是书中给出的实现方法，这个方法需要移动元素2n次，因此，加上例2中的实现，整个排序需要执行，$(n-1)n\over 2$次比较操作和2n次移动操作，这种排序方法被称为计数排序。

另一种方法是原地重排数组元素，不需要一个附加数组，实现代码如下：

template<class T>
void Rearrange2(T a[], int n, int r[]){// 原地重排数组元素

    for (int i = 0; i < n; i++)
        // 获取应该排在 a [ i ]处的元素
    while (r[i] != i) {
        int t = r[i];
        Swap(a[i], a[t]);
        Swap(r[i], r[t]);
    }
}

/*交换两个数组元素*/
template<class T>
void Swap(T& a, T&  b){
    T temp = a;
    a = b;
    b = temp;
}

新的程序需要执行的最少交换次数是0(初始数组已经是按序排列)，最大的交换次数是2(n-1)。注意每次交换操作至少把一个元素移动到正确位置(如a[i])，所以在n-1次交换之后，所有的n个元素已全部按序排列。

例3 选择排序

选择排序：首先找出最大的元素，把它移动到 a [ n-1 ]，然后在余下的 n-1个元素中寻找最大的元素并把它移动到a [ n-2 ]，如此进行下去，

这是按照递增次序重排数组，也可以按照递减次序排序，就是每次找最小的元素，然后依次与数组的第一个元素交换。

代码实现如下：

/*选择排序，按照递增次序排列*/
template<class T>
void selectionSort(T a[], int n){
    for (int size = n; size > 1; size--){
        int max = Max(a, size);
        Swap(a[max], a[size - 1]);
    }
}

/*寻找数组中最大元素*/
template<class T>
int Max(T a[], int n){
    int pos = 0;
    for (int i = 1; i < n; i++){
        if (a[pos] < a[i])
            pos = i;
    }
    return pos;
}
/*交换两个数组元素*/
template<class T>
void Swap(T& a, T&  b){
    T temp = a;
    a = b;
    b = temp;
}

在上述函数中，Max函数会进行$(n-1)n\over 2$次比较操作，而Swap函数会进行3(n-1)次移动操作。

这种实现方式的选择排序的一个缺点是：即使元素已经按序排列，程序仍然继续运行。

因此为了终止不必要的循环，可以在查找最大元素期间检查数组是否已经按序排列，实现方式如下：

/*及时终止的选择排序*/
template<class T>
void selectionSort2(T a[], int n){
    bool isSorted = false;      // 加入终止循环的条件
    for (int size = n; !isSorted && (size > 1); size--){
        int pos = 0;
        isSorted = true;
        // 找最大元素
        for (int i = 1; i < size; i++){
            if (a[pos] <= a[i])
                pos = i;
            else
                // 没有按序排列
                isSorted = false;
        }
        Swap(a[pos], a[size - 1]);
    }
}

这种新的实现方法，最好的情况是数组已经是有序数组的情况，那么外部for循环仅需要执行一次，内部寻找最大元素的比较次数是n-1次。而最坏的情况则是外部for循环执行n-1次，执行的比较次数是$(n-1)n\over 2$次。

例4 冒泡排序

冒泡排序是采用一种“冒泡策略”把最大元素移到右部。在冒泡过程中，对相邻的元素进行比较，如果左边的元素大于右边的元素，则交换这两个元素。

下面是冒泡排序的一种实现方法

/*一次冒泡*/
template<class T>
void Bubble(T a[], int n){
    for (int i = 0; i < n-1; i++){
        if (a[i]>a[i + 1])
            Swap(a[i], a[i + 1]);
    }
}

/*对数组a[0:n - 1]中的n个元素进行冒泡排序*/
template <class T>
void BubbleSort(T a[], int n){

    for (int i = n; i>1; i--)
            Bubble(a, i);
}

这种实现方法中元素比较的次数是$(n-1)n\over 2$。

冒泡排序跟选择排序一样，也是需要设计一个可以及时终止的冒泡排序函数。如果在一次冒泡过程中没有发生元素互换，这说明数组已经按序排列，没有必要再继续进行冒泡过程。

实现如下：

/*一次冒泡*/
template<class T>
bool Bubble(T a[], int n){
    // 没有发生交换
    bool isSwaped = false;
    for (int i = 0; i < n - 1; i++){
        if (a[i]>a[i + 1]){
            Swap(a[i], a[i + 1]);
            // 发生了交换
            isSwaped = true;
        }
    }
    return isSwaped;
}

/*对数组a[0:n - 1]中的n个元素进行冒泡排序*/
template <class T>
void BubbleSort(T a[], int n){

    for (int i = n; i > 1 && Bubble(a, i); i--){}
}

在最好的情况下比较次数只需要n-1次，而最坏情况则和第一种实现方法相同。

例5 插入排序

因为只有一个元素的数组是一个有序数组，所以可以从仅包含欲排序的n个元素的第一个元素的数组开始。通过把第二个元素插入到这个单元数组中，可以得到大小为2的有序数组，并按照这个方法继续进行下去，最终将得到一个大小为n的有序数组。而这种排序方式就是插入排序。

实现代码如下所示：

/*向一个有序数组中插入元素,假定a的大小超过n*/
template<class T>
void Insert(T a[], int& n, const T& x){
    int i;
    for (i = n - 1; i >= 0 && x < a[i]; i--)
        a[i + 1] = a[i];
    a[i + 1] = x;
}

template<class T>
void InsertionSort(T a[], int n){
    for (int i = 1; i < n; i++){
        T t = a[i];
        Insert(a, i, t);
    }
}

这种排序方法，最好的情况下比较次数是n-1，最坏的情况是$(n-1)n\over 2$。

执行步数

上述例子都是利用操作计数方法来估算程序的时间复杂性，但会忽略了所选择操作之外其他操作的开销。

在统计步数的方法中，要统计程序/函数中所有部分的时间开销。与操作计数一样，执行步数也是实例特征的函数。尽管任一个特定的程序可能会有若干个特征(如输入个数，输出个数，输入和输出的大小)，但可以把执行步数看成是其中一部分特征的函数。通常是选择一些感兴趣的特征，例如，如要了解程序的运行时间(即时间复杂性)是如何随着输入个数的增加而增加的，这种情况下，可以把执行步数看成是输入个数的函数。因此在确定一个程序的执行步数之前，必须确切地知道将要采用的实力特征，这些特征不仅定义了执行步数表达式中的变量，而且定义了以多少次计算作为一步。

操作步

操作步是独立于所选特征的任意计算单位，如10次加法可以视为一步，100次乘法也可以视为一步，但n次加法不能视为一步，其中n是实例特征。

程序步

程序步可以定义为一个语法或语义意义上的程序片段，该片段的执行时间独立于实例特征。

可以通过设置一个全局变量count(其初始值为0)来确定一个程序或函数为完成其预定任务所需要的执行步数。可以把count引入到程序语句之中，每当原始程序或函数中的一条语句被执行时，就为count累加上该语句所需要的执行步数。

一个例子如下所示：

template<class T>
T Sum(T a[], int n){// 计算 a[0:n - 1]中元素之和

    T tsum = 0;
    count++; // 对应于tsum = 0
    for (int i = 0; i < n; i++) {
        count++; // 对应于f o r语句
        tsum += a[i];
        count++; // 对应于赋值语句
    }
    count++; // 对应于最后一个f o r语句
    count++; //对应于r e t u r n语句
    return tsum;
}

上述函数Sum是用来计算一个数组元素之和，通过添加一个全局变量count来计算函数的执行步数。可以得知每次调用该函数需要执行2n+3步。

总结

时间复杂性的介绍就到这里为止，时间复杂性是由编译时间和运行时间决定，但书中说明了编译时间是与实例特征关，同时也假定了一次编译后就可以不用编译就能进行若干次运行。而在估算运行时间的时候介绍了两种方法，分别是估算操作计数和执行步数，书中分别给出了不少例子，这里记录的例子主要是操作计数中的例子，包括了选择排序，计数排序，插入排序，冒泡排序等。

还是需要在不断编程中不断实践本小节所介绍的方法。