人们已经回答了你的确切问题，所以我要回答一个稍微不同的问题，人们来这里时可能会想到这个问题。

许多“O(1)时间”算法和数据结构实际上只需要预期的O(1)时间，这意味着它们的平均运行时间是O(1)，可能仅在某些假设下。

常见的例子:哈希表，“数组列表”的扩展(也就是动态大小的数组/向量)。

在这种情况下，您可能更喜欢使用保证时间绝对受对数限制的数据结构或算法，即使它们的平均性能可能更差。 一个例子可能是平衡二叉搜索树，它的运行时间平均较差，但在最坏的情况下更好。

有很多很好的答案，其中一些提到了常量因素，输入大小和内存限制，以及许多其他原因，复杂性只是一个理论指导原则，而不是最终决定现实世界是否适合给定的目的或速度。

这里有一个简单而具体的例子来说明这些想法。假设我们想要找出一个数组是否有重复的元素。简单的二次型方法是编写一个嵌套循环:

const hasDuplicate = arr => { 对于(设I = 0;I < arrr .length;我+ +){ For(令j = I + 1;J < arrr .length;j + +) { If (arr[i] === arr[j]) { 返回true; ｝ ｝ ｝ 返回错误; }; console.log(hasDuplicate([1,2,3,4])); console.log(hasDuplicate([1,2,4,4]));

但这可以通过创建一组数据结构(即删除重复项)，然后将其大小与数组的长度进行比较，在线性时间内完成:

const hasDuplicate = arr => new Set(arr)。== arrr .length; console.log(hasDuplicate([1,2,3,4])); console.log(hasDuplicate([1,2,4,4]));

大O告诉我们，从时间复杂性的角度来看，新的Set方法将更好地扩展。

然而，事实证明，“天真的”二次元方法有很多大O不能解释的:

没有额外的内存占用 没有堆内存分配(没有新的) 临时Set没有垃圾收集 早期的救助;在已知副本可能位于数组前面的情况下，不需要检查多个元素。

如果我们的用例是在有限的小数组上，我们有一个资源受限的环境和/或其他已知的常见情况属性，允许我们通过基准测试建立嵌套循环在特定工作负载上更快，这可能是一个好主意。

另一方面，也许可以预先创建一次集合并重复使用，在所有查找中摊销其开销成本。

这不可避免地导致可维护性/可读性/优雅性和其他“软”成本。在这种情况下，新的Set()方法可能更具可读性，但通常(如果不是更多的话)要获得更好的复杂性需要付出巨大的工程成本。

创建和维护持久的、有状态的Set结构可能会带来bug、内存/缓存压力、代码复杂性和所有其他设计权衡方式。最优地协商这些权衡是软件工程的一个重要部分，而时间复杂性只是帮助指导这个过程的一个因素。

我还没有看到其他一些例子:

In real-time environments, for example resource-constrained embedded systems, sometimes complexity sacrifices are made (typically related to caches and memory or scheduling) to avoid incurring occasional worst-case penalties that can't be tolerated because they might cause jitter. Also in embedded programming, the size of the code itself can cause cache pressure, impacting memory performance. If an algorithm has worse complexity but will result in massive code size savings, that might be a reason to choose it over an algorithm that's theoretically better. In most implementations of recursive linearithmic algorithms like quicksort, when the array is small enough, a quadratic sorting algorithm like insertion sort is often called because the overhead of recursive function calls on increasingly tiny arrays tends to outweigh the cost of nested loops. Insertion sort is also fast on mostly-sorted arrays as the inner loop won't run much. This answer discusses this in an older version of Chrome's V8 engine before they moved to Timsort.

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).

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

简单地说:因为系数(与该步骤的设置、存储和执行时间相关的成本)在较小的大o问题中比在较大的大o问题中要大得多。Big-O只是算法可伸缩性的一个衡量标准。

考虑以下来自黑客词典的例子，提出了一个依赖于量子力学的多重世界解释的排序算法:

用量子过程随机排列数组， 如果数组没有排序，毁灭宇宙。 所有剩下的宇宙现在都被排序了(包括你所在的宇宙)。

(来源:http://catb.org/ esr /术语/ html / B / bogo-sort.html)

注意，这个算法的大O是O(n)，它击败了迄今为止在一般项目上的任何已知排序算法。线性阶跃的系数也很低(因为它只是一个比较，而不是交换，是线性完成的)。事实上，类似的算法可以用于在多项式时间内解决NP和co-NP中的任何问题，因为每个可能的解(或没有解的可能证明)都可以使用量子过程生成，然后在多项式时间内验证。

然而，在大多数情况下，我们可能不想冒多重世界可能不正确的风险，更不用说实现步骤2的行为仍然是“留给读者的练习”。

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.