dev*_*ium 6 big-o time-complexity asymptotic-complexity
如果我有一个需要4n ^ 2 + 7n动作才能完成的算法,它的O是什么？O(4N ^ 2)？为O(n ^ 2)？
我知道7n被切断,但我不知道是否应该保留n ^ 2系数.
谢谢
Mic*_*ray 14
您应该删除任何系数,因为问题实际上是"按顺序",它试图将其表征为线性,指数,对数等等.也就是说,当n非常大时,系数不太重要.
这也解释了为什么你放弃+ 7n,因为当n非常大时,该术语对最终答案的意义相对较小.如果你熟悉微积分,你可能会说limn-> inf(4*n ^ 2 + 7n)〜= lim n-> inf(4*n ^ 2)〜= lim n-> inf(n ^ 2)
您也可以从图形意义上考虑这个问题......也就是说,如果您将函数4n ^ 2 + 7n绘制为更大和更大的n值,则数学家可能会说"它看起来像n ^ 2".当然,它必须是一个相当自由的数学家,因为这不是一个严格的陈述,但这基本上是O(...)试图传达的.
阅读或撰写算法复杂性的每个人都应该确切地知道Landau符号和渐近符号是什么,否则他们并不真正理解正在发生的事情,或者只是有一个近似的(通常是误导性的)想法.
为了简化(很多),让f和g是两个功能f : N -> N和g : N -> N.我们说,f is O(g)当且仅当有一个常数M > 0这样|f(n)| < M|g(n)|,对所有n > M.也就是说,更加非正式地,从大值开始n,所有值f(n)都小于倍数g(n)(即,g 增长快于f).
这个定义相当于
f is O(g) <==> There is K >= 0 such that lim{n -> +oo} |f(n)|/|g(n)| = K
所以,让我们采取f(n) = 4n^2 + 7n并g(n) = n^2尝试证明f is O(g)(我将省略{n -> +oo}):
lim |f(n)|/|g(n)| = lim f(n)/g(n) = lim (4n^2 + 7n) / n^2 = 4 + lim 7n/n^2 =
= 4 + lim 7/n = 4 + 0 = 4
这意味着存在M这样的n > M ==> |f(n)| < M|g(n)|,因此f is O(g).
所以在技术上说4n^2 + 7n is O(4n^2),正确的说4n^2 + 7n is O(n^3),4n^2 + 7n is O(e^n)等等是正确的.但要有意义,我们对下限感兴趣.因此,如果f is O(e^n)和f is O(n^2),我们更有兴趣知道这一点f is O(n^2),因为这更具限制性.
在选择算法时极为重要的是要理解大O符号是指渐近情形,也就是说,当您考虑极其难以想象的巨大输入时,它们可以远远超出已知宇宙中可用的计算能力(即无限大)输入集,用数学表示{n -> +oo}).
对于实际应用(即,没有那么大的输入),在选择算法时,当然,您将观察候选算法的大O符号,但您必须确保所选算法适合您(并且表现更好)适合您(预期) )输入.
最后,通常更好的执行算法更难以理解和正确实现.在选择算法时你也必须考虑这个事实(也就是说,我花在调试和修复这个算法的时间上的时间远远超过我需要等待另一个算法的时间,用更糟糕的大O符号？如果是这样,你应该考虑更简单,效率更低的算法,因为整体解决方案会更有效率).
它是O(n ^ 2).常数因素"进入O".你只保留最大的指数,因为这是一个主导.并且你可以省去系数,因为在比较不同的算法时,甚至非常大的系数导致总数小于具有更大指数(n足够大)的总数.