当Big-O符号何时失效？

这在一定程度上取决于大O表示法测量的内容 - 当它针对最坏情况时，运行时性能通常会比大O所示更好。如果是平均情况，则可能会更糟。
大O表示法通常在算法输入数据具有某些先前信息时“失败”。通常，大O表示法指的是最坏情况下的复杂度 - 如果数据完全随机或完全非随机，则通常会发生这种情况。
例如，如果您向经过分析的算法提供数据，并且大O基于随机数据，但是您的数据具有非常明确定义的结构，则结果时间可能比预期快得多。同样地，如果您正在测量平均复杂度，并且输入数据被恶意随机化，那么算法的执行效果可能比预期差得多。

1. Small N - 对于现今的计算机而言，100个数据量太小无需担忧。
2. Hidden Multipliers - 比如合并排序和快速排序。
3. Pathological Cases - 再比如，合并排序和快速排序在处理某些极端情况下的表现。

在数据量超过可用RAM的情况下，Big-Oh符号法则失效。以排序为例，排序所需时间不是由比较或交换的数量支配（在最优情况下，分别为O(n log n)和O(n)），而是由磁盘操作的次数支配：块写入和块读取。
为了更好地分析处理超出可用RAM的数据的算法，引入了I/O模型，其中计算磁盘读取次数。在此，考虑三个参数：
- 元素数量N； - 内存（RAM）量M（可以放入内存的元素数量）；和 - 磁盘块大小B（每个块中的元素数量）。
值得注意的是，磁盘空间的数量被视为无限大。一个典型的附加假设是M > B²。
继续以排序为例，在I/O情况下通常会选择归并排序：将元素分成大小为θ(M)的块，并在内存中对它们进行排序（例如使用快速排序）。然后，通过从每个块中读取第一个块将θ(M/B)个块合并到一起，将所有元素塞入堆中，并重复选择最小元素，直到选出B个元素。将这个新的合并块写出并继续执行。如果你耗尽了读入内存的块之一，则从同一块中读取新的块并将其放入堆中。
（所有表达式都应该被视为大Θ）。你形成了N/M个排序块，然后将它们合并。你需要合并log(base M/B) N/M次；每次都要读取和写入所有N/B个块，所以需要N/B * (log base M/B of N/M)时间。
你可以分析内存排序算法（适当修改以包括块读取和块写入），并发现它们比我介绍的归并排序效率低得多。
这些知识来自于Arge和Brodal的I/O算法课程（http://daimi.au.dk/~large/ioS08/）；我还进行了实验验证理论：一旦超出内存，堆排序需要“几乎无限”的时间。快速排序变得难以承受，归并排序几乎难以承受，I/O效率高的归并排序表现良好（最佳）。

我曾经见过一些情况，随着数据集的增长，算法复杂度变得不那么重要了，相比较一个具有更糟糕大O记号的算法，用一个聪明的算法来浏览一个大数据结构可能会导致更多的页面错误或缓存未命中。
对于小的 n 值，两个算法可能是可比较的。随着 n 的增加，更聪明的算法表现得更好。但是，在某个点上，n 变得足够大，使系统受到内存压力的影响，此时“更糟糕”的算法实际上可能表现更好，因为常数基本上被重置了。
然而，这并不特别有趣。当你达到这个倒转点时，两种算法的性能通常都是无法接受的，你必须找到一种新的算法，它具有更友好的内存访问模式和更好的大O复杂度。

罗伯特·塞奇威克在他的《算法分析》Coursera课程中谈到了大O符号的缺点。他称特别的恶劣例子为“银河算法”，因为尽管它们可能比它们的前任有更好的复杂度类，但在实践中需要天文级别的输入才能显示出来。

https://www.cs.princeton.edu/~rs/talks/AlgsMasses.pdf

当你的数据不符合模型时，大O符号仍然有效，但你会看到最好和最坏情况之间有重叠。

此外，一些操作针对线性数据访问与随机数据访问进行了调整，因此，一个算法在周期方面优越，但如果调用它的方法从设计中改变，它可能会非常缓慢。同样，如果一个算法由于访问内存的方式而导致页面/缓存未命中，那么大O符号将无法准确估计运行进程的成本。

显然，就像我已经忘记的那样，当N很小时 :)

这个问题就像是在问：“一个人的智商什么时候会在实践中失败？”很明显，拥有高智商并不意味着你会在生活中取得成功，而拥有低智商也不意味着你会灭亡。然而，我们衡量智商是为了评估潜力，即使它不是绝对的。

在算法中，大O符号给出了算法的智商。这并不一定意味着该算法在您特定的情况下表现最佳，但有一些数学基础表明该算法具有一些良好的潜力。如果大O符号足以衡量性能，那么你会看到更多的它，而少一些运行时测试。

将大O视为范围而不是更好或更差的具体度量。有最佳情况和最坏情况，还有大量的中间情况。选择算法的方法是看它们如何适应大O范围，但不要依赖符号来衡量性能的绝对值。

简短回答：当您开始使用大量内存时，现代硬件上始终如此。教科书假设内存访问是均匀的，但现在不再是这样了。当然，您可以为非均匀访问模型执行Big O分析，但这要复杂得多。
小n案例很明显，但不太有趣：足够快就足够了。
实际上，我在Delphi、Java、C#和Smalltalk中使用标准集合时遇到了问题，其中包含数百万个对象，以及在小对象中，主导因素是哈希函数或比较。

Big O及其相关概念被用于比较渐近数学函数的增长。我想强调其中的数学部分。它完全是关于将问题化简成一个输入递增（或者说规模扩大）的函数的能力。它给出了一个很好的图像，其中输入量（x轴）与执行的操作次数（y轴）有关。这完全建立在数学函数的基础上，并要求我们准确地将所使用的算法建模为某种多项式形式。然后就是缩放的假设。
当数据是有限的、固定的且大小恒定时，Big O立即失去了其相关性。这就是为什么几乎所有嵌入式程序员都不会费心研究Big O的原因。从数学上讲，它总是得到O(1)，但我们知道我们需要优化我们的代码以适应空间和MHz定时预算，而这个优化程度超出了Big O的适用范围。这种优化就是同一级别的，各个组件由于对系统性能直接依赖而变得重要。
Big O的另一个失败之处在于它假设硬件差异无关紧要。拥有MAC、MMU和/或位移低延迟数学运算功能的CPU将胜过一些可能被错误地识别为更高阶的渐近符号任务。这仅仅是因为模型本身的局限性所导致的。
另一个常见情况是，在错误地识别要解决的问题的本质并最终得到一个二叉树时，大 O 的重要性变得绝对不相关了。实际上，解决方案实际上是一个状态机。整个算法方案经常忽略了有限状态机问题。这是因为状态机复杂度基于状态数量而不是输入或数据数量增长，而在大多数情况下这些是恒定的。
另一个方面是内存访问本身，这是与硬件和执行环境分离的问题的扩展。许多时候，内存优化会带来性能优化，反之亦然。它们不一定是相互排斥的。这些关系不能很容易地建模成简单的多项式。在堆（内存区域不在算法堆中）数据上运行的理论上糟糕的算法通常比在栈中的数据上运行的理论上良好的算法表现更好。这是因为内存访问和存储效率存在时间和空间复杂度，这些复杂度在大多数情况下不属于数学模型，即使尝试建模，也经常被忽略为可以具有高影响力的低阶项。这是因为这些将显示为一长串被模型忽略的低阶项，当有足够大量的低阶项被忽略时，它们可以具有更大的影响。

想象一下n³+8⁶n²+5*10⁶n²+10⁹n

很明显，具有高倍数的低阶项可能会比大O模型忽略的最高阶项更具有重要意义。它会让我们忽略除n³之外的所有内容。术语“足够大的n”被滥用来想象不现实的情况以证明算法的正确性。对于这种情况，n必须非常大，以至于在担心算法本身之前就会耗尽物理内存。如果您甚至无法存储数据，则算法无关紧要。当内存访问被建模时，低阶项可能看起来像上面的多项式，其中包含超过100个高度缩放的低阶项。然而，对于所有实际目的而言，这些术语甚至从未成为算法试图定义的方程的一部分。

大多数科学符号通常是数学函数的描述，用于建模某些东西。它们是工具。因此，工具的实用性受限，并且仅取决于模型本身的好坏。如果模型无法描述或与手头的问题不匹配，则该模型根本无法达到目的。这就是需要使用不同模型的时候，当这种方法不起作用时，直接方法可能会很好地达到您的目的。

此外，许多最初的算法都是图灵机的模型，它具有完全不同的工作机制，今天的所有计算都是RASP模型。在使用大O或任何其他模型之前，首先问自己这个问题：“我选择了正确的模型来完成手头任务，并且我拥有最实际精确的数学函数吗？”如果答案是否定的，则凭借经验、直觉并忽略花哨的内容。