每日科普 · 2026-10-12 周一
考研 408 × 求职面试
知识点 · 算法设计与分析 · 基础
最好、最坏与平均情况复杂度分析
1. 最好情况：算法在某个输入下执行最少基本操作。例如线性查找第一个元素就命中，只需 1 次比较，复杂度 O(1)。
2. 最坏情况：算法在某个输入下执行最多基本操作。例如线性查找目标在最后或不存在，需要比较 n 次，复杂度 O(n)。
3. 平均情况：按输入分布求期望操作次数。若目标一定存在且等概率出现在每个位置，线性查找平均比较 (n+1)/2 次，仍为 O(n)。
4. 关键区别：最好情况意义有限；最坏情况给出性能保证；平均情况依赖概率假设。分析时要说明输入模型、基本操作，以及是否考虑查找失败。面试中常结合快排、哈希表考查。
每日一题 · 算法设计与分析
最好、最坏与平均情况复杂度分析
对长度为 n 的顺序表进行线性查找，若目标元素一定存在且等概率出现在每个位置，平均比较次数是多少？
A. 1
B. n/2
C. (n+1)/2
D. n
解析
选 C。目标在第 i 个位置时需比较 i 次，i 从 1 到 n 等概率，因此平均次数为 (1+2+...+n)/n = (n+1)/2。最好情况是第 1 个位置命中，1 次；最坏情况是最后命中或不存在，n 次。平均复杂度仍为 O(n)。
面试小贴士 · 算法设计与分析
最好、最坏与平均情况复杂度分析
面试官常问某算法最好、最坏、平均复杂度及触发条件。先说明输入假设，再给基本操作次数和渐近阶；不要只答平均，要提最坏保证。易错：把平均当最坏、忽略查找失败、快排平均 O(n log n) 最坏 O(n^2)。
代码实现 · C
代码示例
int linear_search(int a[], int n, int x) {
for (int i = 0; i < n; ++i) {
if (a[i] == x) return i; // 找到，返回下标
}
return -1; // 未找到
}
int main() {
int a[] = {5, 3, 8, 1};
int pos = linear_search(a, 4, 8);
return pos; // 返回 2；最好1次，最坏4次，平均约2.5次
}