算法学习笔记（Hello算法）—— 时间复杂度
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)。
原文地址：https://blog.csdn.net/m0_74972727/article/details/140578328
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！