算法的效率：算法的时间复杂度和空间复杂度

【本节目标】

• 1.算法效率
• 2.时间复杂度
• 3.空间复杂度
• 4.常见时间复杂度以及复杂oj练习

1、算法效率

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

如何衡量一个算法的好坏呢？比如斐波那契数列：

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

斐波那契数列的递归实现方式非常简洁，但简洁一定好吗？那该如何衡量其好与坏呢？

1.2、算法的复杂度

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

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

2、时间复杂度

2.1、时间复杂度和概念

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

算法中的基本操作的执行次数，为算法的时间复杂度。

即：找到某条语句与问题规模N之间的数学表达式，就是算出了该算法的时间复杂度。

那下面举个例子：

//请计算一下Func1中++count语句总共运行了多少次？
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 = 0;
	while (M--)
	{
		++count;
	}
	printf("%d\n", count);
}

我们可以得出：时间复杂度的函数式：F(N) = N*N+2*N+10。

那这个时候我们赋予N具体的值：

• N=10时，F(N)=130
• N=100时，F(N)=10210
• N=1000时，F(N)=1002010

我们想一下，当N越大，其实F(N)的值，就和__N*N__这个式子关系越大，后面的__2*N+10__所带来的值对整体的F(N)的值影响不大。

实际中我们计算时间复杂度时，我们其实并不是要计算精确的执行次数，而是只需要大概执行次数，那么这里我们使用__大O的渐进表示法。__

2.2、大O的渐进表示法

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

推导大O阶方法：

1、用常数1取代运行时间中的所有加法常数。（只要有常数项就用1去取代）

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

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

使用大O阶的渐进表示法以后，Func1的时间复杂度为：O(N^2)。

• N=10，F(N)=100。
• N=100，F(N)=10000。
• N=1000，F(N)=1000000。

通过上面我们会发现大O的渐进表示法去掉了那些对结果影响不大的项，简洁明了的表示除了执行次数。

另外有些算法的时间复杂度最好，平均和最坏的情况：

• 最坏情况：任意输出规模的最大运行次数（上界）。
• 平均情况：任意输出规模的期望运行次数。
• 最好情况：任意输出规模的最小运行次数（下界）。

例如：在一个长度的N的数组中搜索一个数据x。

• 最坏情况：N次找到。
• 平均情况：N/2找到。
• 最好情况：1次找到。

在实际中一般情况关注的是算法的最坏运行情况，所以数组中搜索数据时间复杂度为O(N)。

2.3、常见时间复杂度计算练习

下面我们多看几个案例，来练习一下大O阶：

2.3.1、单层循环时间复杂度计算

案例1：

//计算Func2的时间复杂度
void Func2(int N)
{
	int count = 0;

	for (int k = 0; k < 2 * N; ++k)
	{
		++count;
	}

	int M = 0;
	while (M--)
	{
		++count;
	}
	printf("%d\n", count);
}

大O阶表示法：O(N) = N

分析：F(N) = 2*N+10

随着N的数值越来越大，+10的这一项对F(N)的值影响不大，所以忽略。

然后高阶项是2*N，N的系数不是1，所以把N前面的系数省略。

所以用大O阶法表示就是O(N) = N

2.3.2、嵌套循环时间复杂度计算

//请计算一下Func1中++count语句总共运行了多少次？
void Func1(int N)
{
	int count = 0;
	for (int i = 0; i < N; ++i)
	{
		for (int j = 0; j < N; ++j)
		{
			++count;
		}
	}
}

大O阶表示法：O(N) = N^2

2.3.3、双重循环时间复杂度计算

案例2：

//计算Func3的时间复杂度
void Func3(int N,int M)
{
	int count = 0;
	for (int i = 0; i < N; ++i)
	{
		++count;
	}

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

大O阶表示法：分情况

分析：

1、如果没有说明M和N的大小关系：

• O(M+N)

2、如果说明了M和N的大小关系：

• M远远大于N：O(M)
• N远远大于M：O(N)
• M差不多相等于N：O(M)或O(N)

2.3.4、常数循环的时间复杂度

案例3：

//计算Func4的时间复杂度
void Func4(int N,int M)
{
	int count = 0;
	for (int k = 0; k < 100; ++k)
	{
		++count;
	}
	printf("%d\n", count);
}
大O阶表示法：O(N) = O(1)

分析：由上面的大O阶规则：__用常数1取代运行时间中的所有加法常数。（只要有常数项就用1去取代）__来说。

此大O阶表示：O(1)。

【扩展】：在做题时，题目会要求：把这个题的时间复杂度优化到O(1)。那这意思并不是只能运算一次。而是说需要运算常数次。

2.3.5、strchar的时间复杂度

案例4：

//计算strchar的时间复杂度
//【补充】strchar是个库函数，用于查找，搜索相匹配的字符串
const char* strchar (const char* str,int character);

比如现在有个字符串："hello world"

大O阶表示法：分情况

分如下几种情况：

• 假设查找的是h，大O阶表示法：O(1)。
• 假设查找的是w，大O阶表示法：O(N/2)。
• 假设查找的是d，大O阶表示法：O(N)。

那在实际情况中，当一个算法随着输入的不同，时间复杂度不同，时间复杂度一律做悲观预期处理，看最坏的情况，所以上面的大O阶表示法就是O(N)。

2.3.6、冒泡排序的时间复杂度的计算

案例5：

冒泡排序的核心思想是：相邻两元素之间进行比较。

如果有N个元素，需要比较N-1次，第一次，比较N-1次，第二次比较N-2次…最后一次比较1次即可。

所以是个等差数列，[项数*(a1+an)] / 2，所以就等于[n*(n-1)]/2。

所以O(N) = N^2。

2.3.7、二分查找时间复杂度的计算

在学习C语言中，学习了二分查找算法，它的底层数学知识就是log2 N。

比如有8=2**3个数据，进行二分查找。

转化为数学知识就是：log2 8 = 3。所以说悲观期望，二分查找最多执行3次。

所以说使用大O阶法表示，也分三种情况：

• 最坏情况：O(log2 N)次找到。
• 平均情况：O((log2 N)/2)找到。
• 最好情况：O(1)次找到。

所以综上，使用悲观期望，二分查找的时间复杂度大O阶法表示为O(log2 N)。

这里补充一点，二分查找是个很nb的算法，数据越多它越nb，但是二分查找有个缺陷就是，只能针对有序数列进行查找，如果想要使用二分，前面是需要先排序，但是排序是很消耗性能的。

所以说以后要学：

• 树—>二叉树—>搜索二叉树—>平衡二叉树—>AVL Tree/RB Tree。

• 哈希表。

• B树系列。

2.3.8、阶乘的时间复杂度

实例7：

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

分析：Fac一共调用了N次。

所以大O阶表示法：O(N)。

2.3.9、斐波那契的时间复杂度

实例8：

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

大O阶表示法：O(N) = 2^N

递归算法：递归次数*每次递归调用的次数。

• 递归次数：每一次只执行一次Fib，所以是O(1)。
• 每次递归调用的次数：计算Fib(N)，需要调用Fib(N-1)+FIB(N-2)。就类似的这个过程。

如下图分析：

可以发现这每一行的规律，它们是等比数列，然后减去省略的一部分x。

所以Fib(N) = 2⁰⁺²1+2^2+…+2(N-1)-x。

等比数列之和为：a1(1-q^n)/(1-q)

所以2⁰⁺²1+2^2+…+2(N-1) = (2^N) - 1。

又因为当N无限大时，减去x相当于没减。

所以最终Fib(N) = (2^N) - 1。

那使用大O阶表示为：O(N) = 2^N。

3、空间复杂度计算

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

空间复杂度不是程序占用了多少bytes的空间，因为这个也没多大意义，所以__空间复杂度算的是变量的个数。__

空间复杂度计算规则基本跟时间复杂度类似，也是用__大O渐进表示法。__

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

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

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

//空间复杂度：O(1)。

分析：这里就看额外创建几个变量即可。

• end变量是额外创建的。
• i变量是额外创建的（i在一套冒泡排序完之后，++i，i还是占用同样的空间，所以整体下来i始终是一个变量）。
• exchange变量是额外创建的。

所以N=3是常数，所以冒泡排序的空间复杂度用大O阶表示就是：O(1)。

3.2、计算斐波那契第n项的数组的空间复杂度

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

//空间复杂度：O(N)

分析：这是计算斐波那契第N项个数的数组，所以需要计算N次。

• fibArray计算N次。
• 变量i也是额外创建的。

当N越来越大时，变量i可以忽略不计了。

所以此大O阶表示为：O(N)。

3.3、阶乘的空间复杂度计算

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

//空间复杂度：O(N)

分析：比如N=4，那就是4*3*2*1。

N=4时需要额外的空间。

N=3时需要额外的空间。

N=2时需要额外的空间。

N=1时需要额外的空间。

一共是N个栈帧的创建。

所以大O阶表示：O(N)。

3.4、斐波那契数列的空间复杂度计算

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

大O阶表示法：O(N)

斐波那契数列按理说时间复杂度和空间复杂度是一样的，都应该是O(N) = 2^N。

但是这里为什么空间复杂度时O(N)呢？如果空间复杂度是2^N，那么会栈溢出。

这是因为：

• 空间是可以重复利用，不累计的。
• 时间是一去不复返，累计的。

那这里空间是如何重复利用呢？如下图所示：

我们将具体的斐波那契数列执行过程细分来看其实是这样的：

这样其它的会重复使用这个空间，这里使用了N个空间，所以最多建立N个栈帧。

所以说我们也可以感知到了斐波那契数列的空间复杂度就是O(N)。

4、常见的复杂度对比

5201314	O(1)	常数阶
3n+4	O(N)	线性阶
3n^2+4n+5	O(N^2)	平方阶
3log(2)n+4	O(longn)	对数阶
2n+3nlog(2)n+14	O(nlogn)	nlogn阶
n3+2n2+4n+6	O(N^3)	立方阶
2^n	O(2^N)	指数阶