复杂度分析 #
复杂度分析包括四个重要概念：
- 最好情况时间复杂度（best case time complexity）
- 最坏情况时间复杂度（worst case time complexity）
- 平均情况时间复杂度（average case time complexity）
- 均摊时间复杂度（amortized time complexity）
最好、最坏情况时间复杂度 #
考虑以下查找代码：
int find(int[] array, int n, int x) {
int i = 0;
int pos = -1;
for (; i < n; ++i) {
if (array[i] == x) {
pos = i;
break;
}
}
return pos;
}
这段代码的时间复杂度取决于查找目标的位置：
- 最好情况：目标在数组第一个位置，时间复杂度为 O(1)
- 最坏情况：目标不存在，需要遍历整个数组，时间复杂度为 O(n)
因此需要引入不同情况下的时间复杂度概念：
- 最好情况时间复杂度：在最理想情况下执行代码的时间复杂度
- 最坏情况时间复杂度：在最糟糕情况下执行代码的时间复杂度
平均情况时间复杂度 #
最好和最坏情况时间复杂度都是极端情况，发生概率不大。为了更好地表示平均情况，需要引入平均情况时间复杂度（简称平均时间复杂度）。
平均时间复杂度分析 #
以查找变量 x 为例，有 n+1 种情况：在数组的 0～n-1 位置中和不在数组中。简单平均计算：
简化后得到 O(n)，但这个计算有问题：各种情况出现的概率不同。
假设 x 在数组中的概率为 1/2，不在数组中的概率为 1/2。如果 x 在数组中，出现在任意位置的概率为 1/n。根据概率乘法法则，x 出现在 0～n-1 中任意位置的概率为 1/(2n)。
考虑概率后的加权平均计算：
这个值就是加权平均时间复杂度或期望时间复杂度。
最终加权平均值为 (3n+1)/4，用大 O 表示法仍为 O(n)。
实际应用
大多数情况下不需要区分三种时间复杂度。只有当同一代码在不同情况下时间复杂度有量级差距时，才需要区分使用。
均摊时间复杂度 #
说白了，均摊时间复杂度就是：
把偶尔出现的 “大开销” 操作，平摊到平时的 “小开销” 操作上，算出一个更实在的平均成本。
举个生活例子： 你每天上班都走路（5 分钟，很轻松），但每周五要大扫除（1 小时，很累）。 如果单看周五，你会觉得 “上班好费时间啊！"（就像最坏时间复杂度）。 但均摊一下：一周 5 天总耗时 = 5×5 分钟 + 60 分钟 = 85 分钟，平均每天 17 分钟。这更能反映你平时上班的真实花费。
算法里也一样： 比如动态数组插入，平时插一个元素很快（O (1)），但偶尔满了要扩容（复制所有元素，O (n)）。 把扩容的 “大开销” 分摊到之前所有的 “小开销” 插入上，算出来的平均成本就是均摊时间复杂度（这里是 O (1)）
// 简单的栈结构
int stack[4]; // 初始容量为4
int top = 0; // 栈顶位置
int total_ops = 0; // 记录总操作次数
// 压栈操作
void push(int value) {
// 如果栈满了，需要清空栈（模拟"昂贵"的操作）
if (top == 4) {
printf("栈满了，清空栈... ");
top = 0; // 清空栈
total_ops += 4; // 假设清空栈需要4次操作（模拟复制成本）
}
// 正常压栈（"便宜"的操作）
stack[top] = value;
top++;
total_ops += 1; // 压栈本身算1次操作
printf("压入%d，当前总操作数: %d\n", value, total_ops);
}
int main() {
// 连续压入8个元素
for (int i = 1; i <= 8; i++) {
push(i);
}
printf("\n8次操作总耗时: %d\n", total_ops);
printf("平均每次操作耗时: %.1f\n", (float)total_ops / 8);
return 0;
}
对于这个例子：
- 大部分时候压栈只需要 1 次操作（O (1)）
- 每 4 次压栈会遇到 1 次 “昂贵” 操作（清空栈，需要 4 次操作）
- 把这 4 次昂贵操作分摊到 4 次压栈上，每次平均多 1 次
- 最终平均每次操作只需要 1.5 次，是个常数
- 所以均摊时间复杂度是 O (1)