数据结构与算法——第1章-时间和空间复杂度(1.2)

发表于 分类于 ， ， 阅读时长 ≈ 3 分钟

数据结构与算法——第1章-时间和空间复杂度(1.2)

一 概述

1
2
3
4
1.怎么判断哪个算法更好
2.好算法的标准
3.时间复杂度
4.空间复杂度

二 怎么判断哪个算法更好

1
2
3
4
5
算法即解决问题的方法。同一个问题，使用不同的算法，
虽然得到的结果相同，但耗费的时间和资源肯定有所差异。
就比如拧一个螺母，扳手和钳子都可以胜任，但使用钳子拧螺母肯定没有扳手的效率高。

如果解决问题的算法有多种，怎么判断哪个算法更好（更优）？

三 好算法的标准

3.1 算法

1
2
3
4
5
6
解决一个问题的方法可能有很多，但能称得上算法的，首先它必须能解决这个问题（称为准确性），
且根据其编写出的程序在任何情况下都不能崩溃（称为健壮性）。

注意，程序和算法是完全不同的概念：
-算法是解决某个问题的想法、思路
-程序是根据算法编写出来的真正可运行的代码

3.2 算法的效率

1
2
3
4
5
6
7
在满足准确性和健壮性的基础上，还有一个重要的筛选条件：通过算法所编写出的程序的运行效率。

程序的运行效率具体可以从2个方面衡量：
-程序的运行时间
-程序运行所需内存空间的大小

根据算法编写出的程序，运行时间更短，运行期间占用的内存更少，该算法的运行效率就更高，算法也就更好。

3.3 算法的时间、空间复杂度

1
2
3
如何衡量一个算法所编写出程序的运行效率？
-时间复杂度衡量程序运行时间的多少
-空间复杂度衡量程序运行所需内存空间的大小

四 时间复杂度

4.1 预估时间复杂度

1
2
3
4
5
6
7
8
判断一个算法所编程序运行时间的多少，并不是将程序编写出来、通过在计算机上运行所消耗的时间来度量。
一方面，解决一个问题的算法可能有很多种，一一实现的工作量无疑是巨大的；
另一方面，计算机软、硬件环境不同，即便使用同一台计算机，
不同时间段其系统环境也不相同，程序的运行时间很可能会受影响，严重时甚至会导致误判。

实际场景中更喜欢用一个估值来表示算法所编程序的运行时间。
表示一个算法所编程序运行时间的多少，
用的并不是准确值（事实上也无法得出），而是根据合理方法得到的预估值。

4.2 预估时间复杂度示例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
如何预估一个算法所编程序的运行时间？
很简单，先分别计算程序中每条语句的执行次数，然后用总的执行次数间接表示程序的运行时间。

示例一、以一段简单的C语言程序为例，预估出此段程序的运行时间：

for(inti= 0; i<n； i++)// 从 0到 n, 执行 n+1次
{
	a++; // 从 0 到 n-1， 执行 n 次
}

整段代码中所有语句共执行了（n+1）+n次，即2n+1次。
数据结构中，每条语句的执行次数称为该语句的频度。整段代码的总执行次数，即整段代码的频度。

示例二、
for(int i=0;i<n;i++)  //n+1
{
	for(int j=0;j<m;j++) //n*(m+1)
	{
		num++;            //n*m
	}
}
说明
-此段程序的频度为: (n+1)+n*(m+1)+n*m，即2*n*m+2n+1。

-不同程序的运行时间，更多场景中比较的是在最坏条件下程序的运行时间。
以上面这段程序为例，最坏条件即当n、m都为无限大时的运行时间。

-当n、m都无限大时，可以认为n=m，2*n*m+2n+1可以简化为2*n²+2*n+1，
这就是此段程序在最坏情况下的运行时间，也就是此段程序的频度。

4.3 复杂度简化

1-简化一

1
2
3
4
5
6
7
当n、m都无限大时，可以认为n=m，2*n*m+2n+1可以简化为2*n²+2*n+1，
这就是此段程序在最坏情况下的运行时间，也就是此段程序的频度。

如果比较以上2段程序的运行时间，即比较2n+1和2*n²+2 *n+1的大小，
显然当n无限大时，前者要远远小于后者（显然，第1段程序的运行时间更短，运行更快）：

类似2n+1、2*n²+2 *n+1这样的频度，还可以再简化吗?

2-简化2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
以2n十1为例，当n无限大时，是否在2n的基础上再做+1操作，并无关紧要，
因为2n和2n+1当n无限大时，它们的值是无限接近的。
甚至还可以认为，当n无限大时，是否给n乘2，也是无关紧要的，因为n是无限大，2n也是无限大。

再以无限大的思想来简化2*n²+2 *n+1。当n无限大的:
-首先，常数1是可以忽略不计的
-其次，对于指数级的2*n²来说，是否在其基础上加2*n，并无关紧要
-甚至于，对于是否给 n²乘 2，也可以忽略

因此，最终频度2 *n²+ 2 *n +1可以简化为 n²

在数据结构中，频度表达式可以这样简化：
-去掉频度表达式中，所有的加法常数式子。例如2*n²+2*n+1简化为2*n²+2*n
-如果表达式有多项含有无限大变量的式子，只保留一个拥有指数最高的变量的式子。例如2n²+ 2n 简化为2n²
-如果最高项存在系数，且不为1，直接去掉系数。例如2n²系数为2，直接简化为n²

事实上，对于一个算法（或一段程序）来说，其最简频度往往就是最深层次的循环结构中某一条语句的执行次数。
例如2n+1最简为n，实际上就是a++语句的执行次数；
同样2 *n²+2*n+1简化为n²，实际上就是最内层循环中num++语句的执行次数。

4.4 大O记法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
得到最简频度的基础上，为了避免人们随意使用a、b、c等字符来表示运行时间，需要建立统一的规范。
数据结构推出了大O记法（注意：是大写的字母O，不是数字0）来表示算法（程序）的运行时间。
发展至今，此方法已为大多数人所采纳。

大O记法的表示方法也很简单，格式为：O(频度），其中，频度为最简之后所得的频度。

例如，用大O记法表示上面2段程序的运行时间，则上面第一段程序的时间复杂度为O(n)，
第二段程序的时间复杂度为O(n²）。

常用的几种时间复杂度，以及它们之间的大小关系：

O(1)常数阶<O(log n)对数阶< O(n)线性阶<O(n²) 平方阶< O(n²）(立方阶）<O(2”）（指数阶)

注意：这里仅介绍以最坏情况下的频度作为时间复杂度，而某些实际场景中，
还可以用最好情况下的频度和最坏情况下的频度的平均值来作为算法的平均时间复杂度。

五 空间复杂度

5.1 空间复杂度

1
2
3
4
5
6
7
8
9
10
11
12
13
14
和时间复杂度类似，一个算法的空间复杂度，也常用大O记法表示。
每一个算法所编写的程序，运行过程中都需要占用大小不等的存储空间，例如：
 -程序代码本身所占用的存储空间
 -程序中如果需要输入输出数据，也会占用一定的存储空间
 -程序在运行过程中，可能还需要临时申请更多的存储空间

首先，程序自身所占用的存储空间取决于其包含的代码量，
如果要压缩这部分存储空间，就要求在实现功能的同时，尽可能编写足够短的代码。

程序运行过程中输入输出的数据，往往由要解决的问题而定，
即便所用算法不同，程序输入输出所占用的存储空间也是相近的。

事实上，对算法的空间复杂度影响最大的，往往是程序运行过程中所申请的临时存储空间。
不同的算法所编写出的程序，其运行时申请的临时存储空间通常会有较大不同。

5.2 示例

1
2
3
4
5
6
7
8
9
10
举个例子
int n;
scanf("od", &n);
int a[10];

通过分析不难看出，这段程序在运行时所申请的临时空间，并不随n的值而变化。
而如果将第3行代码改为：

int a[n];
此时，程序运行所申请的临时空间，和n值有直接的关联。

5.3 大O表示

1
2
3
4
5
6
7
所以，如果程序所占用的存储空间和输入值无关，则该程序的空间复杂度就为O（1）；
反之，如果有关，则需要进一步判断它们之间的关系：
 -如果随着输入值n的增大，程序申请的临时空间成线性增长，则程序的空间复杂度用O(n)表示
 -如果随着输入值n的增大，程序申请的临时空间成n²关系增长，则程序的空间复杂度用 O(n²)表示
 -如果随着输入值n的增大，程序申请的临时空间成n°关系增长，则程序的空间复杂度用 O(n²)表示

在多数场景中，一个好的算法往往更注重的是时间复杂度的比较，而空间复杂度只要在一个合理的范围内就可以。

六 参考

  • CSDN—时间复杂度、空间复杂度