在实时情况下，当你需要一个固定的上界时，你会选择一个堆排序，而不是快速排序，因为堆排序的平均行为也是它的最差情况行为。

当n很小时，O(1)总是很慢。

假设您正在嵌入式系统上实现一个黑名单，其中0到1,000,000之间的数字可能被列入黑名单。这就给你留下了两个选择:

使用1,000,000位的bitset 使用黑名单整数的排序数组，并使用二进制搜索来访问它们

对bitset的访问将保证常量访问。从时间复杂度来看，它是最优的。从理论和实践的角度来看(它是O(1)，常量开销极低)。

不过，你可能更喜欢第二种解决方案。特别是如果您希望黑名单整数的数量非常小，因为这样内存效率更高。

即使您不为内存稀缺的嵌入式系统开发，我也可以将任意限制从1,000,000增加到1,000,000,000,000，并提出相同的论点。那么bitset将需要大约125G的内存。保证最坏情况复杂度为O(1)可能无法说服您的老板为您提供如此强大的服务器。

在这里，我强烈倾向于二叉搜索(O(log n))或二叉树(O(log n))而不是O(1)位集。在实践中，最坏情况复杂度为O(n)的哈希表可能会击败所有这些算法。

我很惊讶没有人提到内存绑定应用程序。

可能存在一种算法具有较少的浮点运算，这要么是因为它的复杂性(即O(1) < O(log n))，要么是因为复杂度前面的常数更小(即2n2 < 6n2)。无论如何，如果较低的FLOP算法的内存限制更大，您可能仍然更喜欢具有更多FLOP的算法。

我所说的“内存受限”是指您经常访问的数据经常超出缓存。为了获取这些数据，在对其执行操作之前，必须将内存从实际内存空间拉到缓存中。这个抓取步骤通常非常慢——比您的操作本身慢得多。

因此，如果你的算法需要更多的操作(但这些操作是在已经在缓存中的数据上执行的[因此不需要读取])，它仍然会在实际的walltime方面以更少的操作(必须在缓存外的数据上执行[因此需要读取])胜过你的算法。

There is a good use case for using a O(log(n)) algorithm instead of an O(1) algorithm that the numerous other answers have ignored: immutability. Hash maps have O(1) puts and gets, assuming good distribution of hash values, but they require mutable state. Immutable tree maps have O(log(n)) puts and gets, which is asymptotically slower. However, immutability can be valuable enough to make up for worse performance and in the case where multiple versions of the map need to be retained, immutability allows you to avoid having to copy the map, which is O(n), and therefore can improve performance.

我在这里的回答是，在随机矩阵的所有行的快速随机加权选择是一个例子，当m不是太大时，复杂度为O(m)的算法比复杂度为O(log(m))的算法更快。