算法：算法的性能分析

前言

来自：keshiim
链接：keshiim博客地址 https://keshiim.github.io

在程序设计中算法的性能分析是非常重要的，针对一个具体的问题可能提出若干种不同的算法实现。如何从这些算法中找出性能最有的那个？或者说是针对一个具体的算法如果评论它的优劣？这里要涉及的一个问题就是如何对算法的性能进行评价？评价算法性能主要充两个方面着手：

算法的执行时间
算法所有占中的存储空间

这两个指标分别对应算法的时间复杂度与空间复杂度，下面分别来说。

算法的时间复杂度

定义

算法的时间复杂度的目的是为了近似的评估算法的执行时间，因为要准确测量一个算法的执行时间多少是非常困难的，他收到计算机软硬件环境的影响。它的定义是这样的：
T(n) = O(f(n))
它表示随问题规模n的增大，算法的执行时间增长率和算法中语句的总体的执行次数f(n)增长率相同，称作算法的渐进时间复杂度，简称时间复杂度。其中这里的O来表示数量级，f(n)一般是算法中频度最大的语句频度。

如何求时间复杂度

要求算法的时间复杂度，关键就在于找到这个算法中执行频度最大的那条语句f(n)，找到了f(n)那么时间复杂度T(n)自然就出来了。
下面举例说明

1. 常数阶 $ O(1) $

void swap(int *i, int *j) {
    int temp = *i;
    *i = *j;
    *j = temp;
}

以上3条语句的语句频度都是1，而且该程序段的执行时间是一个与问题规模n无关的常熟。这种类型的算法的时间复杂度：T(n)=O(1)。

2. 线性形 $ O(n) $

1
2
3

for（int i = 0; i < n; i++) {
    //do you want to do.
}

很明显这种类型的算法的语句频度与问题的规模n刚好是呈线性相关的，时间复杂度为T(n)=O(n)。

3. 平方型 $ O(n^2) $

int[] a = {3, 2, 4, 7, ...., n};
for (int i = 0; i < n - 1; i++) {
    for (int j = i + 1; j < n; j++) {
        if (a[i] > a[j]) {
        //do swap, f(n)=n*n
        int temp = a[i];
        a[i] = a[j];
        a[j] = temp;   
    }
}

当有若干循环语句时，算法的时间复杂度是由嵌套最深的循环语句的频度f(n)决定。而忽略其他嵌套层次更低的循环。

4. 立方型 $ O(n^3) $

for i..n
    for ...
        for ...
            //do sth. //频度最大

常见的时间复杂度

$ O(1) $常熟型
$ O(\log2^{n}) $对数行
$ O(n\log2^{n}) $二维型
$ O(n) $线性型
$ O(n^2) $平方型
$ O(n^3) $立方型
$ O(2^n) $指数型

一般情况下，随问题规模n的增大，时间复杂度T(n)增长最慢的算法为最优算法。以上几种算法随n的不断增加时间复杂度增加越来越快，因此一般应该选择用O(nk)的算法。避免使用指数阶的算法。

最坏时间复杂度与平均时间复杂度

算法的时间复杂度不仅与问题规模n相关海域输入实例的初始状态有关。
看例子：

1
2
3

int i = n - 1;
while (i >= 0 && (a[i] != k))
    i--;

上述算法的时间复杂度不仅与n相关还与输入的数组a与k的取值相关：

最坏情况：数组a中没有与k相等的元素。则语句3的频度f(n)=n，时间复杂度T(n)=O(n)
最好情况：或a中最后一个元素等于k，则语句3的频度f(n)=0，时间复杂度T(n)=O(1)

一般不特别说明，讨论的时间复杂度均是最坏情况下的时间复杂度，这样做的原因是能够保证算法在任何输入实例情况下都能够被考虑到。而平均时间复杂度是指所有可能的输入实例均以等概率出现的情况下的时间复杂度，在这个例子中平均复杂度即为：O(1)

因此上述算法的时间复杂度为：O(n)

算法的控件复杂度

辅助存储空间

一般情况下，一个程序在机器上执行时，处理需要春初本身所需要的代码、输入数据外，还需要一些对数据金鑫操作的辅助存储空间。其中输入数据所占用的具体空间取决于问题本身，与算法无关。因此我们所讨论的空间发咋读只与改算法的实现时所需要的辅助空间单元个数相关。即空间复杂度讨论的是算法所需要的辅助存储空间。

定义

算法的空间发咋读S(n)定义为该算法所耗费的存储空间的数量级，它是问题规模n的函数，记作：

S(n) = O(f(n))

若算法执行时间所需要的辅助空间相对于输入数据量而言是一个常数，则称这个算法为原地工作，负数空间为O(1)。看例子：

将一维数组a中的n个数据逆序存放到原数据中，下面是两种算法

算法1

for (i = 0; i < n; i++)
    b[i] = a[n - i - 1];
for (i = 0; i < n; i++)
    a[i] = b[i];

算法2

for (i = 0; i < n >> 2; i ++) {
    t = a[i];
    a[i] = a[n - i - 1];
    a[n - i - 1] = t;
}

算法1的空间复杂度为O(n)，需要一个大小为n的辅助数组b
算法2的空间复杂度为O(1)，仅需要一个变量t，与问题规模n无关

总结

算法的空间复杂度与时间复杂度合称为算法的复杂度。面对不同的算法如何选择主要就从这两个方面去考虑，理想情况是一个算法的时间与空间复杂度都小，但这是我很难做到的，面对不同的情况小具体问题具体分析：是以时间换空间，还是以空间换时间。

排序算法的性能比较(表)

排序方法	最好时间复杂度	平均时间复杂度	最坏时间复杂度	辅助空间	稳定性
直接插入	O(n)	O($ n^2 $)	O($ n^2 $)	O(1)	稳定
简单选择	O($ n^2 $)	O($ n^2 $)	O($ n^2 $)	O(1)	不稳定
冒泡排序	O(n)	O($ n^2 $)	O($ n^2 $)	O(1)	稳定
希尔排序	—	O($ n^1.3 $)	—	O(1)	不稳定
快速排序	O(nlogn)	O(nlogn)	O($ n^2 $)	O(nlogn)	不稳定
堆排序	O(nlogn)	O(nlogn)	O(nlogn)	O(1)	不稳定
归并排序	O(nlogn)	O(nlogn)	O(nlogn)	O(n)	稳定
基数排序	O(d(n+rd)	O(d(n+rd)	O(d(n+rd)	O(rd)	稳定