并行执行算法的可能性。

我不知道是否有O(log n)和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).

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

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

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

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

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

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

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