从零开始的数据结构与算法(二):算法与复杂度

305 阅读11分钟

算法是对特定问题求解步骤的一种描述,是指令的有限序列。其中每一条指令表示一个或多个操作。算法与数据结构是相辅相成的。解决某一类特定问题的算法可以选定不同的数据结构,而且选择恰当与否直接影响算法的效率。

1 算法特性

  • 有穷性:一个算法必须在有穷步之后结束,即必须在有限时间内完成。

  • 确定性:算法的每一步必须有确切的定义,无二义性,且在任何条件下算法只有唯一一条执行路径,即对于相同的输入只能得出相同的输出。

  • 可行性:算法中的每一步都可以通过已经实现的基本运算的有限次执行得以实现。

  • 输入:一个算法具有零个或多个输入,这些输入取自特定的数据对象集合。

  • 输出:一个算法具有一个或多个输出,这些输出同输入之间存在某种特定的关系。

2 算法设计要求

  • 正确性:算法的执行结果应当满足预先规定的功能和性能要求。正确性要求表明算法必须满足实际需求,达到解决实际问题的目标。
  • 可读性:一个算法应当思路清晰、层次分明、简单明了、易读易懂。可读性要求表明算法主要是人与人之间交流解题思路和进行软件设计的工具,因此可读性必须要强。同时一个可读性强的算法,其程序的可维护性、可扩展性都要好得多,因此,许多时候人们往往在一定程度上牺牲效率来提高可读性。
  • 健壮性:当输入不合法数据时,应能适当处理,不至于引起严重后果。健壮性要求表明算法要全面细致地考虑所有可能的边界情况,并对这些边界条件做出完备的处理,尽可能使算法没有意外的情况。
  • 高效性:有效使用存储空间和有较好的时间效率。高效性主要是指时间效率,即解决相同规模的问题时间尽可能短。

算法复杂度

对于同一个问题,使用不同的算法,也许最终得到的结果是一样的,但在过程中消耗的资源和时间却会有很大的区别。那么我们应该如何去衡量不同算法之间的优劣呢?

算法的复杂性体现在运行该算法时的计算机所需资源的多少上,计算机资源 最重要的是时间和空间 (即寄存器)资源,因此复杂度分为时间和空间复杂度。

  • 时间维度:是指执行当前算法所消耗的时间,我们通常用「时间复杂度」来描述。
  • 空间维度:是指执行当前算法需要占用多少内存空间,我们通常用「空间复杂度」来描述。

因此,评价一个算法的效率主要是看它的时间复杂度和空间复杂度情况。然而,有的时候时间和空间却又是「鱼和熊掌」,不可兼得的,那么我们就需要从中去取一个平衡点。

3 时间复杂度

一个算法花费的时间与算法中语句的执行次数成正比例,哪个算法中语句执行次数多,它花费时间就多。 一个算法中的语句执行次数称为语句频度或时间频度。记为 T(n)。

例题:计算 1-1000所有整数之和

// 方法一
int getSum1(int n) {
    int sum = 0; 
    for (int i = 1; i <= n; i++) {
    	sum += i;
    }
    return sum;
}
// 方法二
int getSum2(int n) {
    int sum = (1 + n) * n / 2;
    return sum;
}

可以看出,当 n 趋向于很大时,方法一 for 的执行次数会随值增大,而方法二的语句执行次数不变,其时间复杂度要低。

3.1 时间复杂度的计算

时间复杂度所研究的在于当 n 趋于足够大时,不同算法在时间量级上的不同。如果算法 A 的时间复杂度为 T(2n+10),算法 B 的时间复杂度为 T(3n),算法 C 的时间复杂度为 T(n*n),当 n 足够大时,C 的耗时要比 A 和 B 的耗时远远大得多,所以可以将时间复杂度的部分项进行忽略,只保留主要项来对算法时间复杂度进行定性分析。

3.1.1 忽略常数项

n T(n)=2n+20 T(n)=2n T(n)=3n+10 T(n)=3n
1 22 2 13 3
2 24 4 16 6
5 30 10 25 15
8 36 16 34 24
15 50 30 55 45
30 80 60 100 90
100 220 200 310 300
300 620 600 910 900

  1. 2n+20 和 2n 随着 n 变大,执行曲线无限接近, 20 可以忽略。
  2. 3n+10 和 3n 随着 n 变大,执行曲线无限接近, 10 可以忽略。

3.1.2 忽略系数项

n T(n)=3n²+2n T(n)=5n²+7n T(n)=n³+5n T(n)=6n³+4n
1 5 12 6 10
2 16 34 18 56
5 85 160 150 770
8 208 376 552 3104
15 705 1230 3450 20310
30 2760 4710 27150 162120
100 30200 50700 1000500 6000400

  1. 随着 n 值变大,3n²+2n 和 5n²+7n ,执行曲线重合, 说明 这种情况下,5 和 3 可以忽略。
  2. 而 n³+5n 和 6n³+4n,执行曲线分离,说明多少次方式关键。

3.1.3 忽略低次项

n T(n)=2n²+3n+10 T(n)=2n² T(n)=n²+5n+20 T(n)=n²
1 15 2 26 1
2 24 8 34 4
5 75 50 70 25
8 162 128 124 64
15 505 450 320 225
30 1900 1800 1070 900
100 20310 20000 10520 10000

  1. 2n²+3n+10 和 2n² 随着 n 变大,执行曲线无限接近,可以忽略 3n+10。
  2. n²+5n+20 和 n² 随着 n 变大,执行曲线无限接近,可以忽略 5n+20。

3.1.4 总结

  1. 一般情况下,算法中的基本操作语句的重复执行次数是问题规模 n 的某个函数,用 T ( n ) 表示,若有某个辅助函数 f ( n ),使得当 n 趋近于无穷大时,T ( n ) / f ( n ) 的极限值为不等于零的常数,则称 f ( n ) 是 T ( n ) 的同数量级函数。记作 T ( n ) = O( f ( n ) ),称O( f ( n ) ) 为算法的渐进时间复杂度,简称时间复杂度。
  2. T ( n ) 不同,但时间复杂度可能相同。 如:T ( n ) = n²+7n+6 与 T ( n ) = 3n²+2n+2 它们的 T ( n ) 不同,但时间复杂度相同,都为 O ( n² )。
  3. 计算时间复杂度的方法:
    1. 用常数 1 代替运行时间中的所有加法常数 T ( n ) = n²+7n+6 => T ( n ) = n²+7n+1;
    2. 修改后的运行次数函数中,只保留最高阶项 T ( n ) =n²+7n+1 => T ( n ) = n²;
    3. 去除最高阶项的系数 T ( n ) = n² => T ( n ) = n² => O ( n² );

4 平均时间复杂度和最坏时间复杂度

4.1 平均时间复杂度

平均时间复杂度是指所有可能的输入实例均以等概率出现的情况下,该算法的运行时间。

4.2 最坏时间复杂度

最坏情况下的时间复杂度称最坏时间复杂度。 一般讨论的时间复杂度均是最坏情况下的时间复杂度。这样做的原因是:最坏情况下的时间复杂度是算法在任何输入实例上运行时间的界限,这就保证了算法的运行时间不会比最坏情况更长。

5 常见时间复杂度

  1. 常数阶 O ( 1 )
  2. 对数阶 O ( log n )
  3. 线性阶 O ( n )
  4. 线性对数阶 O ( n log n )
  5. 平方阶 O ( n² )
  6. 立方阶 O ( n³ )
  7. k 次方阶 O ( n ^ k )
  8. 指数阶 O ( 2 ^ n )

不同时间复杂度对应曲线图

常见的算法时间复杂度由小到大依次为:

Ο ( 1 ) < Ο ( log n ) < Ο ( n ) < Ο ( n log n ) < Ο ( n² ) < Ο ( n³ ) < Ο ( n ^ k ) < Ο ( 2 ^ n )

随着问题规模 n 的不断增大,上述时间复杂度不断增大,算法的执行效率越低。从图中可见,我们应该尽可能避免使用指数阶的算法。

5.1 常数阶 O ( 1 )

无论代码有多长,即使几万几十万行,只要没有循环结构,时间消耗不随某个变量的增长而增长,他的时间复杂度都是 O ( 1 )。

int method(int n) {
    int a = 100 * n;
    return a;
}

5.2 对数阶 O ( log n )

int method(int n) {
    int i = 1;
    int sum = 0;
    while (i < n ) {
        sum += i;
        i = i * 2;
    }
    return sum;
}

在while循环里面,每次都将 i 乘以 2,乘完之后,i 距离 n 就越来越近了。假设循环 x 次之后,i 就大于 n 了,此时这个循环就退出了,也就是说 2 的 x 次方等于 n,那么 x = log2 n 也就是说当循环 log2 n 次以后,这个代码就结束了。因此这个代码的时间复杂度为:O ( log2 n ) 。 O ( log2 n ) 的这个2 时间上是根据代码变化的,i = i * 3 ,则是 O ( log3 n ) 。

5.3 线性阶 O ( n )

int method(int n) {
  	int sum = 0;
  	for (int i = 0; i < n; i++) {
  	    sum += i;
  	}
  	return sum;
}

5.4 线性对数阶 O ( n log n )

int method(int n) {
    int j = 1;
    int sum = 0;
    for (int i = 0; i < n; i++) {
        while (j < n ) {
            sum += j;
            j = j * 2;
        }
    }   
    return sum;
}

将时间复杂度为 O ( log n ) 的代码循环N遍的话,那么它的时间复杂度就是 n * O ( log n ),也就是了O ( n log n )。

5.5 平方阶 O ( n² )

int method(int n) {
	int j = 1;
	int sum = 0;
  	for (int i = 0; i < n; i++) {
  	    for (int j = 0; j < n; j++) {
  	        sum += i * j;
  	    }
  	}
  	return sum;
}

如果把 O ( n ) 的代码再嵌套循环一遍,它的时间复杂度就是 O ( n² ),这段代码其实就是嵌套了2层n循环,它的时间复杂度就是 O( n * n ),即 O ( n² )。

如果将其中一层循环的 n 改成 m,那它的时间复杂度就变成了 O( m * n )

int method(int n, int m) {
    int j = 1;int sum = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            sum += i * j;
        }
    }
    return sum;
}

5.6 高次阶 O ( n³ )、O ( n ^ k )

高次阶类似于平方阶 O ( n² ),如果把 O ( n ) 的代码再嵌套三次。

5.7 指数阶 O ( 2 ^ n )

从前面的图中可以看出指数阶 O ( 2 ^ n ) 随 n 的增长是极快的,在一般的程序算法中一般不会出现也应该避免出现指数阶的时间复杂度。

6 排序的复杂度

排序方法 时间复杂度(平均) 时间复杂度(最好) 时间复杂度(最坏) 空间复杂度 时间复杂度(平均)
插入排序 O ( n² ) O ( n ) O ( n² ) O ( 1 ) 稳定
希尔排序 O ( n ^ 1.3) O ( n ) O ( n² ) O ( 1 ) 不稳定
选择排序 O ( n² ) O ( n² ) O ( n² ) O ( 1 ) 不稳定
堆排序 O ( n log n ) O ( n log n ) O ( n log n ) O ( 1 ) 不稳定
冒泡排序 O ( n² ) O ( n ) O ( n² ) O ( 1 ) 稳定
快速排序 O ( n log n ) O ( n log n ) O ( n² ) O ( n log n ) 不稳定
归并排序 O ( n log n ) O ( n log n ) O ( n log n ) O ( n ) 稳定
计数排序 O ( n + k ) O ( n + k ) O ( n + k ) O ( n + k ) 稳定
桶排序 O ( n + k ) O ( n² ) O ( n ) O ( n + k ) 稳定
基数排序 O ( n + k ) O ( n * k ) O ( n * k ) O ( n + k ) 稳定

8 空间复杂度

8.1 定义

算法的空间复杂度通过计算算法所需的存储空间实现,算法的空间复杂度的计算公式记作:S ( n ) = O ( f ( n ) ),其中,n 为问题的规模,f ( n ) 为语句关于 n 所占存储空间的函数。

  1. 类似于时间复杂度的讨论,一个算法的空间复杂度 (Space Complexity) 定义为该算法所耗费的存储空间,它也是问题规模 n 的函数。
  2. 空间复杂度 (Space Complexity) 是对一个算法在运行过程中临时占用存储空间大小的量度。有的算法需要占用的临时工作单元数与解决问题的规模 n 有关,它随着 n 的增大而增大,当 n 较大时,将占用较多的存储单元,例如快速排序归并排序算法, 基数排序就属于这种情况
  3. 在做算法分析时,主要讨论的是时间复杂度。 从用户使用体验上看,更看重的程序执行的速度。一些缓存产品 (redis, memcache) 和算法(基数排序)本质就是用空间换时间