假设您正在嵌入式系统上实现一个黑名单，其中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)的哈希表可能会击败所有这些算法。

在n有界且O(1)算法的常数乘子高于log(n)上的界的任意点。例如，在哈希集中存储值是O(1)，但可能需要对哈希函数进行昂贵的计算。如果数据项可以简单地进行比较(相对于某些顺序)，并且n的边界是这样的，log n明显小于任何一项上的哈希计算，那么存储在平衡二叉树中可能比存储在哈希集中更快。

在关注数据安全的上下文中，如果更复杂的算法对定时攻击有更好的抵抗能力，那么更复杂的算法可能比不太复杂的算法更可取。

当O(1)中的“1”工作单元相对于O(log n)中的工作单元非常高，且期望集大小较小时。例如，如果数组中只有两到三个项，那么计算Dictionary哈希码可能比迭代数组要慢。

or

当O(1)算法中的内存或其他非时间资源需求相对于O(log n)算法非常大时。

A more general question is if there are situations where one would prefer an O(f(n)) algorithm to an O(g(n)) algorithm even though g(n) << f(n) as n tends to infinity. As others have already mentioned, the answer is clearly "yes" in the case where f(n) = log(n) and g(n) = 1. It is sometimes yes even in the case that f(n) is polynomial but g(n) is exponential. A famous and important example is that of the Simplex Algorithm for solving linear programming problems. In the 1970s it was shown to be O(2^n). Thus, its worse-case behavior is infeasible. But -- its average case behavior is extremely good, even for practical problems with tens of thousands of variables and constraints. In the 1980s, polynomial time algorithms (such a Karmarkar's interior-point algorithm) for linear programming were discovered, but 30 years later the simplex algorithm still seems to be the algorithm of choice (except for certain very large problems). This is for the obvious reason that average-case behavior is often more important than worse-case behavior, but also for a more subtle reason that the simplex algorithm is in some sense more informative (e.g. sensitivity information is easier to extract).

以下是我的观点:

有时，当算法在特定的硬件环境中运行时，会选择较差的复杂度算法来代替较好的算法。假设我们的O(1)算法非顺序地访问一个非常大的固定大小数组的每个元素来解决我们的问题。然后将该阵列放在机械硬盘驱动器或磁带上。

在这种情况下，O(logn)算法(假设它按顺序访问磁盘)变得更有利。