f(n)=Θ(g(n))是否蕴含存在常数c使f(n)=cg(n)？求算法相关反例

你说得没错，sin(n)这类数学函数确实是满足Θ(1)但并非常数的简单反例。在算法与系统领域，这类和实际场景绑定的非平凡例子其实很常见：

• 哈希表单次操作（平均情况）：我们通常说哈希表的查找、插入、删除是Θ(1)时间，但这是平均时间复杂度。实际运行时，操作耗时完全依赖哈希冲突情况——冲突少的时候，操作几乎是固定快；但如果遇到极端冲突（比如所有元素哈希到同一个桶），单次操作会退化成O(n)级别的耗时。从平均情况看它属于Θ(1)范畴，但每次操作的实际耗时并不是固定常数，是波动变化的。

• 带优化的并查集单次操作：带路径压缩和按秩合并的并查集，单次操作的时间复杂度是Θ(α(n))，其中α(n)是阿克曼函数的反函数。这个函数增长极慢，哪怕是对应宇宙级别的n，α(n)也不会超过5，但它严格来说不是常数，属于有界的慢增长函数，因此也满足Θ(1)（所有有界函数都属于Θ(1)），但并非常数。

• 缓存敏感的内存访问操作：比如从数组中读取元素，如果元素在CPU缓存里，读取耗时是纳秒级；如果不在缓存，需要从主存甚至磁盘读取，耗时是前者的几十到上万倍。如果我们分析这类操作的平摊或平均时间，会归类为Θ(1)，但实际每次操作的耗时差异极大，并不是固定常数。

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