【数据结构】算法的时间复杂度和空间复杂度

写在前面

在我们学习数据结构之前，我们肯定就听过某某大神说，我的排序算法的时间复杂度只需要O(logN)，空间复杂度只需要O(1)…听的好唬人，但是实际也真牛。那其中时间复杂度和空间复杂度是什么呢？不才这篇笔记就深入讲解。

文章目录

写在前面
一、算法效率
- 1.1 如何衡量一个算法的好坏
- 1.2、算法的复杂度
二、时间复杂度
- 2.1 时间复杂度的概念
- 2.2、大O渐进表示法
- 2.3、常见时间复杂度计算举例
三、空间复杂度
四、常见复杂度

一、算法效率

1.1 如何衡量一个算法的好坏

是代码干净、简洁和明了就是好算法吗？
举个栗子：计算斐波拉系数

long long Fib(int N)
{
	if (N < 3)
		return 1;
	return Fib(N - 1) + Fib(N - 2);
}

我们写了上面递归的方法来计算，代码干净、简洁和明了，那他是一个好算法吗？结果显而易见，差的不行，如果我们计算第30位的斐波拉系数，大约需要进行10亿次计算，这非常恐怖。也仅仅是第30位。

1.2、算法的复杂度

算法在编写成可执行程序后，运行时需要耗费时间资源和空间(内存)资源。因此衡量一个算法的好坏，一般是从时间和空间两个维度来衡量的，即时间复杂度和空间复杂度。
时间复杂度主要衡量一个算法的运行快慢，而空间复杂度主要衡量一个算法运行所需要的额外空间。 在计算机发展的早期，计算机的存储容量很小。所以对空间复杂度很是在乎。但是经过计算机行业的迅速发展，计算机的存储容量已经达到了很高的程度。所以我们如今已经不需要再特别关注一个算法的空间复杂度。

二、时间复杂度

2.1 时间复杂度的概念

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

简单的说就是这个程序需要最长循环运行多少次。

void Func1(int N)
{
	int count = 0;
	for (int i = 0; i < N; ++i)//第一次循环
	{
		for (int j = 0; j < N; ++j)
		{
			++count;
		}
	}
	for (int k = 0; k < 2 * N; ++k)//第二次循环
	{
		++count;
	}
	int M = 10;
	while (M--)//第三次循环
	{
		++count;
	}
}

在第一次N次循环中，又内嵌了一层N次循环，那此时第一次循环从开始到结束要运行（N*N）次。
在第二次循环中，他的循环次数是2*N次循环，即要运行2*N次
在第三次循环中，M的初始值是：10，每次循环渐渐，即最终会循环10次。

统合上述三次循环，我们就可以的出，运行一次Func1函数需要运行多少次。
Func1 执行的基本操作次数：
在这里插入图片描述
实际中我们计算时间复杂度时，我们其实并不一定要计算精确的执行次数，而只需要大概执行次数，那么这里我们使用大O的渐进表示法。

2.2、大O渐进表示法

大O符号（Big O notation）：是用于描述函数渐进行为的数学符号。

推导大O阶方法：

用常数1取代运行时间中的所有加法常数。
在修改后的运行次数函数中，只保留最高阶项。
如果最高阶项存在且不是1，则去除与这个项目相乘的常数。得到的结果就是大O阶。

使用大O的渐进表示法以后，Func1的时间复杂度为：O(n²)

因为是渐进表示法，保留最高位指数位即可，因为若n为无穷时候，在极值运算中，我们可以认为：
在这里插入图片描述
虽然在数学中上面式子依旧是无穷大，不是无穷大*无穷大，但是为了具象表示大O的渐进表示法选择举例上图。这样方便理解。
通过上面我们会发现大O的渐进表示法去掉了那些对结果影响不大的项，简洁明了的表示出了执行次数。

在实际中一般情况关注的是算法的最坏运行情况

2.3、常见时间复杂度计算举例

通过上面列举的推导大O阶方法，来计算一下下面的例子。

栗子1：

void Func2(int N)
{
	int count = 0;
	for (int k = 0; k < 2 * N; ++k)
	{
		++count;
	}
	int M = 10;
	while (M--)
	{
		++count;
	}
	printf("%d\n", count);
}

先找出循环次数最多的循环，上例中有两个循环，一个是2*N次循环，一个是10次循环
那么上例中为：O(N)。因为相乘的常熟可以被去除。

栗子2：

void Func3(int N, int M)
{
	int count = 0;
	for (int k = 0; k < M; ++k)
	{
		++count;
	}
	for (int k = 0; k < N; ++k)
	{
		++count;
	}
	printf("%d\n", count);
}

先找出循环次数最多的循环，上例中有两个循环，一个是N次循环，一个是M次循环
由于两个都是同次未知数，所以为：O(N+M)。

栗子3：

void Func4(int N)
{
	int count = 0;
	for (int k = 0; k < 100; ++k)
	{
		++count;
	}
	printf("%d\n", count);
}

先找出循环次数最多的循环，上例中只有一个循环，是一个常数次循环。
那么他的时间复杂度就为：O(1)。

栗子4：

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 (a[mid] < x)
			begin = mid + 1;
		else if (a[mid] > x)
			end = mid;
		else
			return mid;
	}
	return -1;
}

上面代码是个二分查找。每次运行都会去除一半的结果。
最好的结果是O(1)，即我们第常数次就找到了。
最坏的结果，是每次折半，直到最后成为一个值的时候才找到。此时我们有N个值，每运行一次二分查找都对 N/2，
即最坏的结果： N/2 /2 /2…/2 = 1 => N = 1*2 *2 *2…*2。现在我们设进行了x次二分查找，可以得出：N = 2^x。那x次就等于：log₂^N。时间复杂度就为：O(log₂^N)。
在数据结构的时间复杂度和空间复杂度中，书写 log₂^N 这样的格式比较困难，也比较麻烦，所以我们统一把 log 以2为底(log₂ )的编写成 log，不同于数学中的 lg 才表示2为底。
在上面栗子中，我们取最坏的结果，二分查找的时间复杂度：O(logN)。

栗子5：

//计算斐波那契递归Fib的时间复杂度？
long long Fib(size_t N)
{
if(N < 3)
return 1;
return Fib(N-1) + Fib(N-2);
}

我们可以画出树形图来观察（如下图）
可以观察到整体而言，递归的次数等比数列的和，虽然有些会提前结束，但是对整体而言可以忽略不计。根据等比数列和公式可以得出递归次数为:(2^N-2）
时间复杂度为：O(2^N)。

三、空间复杂度

空间复杂度也是一个数学表达式，是对一个算法在运行过程中临时占用存储空间大小的量度。

空间复杂度不是程序占用了多少bytes的空间，因为这个也没太大意义，所以空间复杂度算的是变量的个数。空间复杂度计算规则基本跟时间复杂度类似，也使用大O渐进表示法。

注意：函数运行时所需要的栈空间(存储参数、局部变量、一些寄存器信息等)在编译期间已经确定好了， 因此 空间复杂度主要通过函数在运行时候显式申请的额外空间来确定。

栗子1：

long long* Fibonacci(size_t n)
{
	if (n == 0)
		return NULL;
	long long* fibArray = (long long*)malloc((n + 1) * sizeof(long long));
	fibArray[0] = 0;
	fibArray[1] = 1;
	for (int i = 2; i <= n; ++i)
	{
		fibArray[i] = fibArray[i - 1] + fibArray[i - 2];
	}
	return fibArray;
}

动态开辟了n+1个long long个字节空间，此时空间复杂度为O(n)。

栗子2：

void BubbleSort(int* a, int n)
{
	assert(a);
	for (size_t end = n; end > 0; --end)
	{
		int exchange = 0;
		for (size_t i = 1; i < end; ++i)
		{
			if (a[i - 1] > a[i])
			{
				Swap(&a[i - 1], &a[i]);
				exchange = 1;
			}
		}
		if (exchange == 0)
			break;
	}
}

在for循环中只是调用了变量，没有在循环内部创建变量，所以空间复杂度为：O(1)。

栗子3：

//计算斐波那契递归Fib的时间复杂度？
long long Fib(size_t N)
{
if(N < 3)
return 1;
return Fib(N-1) + Fib(N-2);
}

递归调用了N次，开辟了N个栈帧，每个栈帧使用了常数个空间。空间复杂度为O(N)

四、常见复杂度

表达式	大O表示法	阶
5201314	O(1)	常数阶
3n+4	O(n)	线性阶
3n²+4n+5	O(n²)	平方阶
3log(2)n+4	O(logn)	对数阶
2n+3nlog(2)n+14	O(nlogn)	nlogn阶
n³+2n²+4n+6	O(n³)	立方阶
2^n	O(2ⁿ)	指数阶