1.1 统计时间增长趋势
时间复杂度分析统计的不是算法运行时间,而是算法运行时间随着数据量变大时的增长趋势。
// 算法 A 的时间复杂度:常数阶
void algorithm_A(int n) {
System.out.println(0);
}
// 算法 B 的时间复杂度:线性阶
void algorithm_B(int n) {
for (int i = 0; i < n; i++) {
System.out.println(0);
}
}
// 算法 C 的时间复杂度:常数阶
void algorithm_C(int n) {
for (int i = 0; i < 1000000; i++) {
System.out.println(0);
}
}
算法 A:
时间复杂度为 O(1),这是因为算法A不管输入的
n
是什么值,它都只执行了一次操作——打印数字0。这意味着算法的运行时间是固定的,与输入的大小无关。算法 B:
时间复杂度为 O(n),这是因为算法B中的循环将根据输入的
n
执行n
次打印操作。当n
增加时,执行的操作次数也成比例地增加。算法 C:
时间复杂度同样为 O(1),尽管这个算法使用了一个循环,但循环的次数是固定的1000000次,与输入参数
n
的值无关。这意味着无论n
是什么值,算法C都将执行相同数量的操作,因此运行时间是固定的。
1.2 时间复杂度分析有哪些特点
- 时间复杂度能够有效评估算法效率。
- 时间复杂度的推算方法更简便。
- 时间复杂度也存在一定的局限性。
时间复杂度分析本质上是计算“操作数量 𝑇(𝑛)”的渐近上界,它具有明确的数学定义。
函数渐近上界 若存在正实数 𝑐 和实数 𝑛0 ,使得对于所有的 𝑛 > 𝑛0 ,均有 𝑇(𝑛) ≤ 𝑐 ⋅ 𝑓(𝑛) ,则可认为 𝑓(𝑛) 给 出了 𝑇(𝑛) 的一个渐近上界,记为 𝑇(𝑛) = 𝑂(𝑓(𝑛)) 。
如下图所示,计算渐近上界就是寻找一个函数 𝑓(𝑛) ,使得当 𝑛 趋向于无穷大时,𝑇(𝑛) 和 𝑓(𝑛) 处于相同 的增长级别,仅相差一个常数项 𝑐 的倍数。
1.3 推算方法
第一步:统计操作数量
- 忽略 𝑇(𝑛) 中的常数项。因为它们都与 𝑛 无关,所以对时间复杂度不产生影响。
- 省略所有系数。例如,循环 2𝑛 次、5𝑛 + 1 次等,都可以简化记为 𝑛 次,因为 𝑛 前面的系数对时间复 杂度没有影响。
- 循环嵌套时使用乘法。总操作数量等于外层循环和内层循环操作数量之积,每一层循环依然可以分别 套用第 1. 点和第 2. 点的技巧。
代码举例
void algorithm(int n) { int a = 1; // +0(技巧 1) a = a + n; // +0(技巧 1) // +n(技巧 2) for (int i = 0; i < 5 * n + 1; i++) { System.out.println(0); } // +n*n(技巧 3) for (int i = 0; i < 2 * n; i++) { for (int j = 0; j < n + 1; j++) { System.out.println(0); } } }
以下公式展示了使用上述技巧前后的统计结果,两者推算出的时间复杂度都为 𝑂(𝑛2 ) 。
𝑇(𝑛) = 2𝑛(𝑛 + 1) + (5𝑛 + 1) + 2 完整统计 (‑.‑|||)
= 2𝑛2 + 7𝑛 + 3
𝑇(𝑛) = 𝑛2 + 𝑛 偷懒统计 (o.O)
第二步:判断渐近上界
时间复杂度由 𝑇(𝑛) 中最高阶的项来决定。这是因为在 𝑛 趋于无穷大时,最高阶的项将发挥主导作用,其他 项的影响都可以忽略。
1.4 常见类型
设输入数据大小为 𝑛 ,常见的时间复杂度类型如下图所示(按照从低到高的顺序排列)。
下图对比了常数阶、线性阶和平方阶三种时间复杂度。
指数阶的时间复杂度
对数阶的时间复杂度
线性对数阶的时间复杂度
阶乘阶的时间复杂度
1.5 最差、最佳、平均时间复杂度
最差时间复杂度(Worst-Case Time Complexity): 这是指算法在处理给定数据集时可能花费的最长运行时间。在最坏的情况下,算法可能需要执行最多的步骤来解决问题。例如,对于一个排序算法,如果输入数组是完全逆序的,那么某些排序算法(如冒泡排序或插入排序)将需要执行最多的比较和交换操作,这时它们的最差时间复杂度通常是 O(n^2)。
最佳时间复杂度(Best-Case Time Complexity): 这是指算法在处理给定数据集时可能花费的最短运行时间。在最好的情况下,算法可能可以非常快速地完成任务。例如,在搜索问题中,如果要找的元素恰好位于数据集的第一个位置,那么线性搜索的最佳时间复杂度就是 O(1),因为它只需要一次比较就可以找到目标。
平均时间复杂度(Average-Case Time Complexity): 这是指算法在处理所有可能的输入数据集时,平均所需的时间。平均时间复杂度通常比最差时间复杂度更乐观,但比最佳时间复杂度更悲观。它考虑了所有可能的输入情况,并假设这些情况出现的概率相等。例如,对于快速排序算法,虽然其最差情况时间复杂度为 O(n^2),但在平均情况下,它的时间复杂度为 O(n log n)。