数据结构·复杂度

1 时间复杂度

2 大O渐进表示法

举例子（计算时间复杂度为多少）

3 空间复杂度

前言：复杂度分为时间复杂度和空间复杂度，两者是不同维度的，所以比较不会放在一起比较，但是时间复杂度和空间复杂度是用来衡量一个算法是否好坏的标准，时间复杂度用来描述算法运行的时间快慢，空间复杂度用来衡量一个算法所需要的额外空间。最初的计算机时代计算机的存储量很小，所以额外注重空间复杂度，随着发展，计算机的存储已经不是让人担心的点了，所以更为注重时间复杂度。

1 时间复杂度

时间复杂度的定义上可以认为使劲按复杂度是一个函数，定量的描述了算法所需要的时间，但是理论上来说，运行的时间是要上机测试才能测试出来的，实际测试就会花很多时间，所以有了时间复杂度这个分析方式分析算法中执行的基本操作的次数，认定为时间复杂度。

int main()
{
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < N; j++)
		{
			//测试语句
		}
	}
	for (int i = 0; i < N; i++)
	{
		//测试语句
	}
	int M = 10;
	while (M--)
	{
		//测试语句
	}
	return 0;
}

这段代码的时间复杂度是？

两个嵌套的for循环，也就是执行了N^2次，再来一个for循环，执行次数为N，最后while收尾，执行次数为10,所以时间复杂度的函数为F(N) = N^2 + N + 10，随着N的增大，式子的值会大到无法想象，这都得益于N^2，那么整个式子的决定性因素是N^2，所以我们就认为时间复杂度是N^2。

这种估算的方法被称为大O渐进表示法，只取式子中的决定性因素。

2 大O渐进表示法

计算时间复杂度的时候我们通常采用大O渐进表示法，推导大O阶的表示方法为：

1、用常数1取代运行时间中的所有加法常数。

2、在修改后的运行次数函数中，只保留最高阶项。

3、如果最高阶项存在且不是1，则去除与这个项目相乘的常数。得到的结果就是大O阶。

这里其实完全可以类比高中的数学函数，y = x，x可以是2x也可以是3x，这就是为什么舍弃常数的原因，x和2x是没有区别的。

那么什么是加法常数呢？只要没有循环或者递归，我们都可以认为执行次数为O(1)，哪怕是写了一万行代码。

执行程序的时候会存在最好情况最坏情况以及平均情况（期望值），一般计算时间复杂度的时候都是计算的最坏情况，所以像冒泡排序，运气好点，时间复杂度就是O(1),运气不好就是O(N^2)了。

举例子（计算时间复杂度为多少）

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

第一个for循环的执行次数为2 * N次，第二个while循环执行次数为10次，那么函数表达式就是2*N + 10,根据大O表示法，时间复杂度为O(N)。

void Fun3(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 ", count);
}

第一个for循环执行次数为M次，第二个for循环的执行次数为N次，那么函数表达式就是O(M + N)，

那么最后结果视结果而定，如果M远大于N，那么时间复杂度就是O(M)，那么N >> M同理可得。

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

根据第一个for循环的循环条件，循环次数为100次，是常数，所以时间复杂度就是O(1)。

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

冒泡排序严格意义上来说不是标准的O(N^2)，因为它的执行次数在随着程序的执行是逐渐减少的，最开始两两比较的次数是N- 1，每趟下来，就会确定一个数据的位置，所以两两比较的次数每次都会减去1，那么if这个语句执行的次数就是N - 1 N - 2……1,利用高中的等差数列的知识，可以得到时间复杂度的函数是F(N) = (N - 1) * (N - 1 + 1) / 2，根据大O表示法，可得得出复杂度为O(N^2)。

int BinarySeatch(int* a, int n, int x)
{
	assert(a);
	int begin = 0;
	int end = n - 1;
	//[begin,end]是查找区间
	while (begin <= end)
	{
		int mid = begin + ((end - begin) >> 1);
		if (a[mid] < x)
			begin = mid + 1;
		else if (a[mid] > x)
			end = mid - 1;
		else
			return mid;
	}
	return -1;
}

这是一个典型的二分查，时间复杂度为直接看是看不出来的，所以有的代码计算时间复杂度是要结合画图的：

我们讨论最坏情况，二分查找的本质就是不断的缩小区间，一半一半的缩短，那么最开始有N个值，就有N/2/2/2/2/2/2……= 1，那么执行次数就是找的次数就是除以2的次数，计算方式就是

N = 2^x，x是执行的次数，我们求的就是x的值，那么利用高中的换底公式，我们可以得到

x是以2为底，N的对数，而因为对数不太好写，除非使用专业的公式编辑器，所以默认规定LogN,表示的就是以2为底，N的对数，如果有其他底数，就照常写。

long long Fac(size_t N)
{
	if (0 == N)
	{
		return 1;
	}
	return Fac(N - 1) * N;
}

计算阶乘递归的时间复杂度，递归，会多次开辟函数栈帧，所以一次递归，就会开辟一个函数栈帧，执行次数是1，那么递归n次，总执行次数就是N，所以时间复杂度就是O(N)。

引申：

long long Fac(size_t N)
{
	if (0 == N)
		return 1;
	for (int i = 0; i < N; i++)
	{
		//测试语句
	}
	return Fac(N - 1) * N;
}

递归函数里面加了一个for循环，时间复杂度是多少呢？

不加for循环之前，每个函数的时间复杂度是O(1)，开辟了N个函数，那么复杂度就是O(N)，但是现在每个函数的时间复杂度就是O(N)了，因为每个子函数里面都有一个for循环，所以N个O(N)的函数放在一起，时间复杂度就是O(N ^ 2)。

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

我们知道递归用来计算斐波那契数列是非常不划算的，因为重复计算的次数太多了，是次方级别的重复：

像这样，函数执行的次数是从2的0次方开始，一直到2的N次方，那么利用高中的等比数列的公式，可以得出时间复杂度为函数为F(N) = 2^N - 1,所以时间复杂度就是O(2 ^ N)。

这是非常恐怖的，所以计算斐波那契数列的话还是使用迭代吧！

3 空间复杂度

时间复杂度可以理解为语句的执行次数，空间复杂度可以理解额外开辟的空间，也是采用的大O渐进表示法。当然，空间复杂度不是多少字节，意义不大，因为当前的计算机存储足够大，所以空间复杂度表示的是变量的个数，需要注意的是：函数需要的栈空间在编译期间就已经确定好了，所以计算空间复杂度靠的是程序运行时候显示出来的额外空间。

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

计算冒泡排序的空间复杂度：

这个函数里面有变量，但是是有限个的，如end flag i ，并没有额外开辟空间，所以空间复杂度是O(1)，毕竟是没有额外申请空间的。

那么递归计算斐波那契数列的空间复杂度是多少呢？

在此之前我们先看这串代码：

void Test1()
{
	int a = 10;
	printf("%p\n", &a);
}
void Test2()
{
	int b = 10;
	printf("%p\n", &b);
}
int main()
{
	Test1();
	Test2();
	return 0;
}

试问运行结果是不是一样的？有人就会问了，不同函数存的地址肯定不是一样的啊，一般情况是这样的，但是如果两个函数连续调用，并且函数的功能一样，对空间的需求是一样的，那么内存在栈上的空间分配就不会额外开辟空间，也就是说一个函数调用完后，另一个函数就会接着使用这块空间，所以地址是一样的。

那么类比到斐波那契数列的重复计算里面：

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

实际上上开辟的空间都是为了计算函数Fib(N)到Fib(1)的，函数的功能是一样，对空间的需求也是一样的，所以重复计算的时候就不会单独开辟空间，所以需要计算的，都用了开辟的Fib(N)到Fib(1)的空间，那么空间复杂度就是O(N)。

感谢阅读！