为什么总是从大O分析中剔除？
我试图在PC上运行程序的上下文中了解Big O分析的一个特定方面。
假设我有一个性能为O（n + 2）的算法。 在这里，如果n变得非常大，则2变得不重要。 在这种情况下，非常清楚真实的性能是O（n）。
然而，说另一种算法的平均性能为O（n ^ 2/2）。 我看到这个例子的书说真实的表现是O（n ^ 2）。 我不知道我为什么，我的意思是在这种情况下2似乎不是完全不重要。 所以我正在寻找这本书的一个很好的清晰的解释。 这本书解释了这一点：
“考虑1/2是什么意思，检查每个值的实际时间高度依赖于代码转换的机器指令，然后取决于CPU可以执行指令的速度，因此1/2不会执行指令，这意味着非常多。“
而我的反应是......呃???。 我从字面上不知道该说什么，或者更准确地说，这个说法与他们的结论有关。 请有人为我拼出来。
谢谢你的帮助。
大O符号不关心常量，因为大O符号只描述了函数的长期增长率，而不是绝对值。 函数乘以一个常数只会影响其增长率，因此线性函数仍然线性增长，对数函数仍然以对数形式增长，指数函数仍然以指数形式增长等等。由于这些类别不受常数的影响，因此它不会“不管怎样，我们放弃常量。
也就是说，这些常量是绝对重要的！ 运行时为10100n的函数将比运行时为n的函数慢。 运行时间为n2 / 2的函数将比运行时间仅为n2的函数快。 前两个函数都是O（n）并且后两个函数都是O（n2）的事实并不改变它们不会在相同时间内运行的事实，因为这不是大O符号为...设计。 O符号可以很好地判断一个函数在长期内是否会比另一个函数更大。 即使10100n对任何n> 0来说都是一个巨大的值，那么函数是O（n），所以对于足够大的n，它最终会击败运行时间为n2 / 2的函数，因为函数是O（n2）。
总之 - 由于大O只谈及增长率的相对类别，因此忽略了不变的因素。 但是，这些常数是绝对重要的; 他们只是与渐近分析无关。
希望这可以帮助！
你是完全正确的，常数很重要。 在比较同一问题的许多不同算法时，没有常量的O数字给你一个他们如何比较的概述。 如果在同一个O类中有两个算法，则可以使用所涉及的常量进行比较。
但即使对于不同的O类，常量也很重要。 例如，对于多数字或大整数乘法，朴素算法是O（n ^ 2），Karatsuba是O（n ^ log_2（3）），Toom-Cook O（n ^ log_3（5））和Schönhage-Strassen O （N *的log（n）*日志（的log（n）））。 但是，每个更快的算法都会在大常量中反映出越来越大的开销。 所以为了得到近似的交叉点，需要对这些常数进行有效的估计。 因此，如SWAG所示，最多n = 16的天真增殖最快，最多n = 50 Karatsuba，并且从Toom-Cook到Schönhage-Strassen的交叉发生在n = 200。
实际上，交叉点不仅取决于常量，还取决于处理器缓存和其他硬件相关问题。
Big-O符号仅仅描述算法在数学函数上的增长率，而不是某些机器上算法的实际运行时间。
在数学上，令f（x）和g（x）对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 sort在O（nlogn）中运行最坏情况时间，插入排序在O（n ^ 2）最坏情况时间运行。但由于隐藏常数因子插入排序小于marge排序，实际上插入排序可以比许多机器上的小问题大小更快地进行排序。
链接地址: http://www.djcxy.com/p/39699.html