数据结构 ——— 常见的时间复杂度计算例题（最终篇）
目录
前言
例题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的渐进表示法。