数据结构（一）——算法的时间和空间复杂度

发表于 | 分类于

最后更新时间：2018/10/12 16:05

算法 的优劣主要体现在算法的复杂性上。
算法复杂度 是运行该算法时所占用计算机资源的多少。
计算机资源 主要分为时间和空间资源。

时间复杂度

时间频度 是计算一个程序语句执行的次数，通常情况下时间频度计算的是具体的数值。记作T(n)。

时间复杂度 是算法运行时所占用的时间资源，用来度量算法的运行时间，算法占用的时间短算法效率就高，反之占用的时间长算法的效率就低。时间复杂度记作O(f(n))。

时间复杂度与时间频度的关系：T(n)=O(f(n))

注：时间复杂度不是计算程序的运行时间，时间复杂度实际上就是一个函数，该函数计算的是执行基本操作的次数，与时间频度不同的是它计算的不是具体的数值。

时间复杂度的计算方法

1、若是程序执行次数常数，都是常数阶用O(1)表示。
2、若程序执行次数为不固定项，选取相对执行次数最多的项，也就是最高项。
3、若选取的最高项系数不为1，则最高项系数化为1。

注：1、如果算法的执行时间不随着问题规模n的增加而增长，即使算法中有上千条语句，其执行时间也不过是一个较大的常数。此类算法的时间复杂度是O(1)。
    2、当有若干个循环语句时，算法的时间复杂度是由嵌套层数最多的循环语句中最内层语句的频度f(n)决定的。

示例

1
2
3
4
5
　for (i=1; i<=n; i++)
　　       x++;               //执行n次
　for (i=1; i<=n; i++)
　     for (j=1; j<=n; j++)
　　          x++;            //执行n^2次

此段代码的执行次数为n+n^2次，根据时间复杂度的计算方法，选出最高项你n^2，因此时间复杂度为O(n^2)。

常见的时间复杂度

术语 阶 举例
常数阶 O(1) 输出一句话
对数阶 O(log2n) 对有序数组进行折半查找
线性阶 O(n) 对数组进行顺序查找
线性对数阶 O(nlog2n) 归并排序
平方阶 O(n^2) 选择排序
立方阶 O(n^3) 传统的矩阵相乘
k次方阶 O(n^k)
指数阶 O(2^n) 汉诺塔

随着问题规模n的不断增大，上述时间复杂度不断增大，算法的执行效率越低。
常见的算法时间复杂度由小到大依次为：
Ο(1)＜Ο(log2n)＜Ο(n)＜Ο(nlog2n)＜Ο(n2)＜Ο(n3)＜…＜Ο(2^n)＜Ο(n!)

常数阶

1
2
3
4
int test(void) {
    printf("Hello, World!\n");      //  需要执行 1 次
    return 0;       // 需要执行 1 次
}

上面这段代码一共需执行语句2次，是常数，因此是常数阶O(1)。

1
2
3
4
5
6
7
8
int test(void) {
    int x=1;      
    while (x <10)
    {
        x++;      //需要循环执行10次
    }
    return 0;     
}

上面这段代码一共需执行语句10次，也是常数，因此也是常数阶O(1)。

对数阶

1
2
3
4
int i = 1, n = 100;
while(i < n){
    i = i * 2;
}

求这段代码的时间复杂度,首先设执行次数为x, 2^x=n 即 x=log2n，因此是对数阶O(log2n)

线性阶

1
2
3
4
5
6
int test(int n) {
    for(int i = 0; i<n; i++) {         // 需要执行 (n + 1) 次
        printf("Hello, World!\n");      // 需要执行 n 次
    }
    return 0;       // 需要执行 1 次
}

这段代码执行了(n+1+n+1)=2n+2次,运用计算方法去掉常数，化系数为1得到n，因此是线性阶O(n)。

线性对数阶

平方阶

1
2
3
4
int sum=0；                 
for(i=1;i<=n;i++)        //需要执行n次
   for(j=1;j<=n;j++)     //需要执行n^2次
     sum++；

这段代码执行了n^2+n，运用计算方法去选取最高项，得到n^2，因此是平方阶O(n^2)。

立方阶

1
2
3
4
5
6
7
8
for(i=0;i<n;i++)
    {  
       for(j=0;j<i;j++)  
       {
          for(k=0;k<j;k++)
             x=x+2;  
       }
    }

这段代码执行了0+(1-1)*1/2+···+(n-1)n/2=n(n+1)(n-1)/6，运用计算方法去选取最高项，得到n^3，因此是平方阶O(n^3)。

指数阶

时间复杂度的最坏情况与平均情况

对于算法分析，一种是计算所有情况的平均值，这种时间复杂度的计算方法称为平均时间复杂度，它是最有意义的，因为是期望的运行时间。另一种是计算最坏情况下的时间复杂度，这种方法称为最坏时间复杂度。在一般情况下都是计算最坏时间复杂度。

空间复杂度

空间复杂度 是算法在运行时所占用的空间资源，程序在运行时产生临时变量需要占用存储空间，占用存储空间资源少算法效率高，占用存储空间资源多算法效率低。利用算法的空间复杂度，可以对算法的运行所需要的内存空间有个预先估计。

注：空间复杂度强调的是使用的辅助空间的大小，而不是指所有的数据所占用的空间大小。

##空间复杂度的计算方法

1、若创建的变量为常数，则用O(1)表示。
2、若是递归算法，则空间复杂度=递归调用次数N*每次递归所要的辅助空间。

示例

1
2
int a,b,c;
printf("%d %d %d\n",a,b,c);

这段代码的存储3个变量，为常数，因此是O(1)。

1
2
3
4
5
6
7
int fun(int n){
    int k=10;
    if(n==k)
        return n;
    else
        return fun(++n);
}

这段代码是递归算法，每次递归调用时都会创建1个变量，调用n次，空间复杂度O(n*1)=O(n)。

常用排序算法的时间复杂度和空间复杂度

排序方法 平均时间复杂度 最坏时间复杂度 空间复杂度 稳定性
冒泡排序 O(n^2) O(n^2) O(1) 是
选择排序 O(n^2) O(n^2) O(1) 不是
直接插入排序 O(n^2) O(n^2) O(1) 是
归并排序 O(nlogn) O(nlogn) O(n) 是
快速排序 O(nlogn) O(n^2) O(logn) 不是
堆排序 O(nlongn) O(nlogn) O(1) 不是
希尔排序 O(nlongn) O(n^s) O(1) 不是
计数排序 O(n+k) O(n+k) O(n+k) 是
基数排序 O(N*M) O(N*M) O(M) 是