再一次，我发现自己有一套破碎的假设。这篇文章本身是关于通过修改一个经过验证的最佳算法来考虑虚拟内存的 10 倍性能提升：
在以千兆赫时钟频率运行的现代多问题 CPU 上，最坏情况下的损失是每个 VM 页面错误几乎 1000 万条指令。如果您使用旋转磁盘运行，那么这个数字更像是 1 亿条指令。
如果这些操作导致页面错误和缓慢的磁盘操作，那么 O(log2(n)) 算法有什么好处？对于大多数相关数据集，避免页面错误的 O(n) 甚至 O(n^2) 算法将围绕它运行。
周围还有更多这样的算法吗？我们是否应该重新审视我们教育的所有这些基本组成部分？自己写的时候还需要注意什么？
澄清：
所讨论的算法并不比经过验证的最优算法快，因为 Big-O 表示法存在缺陷或毫无意义。它更快，因为经过验证的最佳算法依赖于现代硬件/操作系统中不正确的假设，即所有内存访问都是平等的和可互换的。
只有当您的客户抱怨您的程序运行缓慢或错过关键期限时，您才需要重新检查您的算法。否则，请关注正确性、健壮性、可读性和易于维护。在实现这些项目之前，任何性能优化都是在浪费开发时间。
页面错误和磁盘操作可能是特定于平台的。始终分析您的代码以查看瓶颈在哪里。在这些领域花费时间将产生最大的好处。
如果您对页面错误和缓慢的磁盘操作感兴趣，您可能需要了解：
同样，这些项目仅在达到质量、客户投诉和分析器分析您的程序之后。
我将扩展 GregS 的答案：区别在于有效复杂度和渐近复杂度。渐近复杂度忽略常数因素，仅对“足够大”的输入有效。通常“足够大”实际上可能意味着“比现在和几十年内任何计算机都可以处理的更大”；这就是该理论（有理由地）名声不好的地方。当然也有“足够大”意味着n =3 的情况！
一种更复杂（因此也更准确）的方法是首先问“你感兴趣的问题的规模范围是多少？” 然后，您需要测量该大小范围内各种算法的效率，以了解“隐藏常数”。或者您可以使用更精细的算法渐近方法，它实际上可以为您提供对常数的估计。
另一件事是“过渡点”。当然，对于所有n < 1.99 * 10 17 ，运行 2 n 2次的算法将比运行 10 16 n log( n ) 次的算法快。因此，二次算法将是可供选择的算法（除非您正在处理 CERN 担心的数据大小）。即使是次指数项也会咬人——对于n < 5*10 15，3 n 3比n 3 + 10 16 n 2好得多（假设这些是实际的复杂性）。
一件重要的事情是要意识到 big-O 表示法（谈论运行时复杂性）的最常见用法只是故事的一半- 还有另一半，即空间复杂度（也可以使用 big-O 表示），它可以也相当相关。
一般来说，现在内存容量的进步已经超过了计算速度的进步（对于单核 - 并行化可以解决这个问题），因此对空间复杂性的关注较少，但它仍然是一个应该牢记的因素，尤其是在具有更有限的内存或处理大量数据时。
O(n) 只是故事的一部分——很大一部分，通常是主导部分，但并不总是主导部分。一旦进行了性能优化（在开发过程中不应过早进行），您需要考虑您正在使用的所有资源。你可以概括阿姆达尔定律意味着您的执行时间将由最有限的资源支配。请注意，这也意味着还必须考虑您正在执行的特定硬件。对于大规模并行计算机（例如 CM 或 MassPar）而言，高度优化和极其高效的程序在大型矢量盒（例如 Cray-2）和高速微处理器上可能表现不佳。该程序甚至可能在大量功能强大的微处理器（map/reduce 风格）上表现不佳。针对缓存、CPU 通信、I/O、CPU 速度、内存访问等不同平衡的不同优化意味着不同的性能。
当我花时间进行性能优化时，我们会争取整个系统的“平衡”性能。带有慢速 I/O 系统的超快 CPU 几乎没有意义，等等。O() 通常只考虑 CPU 复杂度。您也许可以权衡内存空间（展开循环没有 O() 意义，但它确实经常有助于实际性能）；关注缓存命中副线性内存布局副内存库命中；虚拟与真实内存；磁带 vs 旋转磁盘 vs RAID，等等。如果您的性能主要由 CPU 活动主导，并且 I/O 和内存一直处于闲置状态，那么 big-O 是您最关心的问题。如果你的 CPU 是 5% 并且网络是 100%，也许你可以摆脱 big-O 并处理 I/O、缓存等。
多线程，尤其是多核，使所有分析变得更加复杂。这引发了非常广泛的讨论。如果您有兴趣，Google 可以为您提供数月或数年的参考资料。
我没有看到任何错误的假设。Big-O 表示法是在非常非常简化的理想化计算机上的算法复杂性的度量，并且忽略了常数项。显然，这不是关于实际机器实际速度的最终决定。