数据结构 ——— 常见的时间复杂度计算例题（最终篇）

前言

例题1：

例题2（例题1的延申）：

例题3：

前言

在前两章分析了不少常见的时间复杂度计算例题，有固定执行N次的，也有要分情况看待的

数据结构 ——— 常见的时间复杂度计算例题（上篇）-CSDN博客

数据结构 ——— 常见的时间复杂度计算例题（中篇）-CSDN博客

接下来要分析的是递归算法的时间复杂度例题

例题1：

代码演示：

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

	return Fac(N - 1) * N;
}

问：计算阶乘递归 Fac 函数的时间复杂度？

代码解析：

第一次进入 Fac 函数，先进行 if 判断，判断为假，就会再次执行 Fac 函数，知道 N 为 0 就递归返回，那么也就是：

Fac(N) -> Fac(N-1) -> Fac(N-2) -> …… -> Fac(2) -> Fac(1) -> Fac(0)

执行了 N 次，且每次执行是一个 if 判断，也就是每次执行常数次，也就是 N*1 = N，得出时间复杂度函数式：

时间复杂度函数式：F(N) = N

那么直接通过时间复杂度函数式得出大O的渐进表示法：

大O渐进表示法：O(N)

例题2（例题1的延申）：

代码演示：

long long FFac(size_t N)
{
	if (N == 0)
		return 1;

	// 循环1
	for (size_t i = 0; i < N; i++)
	{
		//……
	}

	return Fac(N - 1) * N;
}

问：计算阶乘递归 FFac 函数的时间复杂度？

代码解析：

和例题1 基本类似，唯一的区别在于例题1 的每次递归中只执行 if 语句，也就是每次递归只执行了常数次，而例题2 的每次递归除了执行了 if 语句，还执行了 for 循环，也就是例题2 每次递归了 1+N 次，且递归了 N 次，所以得出时间复杂度函数式：

时间复杂度函数式：F(N) = N(1+N) = N^2 + N

由时间复杂度函数式和大O的渐进表示法规则得出：只保留最高项（去掉 F(N) 中的 N ）得出大O的渐进表示法：

大O渐进表示法：O(N^2)

例题3：

代码演示：

long long Fib(size_t N)
{
	if (N < 3)
		return 1;

	return Fib(N - 1) + Fib(N - 2);
}

问：计算斐波那契递归 Fib 函数的时间复杂度？

代码解析：

最开始进入 Fib(N) 函数，先进行 if 判断，判断为假的话，就会执行 Fib(N-1) 和 Fib(N-2) ，而 Fib(N-1) 又会执行 Fib(N-2) 和 Fib(N-3) ，且 Fib(N-2) 就会执行 Fib(N-3) 和 Fib(N-4)……，以此类推，得出以下类似直角三角形的表达式：

2^0 —— Fib(N)

2^1 —— Fib(N-1) Fib(N-2)

2^2 —— Fib(N-2) Fib(N-3) Fib(N-3) Fib(N-4)

………………………………………………………………

2^(N-4) —— Fib(4) ……………………………

2^(N-3) —— Fib(3) Fib(2) …………

2^(N-2) —— Fib(2) Fib(1)

由以上的表达式得出时间复杂度函数式：

时间复杂度函数式：F(N) = 2^0 + 2^1 + 2^2 + …… + 2^(N-4) + 2^(N-3) + 2^(N-2)

化简时间复杂度函数式（错位相减法）：

等式两边同乘2：

2*F(N) = 2^1 + 2^2 + 2^3 + …… + 2^(N-3) + 2^(N-2) + 2^(N-1)

错位相减：

2*F(N) = 2^1 + 2^2 + 2^3 + ……...... + 2^(N-3) + 2^(N-2) + 2^(N-1)

F(N) = 2^0 + 2^1 + 2^2 + …… + 2^(N-4) + 2^(N-3) + 2^(N-2)

得：

F(N) = -1 + 2^(N-1) = 2^(N-1) -1

再根据时间复杂度函数式和大O的渐进表示法的规则推导出大O的渐进表示法：只保留最高阶项（除去 F(N) 中的 1 ）；如果最高阶项存在且不是1，则去除与这个项目相乘的常数（除去 F(N) 中的1 ），得出大O的渐进表示法：

大O渐进表示法：O(2^N)

结论

计算代码的时间复杂度时，不论代码是固定执行的次数，还是要分情况看待，还是递归执行，都要先推导出时间复杂度的函数式，再根据时间复杂度函数式和大O的渐进表示法的规则推导出大O的渐进表示法。