【数据结构】时间复杂度

一、算法的复杂度

二、时间复杂度

2.1 时间复杂度的概念

2.2 大O渐进表示法

2.3 计算时间复杂度步骤

三、常见时间复杂度举例

3.1 ❥ 常数阶

3.2 ❥ 线性阶

3.3 ❥ 平方阶

3.4 ❥ 对数阶

3.5 ❥ 指数阶

3.6 ❥ 多个未知数的复杂度

四、最好，最坏，平均情况

五、时间复杂度优劣对比

一、算法的复杂度

如何衡量一个算法的好坏呢？

是从时间效率和空间效率这两个方面进行衡量。

因为算法在编写成可执行程序后，运行需要耗费时间资源和空间（内存）资源。因此衡量一个算法的好坏，一般从时间和空间这两个维度来衡量。即时间复杂度和空间复杂度。

时间复杂度主要衡量一个算法的运行快慢，而空间复杂度主要衡量一个算法运行所需要的额外空间。在计算机发展的早期，计算机的存储容量很小，所以对空间的复杂度很是在乎。现如今计算机行业迅速发展，计算机存储容量很高，因此就不再特别关注算法的空间效率，通常更加注重时间效率。

注意：

不能认为时间复杂度就比空间复杂度重要，在某些场景下空间复杂度反而比时间复杂度重要，在程序中我们需要综合考虑让时间和空间的消耗达到一个平衡点。

二、时间复杂度

2.1 时间复杂度的概念

在计算机科学中，算法的时间复杂度是一个函数，它定性描述了该算法的运行时间。

一个算法所花费的时间与其中语句的执行次数成正比例，算法中的基本操作的执行次数，为算法的时间复杂度。

例题：

int func(int n)
{
	for (int i = 0; i < n; i++)
	{
		printf("haha\n");
	}
	return 0;
}

以上代码共执行了多少次呢？

分析如下：

作为衡量代码速度的依据，当代码较多的时候，一条一条地去数就比较麻烦，而且在函数调用函数的时候，运行起来也比较麻烦。

所以，算法一般使用估算值来衡量代码的执行速度，这里用大O的渐进表示法来表示时间复杂度。

2.2 大O渐进表示法

大O渐进表示法：用来粗略度量算法的效率。

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

推导大O阶方法：

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

简而言之，去掉常数项，低次幂，最高次的系数就是该函数的时间复杂度。

本质：计算算法时间复杂度（次数）属于哪个量级（level）。

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

2.3 计算时间复杂度步骤

1、找出算法中的基本语句。

算法中执行次数最多的那条语句就是基本语句，通常是最内层循环的循环体。

2、计算基本语句的执行次数的数量级。

　　计算基本语句执行次数的数量级，这就意味着只要保证基本语句执行次数的函数中的最高次幂正确即可。

3、用O记号表示算法的时间性能。

　　将基本语句执行次数的数量级放入O记号中

三、常见时间复杂度举例

3.1 ❥ 常数阶

常数阶的时间复杂度是：O(1）

说明算法的执行时间是常量，不随输入规模的增加而增加。

例题：

//计算Print的时间复杂度
void Print()
{
	int i = 0;
	for (i = 0; i < 100; i++)
	{
		printf("lala\n");//层次最深的语句
	}
	printf("haha\n");
}

可知，最深的打印语句执行了100次，也就是常数次。用O(1)表示。

注意：

其实printf("haha\n");也算一次运算，但是它整体影响不大，（因为cpu运行速度超级快）所以可以忽略这些细枝末节，不用计算。

易错提醒：

O(1)是代表的是常数次，不是1次。
只要是常数，都用O(1)进行表示。

3.2 ❥ 线性阶

线性阶的时间复杂度是：O(N）

例题：

// 计算阶乘递归Fac的时间复杂度
long long Fac(int N)
{
	if (0 == N)
		return 1;
	return Fac(N - 1) * N;
}

分析如下：

由此可知：

递归的时间复杂度：所有递归调用的次数累加。

3.3 ❥ 平方阶

平方阶的时间复杂度是：O(N^2）

例题：

// 计算阶乘递归Fac的时间复杂度
long long Fac(int N)
{
	if (0 == N)
		return 1;

	for (int i = 0; i < n; ++i)
	{
		//...
	}

	return Fac(N - 1) * N;
}

分析如下：

由于计算的是算法时间复杂度（次数）属于哪个量级，所以只需要看决定性的项，也就是最高阶的项，不需要关注那些细枝末节。

所以(n^2+n)/2属于平方阶，忽略它的最高项的系数以及低次项，因此算出来的该递归函数的时间复杂度为O(N^2)。

3.4 ❥ 对数阶

对数阶的时间复杂度是：O(logN）

例题：

// 计算BinarySearch的时间复杂度
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 - 1;
		else
			return mid;
	}
	return -1;
}

分析如下：

3.5 ❥ 指数阶

指数阶的时间复杂度是：O(2^N）

例题：

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

分析如下：

3.6 ❥ 多个未知数的复杂度

一个时间复杂度里面也不一定只有一个未知数。

那遇见存在多个未知数的情况，我们该如何写代码呢？

我们举例来说明，看如下代码：

// 计算Func3的时间复杂度
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);
}

分析如下：

该代码的时间复杂度为：O(M+N）

也可以写成O(max(M，N))

如果有说明M和N的关系的，写成下面的形式这样更好