为什么恒定总是从大O分析中掉线？

Question

我试图在PC上运行程序的背景下理解Big O分析的一个特定方面.

假设我有一个性能为O(n + 2)的算法.如果n变得非常大,那么2变得微不足道.在这种情况下,非常清楚真正的性能是O(n).

但是,另一种算法的平均性能为O(n ^ 2/2).我看到这个例子的书说实际表现是O(n ^ 2).我不确定我明白为什么,我的意思是在这种情况下,2似乎并非完全无足轻重.所以我正在寻找书中一个很好的清晰解释.这本书以这种方式解释:

"考虑1/2意味着什么.检查每个值的实际时间高度依赖于代码转换的机器指令,然后取决于CPU执行指令的速度.因此1/2不会非常意思."

我的反应是......嗯??? 我完全不知道那句话是什么,或者更确切地说,这句话与他们的结论有什么关系.请允许有人为我拼出来.

谢谢你的帮助.

Answer 1

"这些常数是有意义的还是相关的？"之间存在区别？并且"大O符号关心他们吗？" 第二个问题的答案是"不",而第一个问题的答案是"绝对的".

Big-O表示法并不关心常数,因为big-O表示法仅描述函数的长期增长率,而不是它们的绝对值.将函数乘以常数仅影响其生长速率恒定量,因此线性函数仍然线性增长,对数函数仍然呈对数增长,指数函数仍然呈指数增长等等.由于这些类别不受常数影响,因此它不会我们放弃常数的问题.

也就是说,这些常数绝对重要!的函数,其运行时间为10 ¹⁰⁰ n将被方式比其运行时只是N A功能慢.运行时为n ^2/2的函数将比运行时为n ²的函数快.前两个函数都是O(n)和后两个函数都是O(n ²)这一事实并没有改变它们不会在相同的时间内运行的事实,因为那不是什么大O符号是专为.O符号有助于确定从长远来看一个函数是否会大于另一个函数.即使10 ¹⁰⁰ n对于任何n> 0来说都是巨大的值,该函数也是O(n),因此对于足够大的n,它最终会击败运行时为n ^2/2的函数,因为该函数是O(n ²⁾).

总之 - 由于大O只讨论增长率的相对类别,它忽略了常数因素.但是,这些常数绝对重要; 它们与渐近分析无关.

希望这可以帮助!

Answer 2

常数很重要，你是完全正确的。在比较同一问题的许多不同算法时，不带常数的 O 数可以让您大致了解它们之间的比较情况。如果您在同一个 O 类中有两个算法，您将使用所涉及的常量来比较它们。

\n\n

但即使对于不同的 O 类，常数也很重要。例如，对于多位数或大整数乘法，朴素算法是 O(n^2)，Karatsuba 是 O(n^log_2(3))，Toom-Cook O(n^log_3(5)) 和 Sch\xc3\ xb6nhage-Strassen O(n*log(n)*log(log(n)))。然而，每个更快的算法都有越来越大的开销，这反映在大常数上。因此，为了获得近似的交叉点，需要对这些常数进行有效的估计。因此，如 SWAG 所示，在 n=16 之前，朴素乘法是最快的，在 n=50 Karatsuba 之前，从 Toom-Cook 到 Sch\xc3\xb6nhage-Strassen 的交叉发生在 n=200 时。

\n\n

实际上，交叉点不仅取决于常数，还取决于处理器缓存和其他与硬件相关的问题。

\n

Answer 3

Big-O 表示法仅从数学函数的角度描述算法的增长速度，而不是算法在某些机器上的实际运行时间。

在数学上，对于足够大的 x，令 f(x) 和 g(x) 为正。我们说 f(x) 和 g(x) 以与 x 趋于无穷大相同的速度增长，如果

现在让 f(x)=x^2 和 g(x)=x^2/2，然后 lim(x->infinity)f(x)/g(x)=2。所以 x^2 和 x^2/2 都有相同的增长率。所以我们可以说 O(x^2/2)=O(x^2)。

正如 templatetypedef 所说，渐近符号中的隐藏常数绝对重要。例如：marge 排序在 O(nlogn) 最坏情况下运行，插入排序在 O(n^2) 最坏情况下运行。但作为隐藏常数因子插入排序比边缘排序小，实际上对于许多机器上的小问题，插入排序可以比边缘排序更快。

Answer 4

Big O 表示法最常用于描述算法的运行时间。在这种情况下，我认为特定的常量值本质上是没有意义的。想象一下下面的对话：

Alice：你算法的运行时间是多少？

鲍勃：7n ²

爱丽丝：你说的 7n ²是什么意思？

• 单位是什么？微秒？毫秒？纳秒？
• 你在什么 CPU 上运行它？英特尔 i9-9900K？高通骁龙845？（或者您使用的是 GPU、FPGA 还是其他硬件？）
• 您使用的是什么类型的 RAM？
• 你用什么编程语言实现了算法？源代码是什么？
• 您使用的是什么编译器/VM？你传递给编译器/VM 的标志是什么？
• 什么是操作系统？
• 等等。

因此，如您所见，任何表示特定常量值的尝试本质上都是有问题的。但是一旦我们抛开常数因素，我们就可以清楚地描述一个算法的运行时间。Big O 符号为我们提供了一个关于算法需要多长时间的强大而有用的描述，同时从其实现和执​​行的技术特征中抽象出来。

现在，在描述算法执行的操作数（适当定义）或 CPU 指令数、排序算法执行的比较数等时，可以指定常数因子。但通常，我们真正感兴趣的是运行时间。

这并不是说算法在现实世界中的性能特征不重要。例如，如果您需要矩阵乘法的算法，则建议不要使用 Coppersmith-Winograd 算法。该算法确实需要 O(n ^2.376 ) 时间，而其最强竞争对手 Strassen 算法则需要 O(n ^2.808） 时间。然而，根据维基百科的说法，Coppersmith-Winograd 在实践中很慢，并且“它只为大到现代硬件无法处理的矩阵提供了优势。” 这通常解释为：Coppersmith-Winograd 的常数因子非常大。但重申一下，如果我们谈论的是 Coppersmith-Winograd 的运行时间，那么为常数因子提供一个具体的数字是没有意义的。

尽管存在局限性，但大 O 表示法是一种很好的运行时间度量。在许多情况下，它甚至在我们编写一行代码之前就告诉我们对于足够大的输入大小哪些算法是最快的。