为什么总是从大O分析中减去该常数？

80
投票

[这些常量有意义还是相关？和“大O表示法是否关心它们？”第二个问题的答案为“否”，而第一个问题的答案为“绝对！”

Big-O表示法不关心常量，因为big-O表示法仅描述函数的长期增长率，而不是函数的绝对值。将函数乘以常数只会对其常数的增长率产生影响，因此线性函数仍会线性增长，对数函数仍会对数增长，指数函数仍呈指数增长，等等。由于这些类别不受常数的影响，因此不会无论我们删除常量。

也就是说，这些常量绝对有效！运行时为10 ¹⁰⁰ n的函数将比运行时仅为n的函数慢[[way。运行时间为n 2 / 2的函数将比运行时间仅为n ²的函数更快。前两个函数都是O（n），后两个函数都是O（n ²）的事实并没有改变它们不在相同时间运行的事实，因为那不是big-O表示法是为此而设计的。记号对于确定^{从长远来看}一个函数是否会大于另一个函数很有用。即使10 100 n对于任何n> 0来说都是一个巨大的值，但该函数为O（n），因此对于足够大的n最终，它将击败运行时间为n ² / 2的函数因为该函数是O（n ²）。

^{总而言之，由于big-O只讨论相对的增长率类别，因此它忽略了恒定因素。但是，这些常数绝对重要。它们只是与渐进分析无关。希望这会有所帮助！}

5
投票

[Big-O符号仅根据数学函数描述算法的增长率，而不是某些机器上算法的实际运行时间。

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

<< img src =“ https://image.soinside.com/eyJ1cmwiOiAiaHR0cHM6Ly9pLnN0YWNrLmltZ3VyLmNvbS9zeld1eC5qcGcifQ==” alt =“在此处输入图像描述”>

现在让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 sort在O（nlogn）最坏情况下运行，插入sort在O（n ^ 2）最坏情况下运行。对于许多机器上较小的问题，插入排序中的常量因子小于marge排序的常量因子，实际上，插入排序可能比marge排序的速度更快。

4
投票

您完全正确，常量很重要。在比较同一问题的许多不同算法时，不带常量的O数为您提供了它们如何比较的概述。如果您在同一个O类中有两种算法，则可以使用所涉及的常量对其进行比较。

但是即使对于不同的O类，常量也很重要。例如，对于多位数或大整数乘法，朴素算法为O（n ^ 2），唐津为O（n ^ log_2（3）），Toom-Cook O（n ^ log_3（5））和Schönhage-StrassenO （n * log（n）* log（log（n）））。但是，每个更快的算法在大常量上的开销都越来越大。因此，要获得近似的交叉点，就需要对这些常数进行有效的估计。因此，就像SWAG一样，最多n = 16的天真乘法最快，最多n = 50 Karatsuba，并且从Toom-Cook到Schönhage-Strassen的交叉发生在n = 200。

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

4
投票

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

爱丽丝：您的算法的运行时间是多少？

鲍勃：7n

^{爱丽丝：7n 2}是什么意思？^{什么单位？微秒？毫秒？纳秒？您在哪个CPU上运行？英特尔i9-9900K？高通骁龙845？（或者您使用的是GPU，FPGA还是其他硬件？）
您正在使用哪种类型的RAM？
您使用哪种编程语言实现该算法？什么是源代码？
您正在使用什么编译器/ VM？您将哪些标志传递给编译器/ VM？
什么是操作系统？
等
如您所见，任何表示特定常数值的尝试本质上都是问题。但是，一旦我们撇开常数因子，我们就可以清楚地描述算法的运行时间。大O符号为我们提供了算法耗时的健壮和有用的描述，同时抽象了其实现和执行的技术特征。现在，当描述算法执行的操作数（适当定义）或CPU指令，排序算法执行的比较数等时，可以指定常数因子。但是通常，我们真正感兴趣的是运行时间。
这些都不是暗示算法的实际性能特征不重要。例如，如果您需要矩阵乘法的算法，则不建议使用Coppersmith-Winograd算法。确实，此算法需要O（n
2.376}）时间，而其最强竞争对手Strassen算法却需要O（n ^2.808）时间。但是，根据Wikipedia所述，Coppersmith-Winograd在实践中速度较慢，并且“它仅对大型矩阵提供了优势，以至于无法通过现代硬件进行处理。”通常可以这样解释，即Coppersmith-Winograd的常数因子非常大。但是要重申一下，如果我们谈论的是Coppersmith-Winograd的运行时间，那么给定常数作为常数是没有意义的。^{尽管有其局限性，但是大的O标记可以很好地衡量运行时间。而且在很多情况下，它甚至告诉我们在编写一行代码之前，就告诉我们对于足够大的输入大小，哪种算法最快。}

3
投票

没有常数的Big O足以进行算法分析。

首先，实际时间不仅取决于多少条指令，而且还取决于每条指令的时间，这与代码运行所在的平台紧密相关。这不仅仅是理论分析。因此在大多数情况下该常数不是必需的。

其次，Big O主要用于测量随着问题变大运行时间将如何增加，或者随着硬件性能的提高运行时间将如何减少。

第三，对于高性能优化的情况，还将考虑常数。

1
投票

除非现在输入的值非常大，否则现在不需要花大量时间在计算机中执行特定任务所需的时间。

假设我们要乘以2个大小为10 * 10的矩阵，将不会有问题

除非我们要进行此操作多次，然后渐近符号的作用变得普遍并且当n的值变得非常大时，常数对答案实际上没有任何影响，并且几乎可以忽略不计]]，因此我们倾向于在计算复杂度时保留它们。

0
投票

O(n+n)的时间复杂度降低为O(2n)。现在2是一个常数。因此，时间复杂度将主要取决于n。因此，O(2n)的时间复杂度等于O(n)。同样，如果存在类似O(2n + 3)的内容，则仍将是O(n)，因为时间基本上取决于n的大小。现在假设有一个代码O(n^2 + n)，它将是O(n^2)，因为当n的值增加时，与n^2的效果相比，n的效果将变得不那么重要。例如：

问题描述投票：40回答：7

7个回答

最新问题

为什么总是从大O分析中减去该常数？

问题描述 投票：40回答：7

7个回答

最新问题

问题描述投票：40回答：7