证明基于比较的算法求解人名查分问题的最坏情况Ω(log n)及疑问

一、证明最坏时间复杂度为Ω(log n) #

我们可以通过决策树模型推导这个下界：

• 所有基于比较的查询算法，都能抽象成一棵二叉决策树：每个内部节点对应一次人名比较操作（比如判断查询名与当前节点人名的大小关系），每个叶子节点对应一个查询结果（找到匹配分数或确定目标不存在）。
• 假设数组中有n个不同的人名，查询时至少需要区分n种匹配情况，因此决策树至少包含n个叶子节点。
• 高度为h的二叉树，叶子节点总数最多为2^h。结合上述结论可得：n ≤ 2^h，两边取对数后得到h ≥ log₂n。这意味着最坏情况下的比较次数至少为log₂n，即算法的最坏时间复杂度为Ω(log n)。

二、解答疑问：是否所有基于比较的算法最坏时间复杂度均为Ω(n log n)？ #

答案是否定的，存在大量基于比较的算法，其最坏时间复杂度远低于Ω(n log n)：

• 线性扫描算法：不做任何预处理，直接遍历数组逐个比较人名，找到匹配的分数。这种算法的最坏时间复杂度为O(n)，明显小于Ω(n log n)。
• 预处理+二分查询：先通过基于比较的排序算法（如归并排序）将数组按人名排序（预处理时间O(n log n)），之后每次查询使用二分查找，单次查询的最坏时间复杂度为O(log n)，同样远低于Ω(n log n)。

Ω(n log n)是基于比较的排序算法的最坏时间复杂度下界，但查询问题并不强制要求对数组排序，因此不存在这样的强制限制。

内容的提问来源于stack exchange，提问作者Deveo