时间复杂度与空间复杂度详解 —— 如何计算 + 如何表示_空间复杂度和时间复杂度

算法效率

算法效率分析分为两种：第一种是时间效率，第二种是空间效率。时间效率被称为时间复杂度，而空间效率被称作空间复杂度。

时间复杂度主要衡量的是一个算法的运行速度，而空间复杂度主要衡量一个算法所需要的额外空间。在计算机发展的早期，计算机的存储容量很小，所以对空间复杂度很是在乎。但是随着计算机行业的迅速发展，计算机的存储容量已经达到了很高的程度。所以我们如今已经不需要再特别关注一个算法的空间复杂度。这就是为什么我们大多时候听到的是时间复杂度，而很少听到空间复杂度的原因。

大O的渐进表示法规则

时间复杂度和空间复杂度一般都使用大O的渐进表示法进行表示，大O的渐进表示法规则如下：

1、所有常数都用常数1表示。
2、只保留最高阶项。
3、如果最高阶项存在且不是1，则去除与这个项的系数，得到的结果就是大O阶。

下面例子中使用大O的渐进表示法的时候会逐步分析。

时间复杂度

时间复杂度的定义：在计算机科学中，算法的时间复杂度是一个函数，它定量描述了该算法的运行时间。一个算法执行所耗费的时间，从理论上说，是不能算出来的，只有你把你的程序放在机器上跑起来，才能知道。但是我们需要每个算法都上机测试吗？是可以都上机测试，但是这很麻烦，所以才有了时间复杂度这个分析方式。一个算法所花费的时间与其中语句的执行次数成正比例，算法中的基本操作的执行次数，为算法的时间复杂度。

实例一：

//计算Func1的时间复杂度
void Func1(int N)
{
	int count = 0;
	for (int i = 0; i < 2 * N; i++)
	{
		for (int j = 0; j < 2 * N; j++)
		{
			count++;
		}
	}
	for (int k = 0; k < 2 * N; k++)
	{
		count++;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

Func1函数执行了一个嵌套的for循环（共执行了4 * N²次），又执行了一个单独的for循环（共执行了2 * N次），所以Func1函数的时间复杂度为：T(N) = 4 * N² + 2 * N 。

根据大O的渐进表示法，只保留最高阶项（即4 * N²），去除最高项的系数后（即N²），就是最终结果。所以，用大O的渐进表示法表示Func1函数的时间复杂度为：O(N²) 。

实例二：

//计算Func2的时间复杂度
void Func2(int N)
{
	int count = 0;
	for (int k = 0; k < 100; k++)
	{
		++count;
	}
	printf("%d\n", count);
}
1
2
3
4
5
6
7
8
9
10

Func2函数内部执行了一个for循环（共100次），Func2函数内语句的执行次数不会随着传入的变量N的改变而改变，即执行的次数为常数次。Func2函数的时间复杂度为T(N) = 100 。

根据大O的渐进表示法，所有的常数都用常数1来表示，所以，用大O的渐进表示法表示Func2函数的时间复杂度为：O(1) 。

拓：在刷题时看到题目要求时间复杂度为O(1)，并不是要求函数内部不能含有循环，而是要求循环的次数为常数次。

实例三：

//计算二分查找函数的时间复杂度
int BinarySearch(int* a, int N, int x)
{
	assert(a);
	int begin = 0;
	int end = N - 1;
	while (begin < end)
	{
		int mid = begin + ((end - begin) >> 1);
		if (x > a[mid])
			begin = mid + 1;
		else if (x < a[mid])
			end = mid - 1;
		else
			return mid;
	}
	return -1;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

计算二分查找函数的时间复杂度，我们需要对代码进行分析：我们用二分查找法查找数据时，查找一次后可以筛去一半的数据，经过一次次的筛选，最后会使得待查数据只剩一个，那么我们查找的次数就是while循环执行的次数。
因为数据个数为N，一次查找筛去一半的数据，即还剩N/2个数据，经过一次次的筛选，数据最后剩下1个，那么查找的次数可以理解为N除以若干个2，最后得1，那么while循环执行的次数就是N除以2的次数，我们只需计算N除以了多少次2最终等于1即可。

我们假设N除以了x个2，最终等于1，那么

最后，两边同时取2的对数，得while循环执行的次数，即x = logN 。所以，用大O的渐进表示法表示二分查找函数的时间复杂度为：O(logN) 。

注：表示时间和空间复杂度时，log表示以2为底的对数。

实例四：

//计算斐波那契函数的时间复杂度
int Fibonacci1(int N)
{
	if (N == 0||N == 1)
		return 1;
	else
		return Fibonacci1(N - 1) + Fibonacci1(N - 2);
}
1
2
3
4
5
6
7
8

我们知道，使用递归法求斐波那契数，当我们要求某一个斐波那契数时，需要知道他的前两个斐波那契数，然后相加得出。那么当我们要知道第N个斐波那契数时，递归的次数如下图：

因为右下角的递归函数会提前结束，所以图中三角形必定有一块是没有数据的，但是当N趋于无穷时，那缺省的一小块便可以忽略不计，这时总共调用斐波那契函数的次数为：

这是一个等比数列的求和，最后得出结果为：2^N - 1 。
保留最高阶项后，用大O的渐进表示法表示斐波那契函数的时间复杂度为：O(2^N) 。

注：递归算法的时间复杂度 = 递归的次数 * 每次递归函数中的次数。

空间复杂度

空间复杂度是对一个算法在运行过程中临时占用存储空间大小的量度。空间复杂度不是程序占用了多少字节的空间，因为这个也没太大意义，所以空间复杂度算的是变量的个数。空间复杂度计算规则基本跟时间复杂度类似，也使用大O渐进表示法。

实例一：

//计算冒泡排序函数的空间复杂度
void BubbleSort(int* a, int N)
{
	assert(a);
	for (int i = 0; i < N; i++)
	{
		int exchange = 0;
		for (int j = 0; j < N - 1 - i; j++)
		{
			if (a[j]>a[j + 1])
			{
				int tmp = a[j];
				a[j] = a[j + 1];
				a[j + 1] = tmp;
				exchange = 1;
			}
		}
		if (exchange == 0)
			break;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

冒泡排序函数中使用了常数个额外空间（即常数个变量），所以用大O的渐进表示法表示冒泡排序函数的空间复杂度为O(1) 。

实例二：

//计算阶乘递归函数的空间复杂度
long long Factorial(size_t N)
{
	return N < 2 ? N : Factorial(N - 1)*N;
}
1
2
3
4
5

阶乘递归函数会依次调用Factorial(N),Factorial(N-1),…,Factorial(2),Factorial(1)，开辟了N个空间，所以空间复杂度为O(N) 。

注：递归算法的空间复杂度通常是递归的深度（即递归多少层）。