如何理解时间复杂度和空间复杂度——保姆级详解

前言

其实简单来说，就是同一个功能

• 别人写的代码跑起来占内存50M,耗时50毫秒
• 而你写的代码跑起来占内存300M,耗时300毫秒，甚至更多

所以

1.衡量代码好坏有两个非常重要的标准是：运行时间和占用空间，就是我们后面要说到的时间复杂度和空间复杂度，也是学好算法的重要基石。
2.这也是会算法和不会算法的工程师的区别、更是薪资的区别，因为待遇好的大厂面试基本都有算法。

可能有人会问：别人是怎么做到的？代码还没开发完，运行起来之前怎么知道占多少内存和运行时间呢？

确切的占用内存或运行时间确实算不出来，而且同一段代码在不同性能的机器上执行的时间也是不一样的，可是代码的基本执行次数，我们是可以算得出来的，这就是要说到时间复杂度了。

什么是时间复杂度

1. 时间复杂度（time complexity）

1.1 语句频度T(n)

算法执行需要的时间，理论上只能通过上机来测试出来，但是我们不可能对所有的算法都来上机测试。我们只需要知道哪个算法用时比较多即可。一个算法花费的时间与算法中基本操作语句的执行次数成正比，哪个算法中语句执行次数多，哪个算法用时就长。而一个算法中语句执行的次数叫做语句频度，计作 T(n)。
总结一下，就是说我们用 T(n) 来算法执行的时间。

1.2 时间复杂度

在T(n)中，n 叫做问题的规模，当 n 不断变化时，语句频度 T(n) 也会变化。我们想知道T(n) 的变化规律，于是便引入了时间复杂度的概念。
在衡量时间复杂度时候，我们通常用 O(x) 的概念。这里需要知道量级的概念：
如果

这是时候，我们称作 f(n) 是 T(n) 同数量级函数，就计作 T(n)=O(f(n))，也就把 O(f(n)) 叫做算法的 渐进时间复杂度，简称 时间复杂度。
需要明白的是，语句频度T(n) 不同，时间复杂度也是可以相同的，直观理解就是说看最高次项。比如 T(n)=n^2+5n+6 和 T(n)=3n^2+n+3，时间复杂度都是

• 不同时间复杂度时间变化图
  

来看看下面这个栗子：

int main
{
	printf("我吃了一个苹果\n");
	printf("我又吃了一个苹果\n");
	return 0;
}
1
2
3
4
5
6

调用这个函数，里面总执行次数就是3次，这个没毛病，都不用算

那么下面这个栗子呢

int main
{
	int n = 0;
	for(int i = 0;i < n;i ++)
	{
	printf("我吃了一个苹果\n");
	}
	return 0;
}
1
2
3
4
5
6
7
8
9

那这个函数里面总执行次数呢？根据我们传进去的值不一样，执行次数也就不一样，但是大概次数我们总能知道

int n = 0;                      //执行1次
i < n;                          //执行n+1次
i ++;                           //执行n+1次
printf("我吃了一苹果\n");        //执行n次
return 0;                       //执行1次
1
2
3
4
5

这个函数的总执行次数就是 3n + 4 次，对吧

可是我们开发不可能都这样去数，所以根据代码执行时间的推导过程就有一个规律，也就是所有代码执行时间 T(n)和代码的执行次数 f(n) ，这个是成正比的，而这个规律有一个公式T(n) = O( f(n) )

n 是输入数据的大小或者输入数据的数量
T(n) 表示一段代码的总执行时间
f(n) 表示一段代码的总执行次数
O 表示代码的执行时间 T(n) 和 执行次数f(n) 成正比

完整的公式看着就很麻烦，别着急，这个公式只要了解一下就可以了，为的就是让你知道我们表示算法复杂度的 O() 是怎么来的，我们平时表示算法复杂度主要就是用 O()，读作大欧表示法，是字母O不是零

只用一个 O() 表示，这样看起来立马就容易理解多了

回到刚才的两个例子，就是上面的两个函数

• 第一个函数执行了3次，用复杂度表示就是 O(3)
• 第二个函数执行了3n + 4次，复杂度就是 O(3n+4)

这样有没有觉得还是很麻烦，因为如果函数逻辑一样的，只是执行次数差个几次，像O(3) 和 O(4)，有什么差别？还要写成两种就有点多此一举了，所以复杂度里有统一的简化的表示法，这个执行时间简化的估算值就是我们最终的时间复杂度。

简化的过程如下

• 如果只是常数直接估算为1，O(3) 的时间复杂度就是 O(1)，不是说只执行了1次，而是对常量级时间复杂度的一种表示法。一般情况下，只要算法里没有循环和递归，就算有上万行代码，时间复杂度也是O(1)
• O(3n+4) 里常数4对于总执行次数的几乎没有影响，直接忽略不计，系数 3 影响也不大，因为3n和n都是一个量级的，所以作为系数的常数3也估算为1或者可以理解为去掉系数，所以 O(3n+4) 的时间复杂度为 O(n)
• 如果是多项式，只需要保留n的最高次项，O( 666n³ + 666n² + n )，这个复杂度里面的最高次项是n的3次方。因为随着n的增大，后面的项的增长远远不及n的最高次项大，所以低于这个次项的直接忽略不计，常数也忽略不计，简化后的时间复杂度为 O(n³)。

这里如果没有理解的话，暂停理解一下

接下来结合栗子，看一下常见的时间复杂度

1.3 常见时间复杂度

常数阶
对数阶
线性阶
线性对数阶
平方阶
立方阶
k次方阶
指数阶
随着问题规模 n 的不断增大，上述时间复杂度不断增大，算法执行效率越低。

从上往下时间复杂度不断增大

O(1)

上面说了，一般情况下，只要算法里没有循环和递归，就算有上万行代码，时间复杂度也是 O(1)，因为它的执行次数不会随着任何一个变量的增大而变长，比如下面这样

int main()
{
	int n = 0;
	if(n>0)
	{
		printf("开始吃苹果\n");
	}
		return 0;
}
1
2
3
4
5
6
7
8
9

O(n)

上面也介绍了 O(n)，总的来说 只有一层循环或者递归等，时间复杂度就是 O(n)，比如下面这样

int main()
{
	int n = 0;
	for (int i = 0; i < n; i++)
	{
		printf("我吃了1个苹果\n");
	}
	while (n > 0)
	{
		printf("我吃了1个苹果\n");
	}

	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

O(n^2)

比如嵌套循环，如下面这样的，里层循环执行 n 次，外层循环也执行 n 次，总执行次数就是 n x n，时间复杂度就是 n 的平方，也就是 O(n²)。假设 n 是 10，那么里面的就会打印 10 x 10 = 100 次

int main()
{
	int n = 0;
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
		{
			printf("我吃了1个苹果\n");
		}
	}
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12

还有这样的，总执行次数为 n + n²，上面说了，如果是多项式，取最高次项，所以这个时间复杂度也是 O(n²)

int main()
{
	int n = 0;
	for (int i = 0; i < n; i++)
	{
		printf("我吃了1个苹果\n");
	}
	for (int j = 0; j < n; j++)
	{
		for (int m = 0; m < n; m++)
		{
			printf("我吃了1个苹果\n");
		}
	}
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

O(logn)

举个栗子，这里有一包糖

这包糖里有16颗，每天吃这一包糖的一半，请问多少天吃完？

意思就是16不断除以2，除几次之后等于1？用代码表示

#include<stdio.h>
int main()
{
	int day = 0;
	int n = 16;
	while (n > 1)
	{
		n = n / 2;
		day++;
	}
	printf("%d", day);
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

循环次数的影响主要来源于 n/2 ，这个时间复杂度就是 O(logn) ，这个复杂度是怎么来的呢，别着急，继续看

再比如下面这样

int main() 
{
	int n = 16;
	for (int i = 0; i < n; i *= 2)
	{
		printf("一天\n");
	}
}
1
2
3
4
5
6
7
8

里面的打印执行了 4 次，循环次数主要影响来源于 i *= 2 ，这个时间复杂度也是 O(logn)

这个 O(logn) 是怎么来的，这里补充一个小学三年级数学的知识点，对数，我们看一张图

没有理解的话再看一下，理解一下规律

• 真数：就是真数，这道题里就是16
• 底数：就是值变化的规律，比如每次循环都是i*=2，这个乘以2就是规律。比如1,2,3,4,5…这样的值的话，底就是1，每个数变化的规律是+1嘛
• 对数：在这道题里可以理解成x2乘了多少次，这个次数
  仔细观察规律就会发现这道题里底数是 2，而我们要求的天数就是这个对数4，在对数里有一个表达公式

a^b = n 读作以a为底,b的对数=n，在这道题里我们知道a和n的值，也就是 2^b = 16 然后求 b

把这个公式转换一下的写法如下

log(a) n = b 在这道题里就是 log(2) 16 = ? 答案就是 4

公式是固定的，这个16不是固定的，是我们传进去的 n，所以可以理解为这道题就是求 log(2)n = ?

用时间复杂度表示就是 O(log(2)n)，由于时间复杂度需要去掉常数和系数，而log的底数跟系数是一样的，所以也需要去掉，所以最后这个正确的时间复杂度就是 O(logn)

emmmmm…

没有理解的话，可以暂停理解一下

其他还有一些时间复杂度，我由快到慢排列了一下，如下表顺序

随着数据量或者 n 的增大，时间复杂度也随之增加，也就是执行时间的增加，会越来越慢，越来越卡

总的来说时间复杂度就是执行时间增长的趋势，那么空间复杂度就是存储空间增长的趋势

什么是空间复杂度

其实与时间复杂度十分的相似

2.空间复杂度

2.1空间复杂度就是算法需要多少内存，占用了多少空间

2.2常用的空间复杂度有

O(1)、O(n)、O(n²)

O(1)

只要不会因为算法里的执行，导致额外的空间增长，就算是一万行，空间复杂度也是 O(1)，比如下面这样，时间复杂度也是 O(1)

int main()
{
	int i = 0;
	int n = i * 100;
	if (n==100)
	{
		printf("我吃了一个苹果\n");
	}
 return 0;
}
1
2
3
4
5
6
7
8
9
10

O(n)

比如下面这样，n 的数值越大，算法需要分配的空间就需要越多，来存储数组里的值，所以它的空间复杂度就是 O(n)，时间复杂度也是 O(n)

int main()
{
	int n = 0;
	int arr[] = {0};
	for (int i = 0; i < n; i++)
	{
		arr[i] = i;
	}
	return 0;
}
1
2
3
4
5
6
7
8
9
10

O(n^2)

O(n²) 这种空间复杂度一般出现在比如二维数组，或是矩阵的情况下

不用说，你肯定明白是啥情况啦

就是遍历生成类似这样格式的

#include<stdio.h>
int main()
{
	int arr[3][5] = { {1,2,3,4,5},{1,2,3,4,5},{1,2,3,4,5} };
	for(int i = 0;i<3;i++)
	{
		for (int j = 0; j < 5; j++)
		{
			printf("%d ", arr[i][j]);
		}
		printf("\n");
	}
	return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

总的来说，我们更加关注算法的时间按复杂度。而时间按复杂度与两个因素有关：算法中的嵌套循环层数 + 最内层循环的次数
一般来说，指数的时间复杂度是不被接受的，只能在 n 比较小的时候来用，其他的多项式时间复杂度是可以接受的。
有错误欢迎来评论区指正喔