数据结构初阶(C语言）-复杂度的介绍

       在学习顺序表之前，我们需要先了解下什么是复杂度：

一，复杂度的概念

       我们在进行代码的写作时，通常需要用到许多算法，而这些算法又有优劣之分，区分算法的优劣则是通过算法的时间复杂度和空间复杂度来决定。

       时间复杂度主要衡量⼀个算法的运行快慢，而空间复杂度主要衡量一个算法运行所需要的额外空间。 在计算机发展的早期，计算机的存储容量很小。所以对空间复杂度很是在乎。但是经过计算机行业的迅速发展，计算机的存储容量已经达到了很高的程度。所以我们如今已经不需要再特别关注一个算法的空间复杂度。

二，时间复杂度

2.1定义

       在计算机科学中，算法的时间复杂度是⼀个函数式T(N)，它定量描述了该算法的运行时间。时 间复杂度是衡量程序的时间效率，那么为什么不去计算程序的运行时间呢？

1. 因为程序运行时间和编译环境和运行机器的配置都有关系，比如同⼀个算法程序，用⼀个老编译 器进行编译和新编译器编译，在同样机器下运行时间不同。

2. 同⼀个算法程序，用⼀个老低配置机器和新高配置机器，运行时间也不同。

3. 并且时间只能程序写好后测试，不能写程序前通过理论思想计算评估。

而这里我们所说的T(N)即为程序所执行的次数，下面我们来看一个例子：
 

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;
	}
}

       可以看到，这条语句中，++count这条语句被执行的次数为N*N+2*N+10，即T（N）= N*N+2*N+10。

       但在实际情况中，对于程序的执行次数的计算非常的麻烦，我们通常不使用以上的方式来计算时间复杂度，而是用粗略值O(N)来估算，使用的是大O的渐进表示法。

2.2大O的渐进表示法

1. 时间（空间）复杂度函数式T(N)中，只保留最高阶项，去掉那些低阶项，因为当N不断变大时，低阶项对结果影响越来越小，当N无穷大时，就可以忽略不计了。

2. 如果最高阶项存在且不是1，则去除这个项目的常数系数，因为当N不断变大，这个系数对结果影响越来越小，当N无穷大时，就可以忽略不计了。

3. T(N)中如果没有N相关的项目，只有常数项，用常数1取代所有加法常数。

所以我们可以计算出上面的例子的时间复杂度为O(N*N)。（平方打不出来求放过）

2.3大O的渐进法表示时间复杂度的几道例题

2.3.1示例一

首先是我们之前学习c语言时常见的冒泡排序:
 

void bubble_sort(int* arr, size_t sz)
{
	assert(arr);
	int exchange = 0;
	int a = 0;
	for (int i = 0; i < sz; i++)
	{
		for (int j = 0; j < sz - i - 1; j++)
		{
			if (arr[j] > arr[j + 1])
			{
				a = arr[j];
				arr[j] = arr[j + 1];
				arr[j + 1] = a;
				exchange = 1;
			}
		}
		if (exchange == 0)
			break;
	}
}

       由于定义常值的代码只有一两条（类似于int exchange = 0），所以这里我们只看循环部分即可推出该程序的时间复杂度。

       首先，最理想的情况即是数组本身就为顺序排列的话，那我们的时间复杂度为O(N),当最坏的情况下数组为降序，这时拍的次数最多为1/2（N*N + N),根据上面的渐进表示法我们可以得知，此时的时间复杂度为O(N*N)。所以此程序的时间复杂度为O(N*N)。由此可见我们程序的时间复杂度其实是由最坏的情况所决定的。

下面的例题供大家熟悉这套规则的同时，了解我们之后常见的时间复杂度的计算方式：

2.3.2示例二

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

他的执行次数为2N+10，所以我们根据渐进表示法的第二条准则即可得出其时间复杂度为O(N)。

2.3.3示例三

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);
}

这里我们可以知道他的程序执行次数为M+N次，所以我们的时间复杂度对于此题来说为O(M+N)。

2.3.4示例四

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

这里程序的执行次数为常数，所以我们的时间复杂度为O(1)。

2.3.5示例五

void func5(int n)
{
	int cnt = 1;
	while (cnt < n)
	{
		cnt *= 2;
	}
}

       这里我们的执行次数为logn(以2为底)，所以我们的时间复杂度为O(logN);但实际上，我们平时写的时候可以将底数忽略，由于当n趋于正无穷的时候，底数对其的影响就微乎其微了，我们可以通过中学时期学过的换底公式得出这个结论，这里不详细介绍换底证明的步骤，如果有兴趣可以自行下去推导。

三，空间复杂度

3.1定义

       1.空间复杂度也是一个数学表达式，是对一个算法在运行过程中因为算法的需要额外临时开辟的空间。

       2.空间复杂度不是程序占用了多少bytes的空间，因为常规情况每个对象大小差异不会很大，所以空间复杂度算的是变量的个数。

       3.空间复杂度计算规则基本跟实践复杂度类似，也使用大O渐进表示法。

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

       所以我们可以知道这于时间复杂度的计算相差不大，只是把程序执行的次数改变成了程序额外开辟的空间来进行计算。

3.2示例

3.2.1冒泡排序

​
void bubble_sort(int* arr, size_t sz)
{
	assert(arr);
	int exchange = 0;
	int a = 0;
	for (int i = 0; i < sz; i++)
	{
		for (int j = 0; j < sz - i - 1; j++)
		{
			if (arr[j] > arr[j + 1])
			{
				a = arr[j];
				arr[j] = arr[j + 1];
				arr[j + 1] = a;
				exchange = 1;
			}
		}
		if (exchange == 0)
			break;
	}
}
 
​

函数栈帧在编译期间已经确定好了，只需要关注函数在运行时额外申请的 空间。 BubbleSort额外申请的空间有 exchange等有限个局部变量，使用了常数个额外空间 因此空间复杂度为O(1)。

3.2.2示例二

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

Fac递归调用了N次，额外开辟了N个函数栈帧，每个栈帧使用了常数个空间因此空间复杂度为： O(N)。

四，常见复杂度对比

复杂度的介绍就到这里已经够我们目前的使用的了，我们下篇文章见。