时间复杂度为O(f(x))与θ(f(x))的两种算法应优先选择哪一种？

核心结论 #

通常优先选择给出θ(f(x))复杂度的算法，具体选择逻辑可结合业务场景和复杂度标注前提调整。 #

两个复杂度符号的核心区别 #

先明确两个渐近符号的标准定义：

• O(f(x))（大O符号）：仅代表算法运行时间的上界，数学含义为输入规模x足够大时，算法耗时永远不会超过c*f(x)（c为正的常数）。
  该定义只限制上限，不限制下限：你完全可以把实际复杂度为O(n)的算法标注为O(n²)，数学上完全成立，只是这个上界给得非常宽松，没有实际参考价值。
• θ(f(x))（西塔符号）：代表算法运行时间的紧确界，同时限制了上界和下界：输入规模x足够大时，算法耗时会稳定在c1*f(x)到c2*f(x)之间（c1、c2均为正的常数），不会出现数量级的波动。

具体选择原因 #

1. 性能可预期性更高 #

只要算法标注了θ(f(x))，就说明无论最好、最坏还是平均场景下，它的耗时都在f(x)的量级范围内，不会出现突发的性能暴跌。比如同样是对数级复杂度的查找算法：

• 二分查找的最坏复杂度是θ(logn)，不管输入什么有序数组，最多查询logn次就能得到结果
• 插值查找的最坏复杂度是O(n)，只有输入均匀分布的有序数组时才能达到O(loglogn)的速度，一旦数组分布不均匀，耗时直接飙升到线性级别
  如果是实时交易、系统调度这类对时延稳定性要求极高的场景，选θ(f(x))的算法完全不会踩性能波动的坑。

2. 复杂度标注的可信度更高 #

行业内标注算法复杂度的默认规则是给出能达到的最紧的界。如果一个算法只敢标O(f(x))，不敢标θ(f(x))，只有两种可能：

• 它的性能波动极大，下界远低于f(x)，没法给出稳定的紧确界
• 给出的O(f(x))上界是宽松的，实际最坏复杂度可能远高于预期
  这种情况下选明确给出θ(f(x))的算法，踩坑的概率要低得多。

3. 特殊场景下的例外 #

如果你能100%确认自己的业务数据场景完全匹配O(f(x))算法的最优情况，也可以选择O(f(x))的算法。比如你确认所有输入数组都是均匀分布的，那插值查找的实际表现会比二分查找好很多。

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