为什么从大的O分析总是下降？
我试图在PC上运行程序的上下文中了解Big O分析的一个特定方面。
假设我有一个性能为O（n + 2）的algorithm。 在这里，如果n变得非常大，则2变得不重要。 在这种情况下，真正的性能是O（n）。
然而，说另一个algorithm的平均性能为O（n ^ 2/2）。 我看到这个例子的书说真实的performance是O（n ^ 2）。 我不知道为什么，我的意思是在这种情况下，2似乎不是完全无关紧要的。 所以我正在寻找这本书的一个很好的清晰的解释。 这本书解释了这一点：
“考虑1/2是什么意思，检查每个值的实际时间高度依赖于代码转换的机器指令，然后取决于CPU可以执行指令的速度，因此1/2”这意味着非常多。“
而我的反应是……呃??? 我从字面上不知道这个说法是什么，或者更确切地说，这个说法与他们的结论有什么关系。 有人可以为我拼出来，请。
感谢您的帮助。
大O符号不关心常量，因为大O符号只描述了函数的长期增长率，而不是绝对的大小。 常数乘以一个函数只会影响它的增长率，所以线性函数仍然是线性增长的，对数函数仍然以对数forms增长，指数函数依然以指数forms增长等。由于这些类别不受常数的影响，不pipe怎样，我们放弃常量。
那就是说，那些常量是绝对重要的！ 运行时为10 100 n的函数将比运行时为n的函数慢。 运行时间为n 2/2的函数比运行时间仅为n 2的函数要快。 前两个函数都是O（n），后两个是O（n 2 ）的事实并不改变它们不在相同的时间内运行的事实，因为这不是什么大O符号是专为。 O符号可以很好地判断一个函数在长期内是否会比另一个函数大。 即使10 100 n对任何n> 0来说都是一个巨大的值，那么函数是O（n），所以对于足够大的n，它最终会击败运行时间为n 2/2的函数，因为函数是O（n 2 ）。
总而言之，由于大O只谈及增长率的相对类别，因此忽略了不变的因素。 但是，这些常数是绝对重要的。 他们只是与渐近分析无关。
希望这可以帮助！
你是完全正确的，常数很重要。 在比较许多不同的algorithm对于同一个问题，没有常数的O数给你一个他们如何比较彼此的概述。 如果在同一个O类中有两个algorithm，则可以使用所涉及的常量进行比较。
但即使对于不同的O类，常量也很重要。 例如，对于多数字或大整数乘法，朴素algorithm是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）））。 但是，每个较快的algorithm都有一个反映在大常量中的越来越大的开销。 所以为了得到近似的交叉点，需要对这些常数进行有效的估计。 因此，如SWAG所示，最多n = 16的幼稚繁殖最快，最多可达50 karatsuba，从Toom-Cook到Schönhage-Strassen的交叉发生在n = 200。
实际上，交叉点不仅取决于常数，还取决于处理器caching和其他硬件相关的问题。
Big-O符号只是用math函数来描述algorithm的增长率，而不是某些机器上algorithm的实际运行时间。
在math上，令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）最坏情况时间，插入sorting运行在O（n ^ 2）最坏情况时间。但是作为隐藏常数因子在插入sorting比margesorting小，实际上插入sorting可以比许多机器上的小问题尺寸更快地sorting。
没有常量的大O足以进行algorithm分析。
首先，实际时间不仅取决于指令的数量，而且还取决于与代码运行的平台紧密相连的每条指令的时间。 这不仅仅是理论分析。 所以这个常数在大多数情况下是不需要的。
其次，Big O主要用于测量随着硬件性能的提高，随着问题变大或运行时间减less，运行时间将会如何增加。
第三，对于高性能优化的情况，也会考虑常量。
除非input的值非常大，否则现在每天在计算机中执行特定任务所需的时间不需要很长时间。
假设我们想要乘以10 * 10的2个matrix， 除非我们想多次做这个操作，然后渐近符号的作用变得普遍，并且当n的值变得非常大时常数不会真的对答案有什么不同，几乎可以忽略不计，所以我们在计算复杂性的时候往往会把它们留下。
