複雜性。爲什麼常量不重要？

有人能以簡單的方式向我解釋爲什麼常量不重要，當談到大O符號？爲什麼添加常量時複雜性保持不變。這不是一個我想更好地理解這個問題的作業問題。讓我直接得到這個大O是爲了看到一個函數的行爲，因爲它接近無窮大的權利？複雜性。爲什麼常量不重要？

我知道了。非常感謝大家。

由於常數是獨立的N：它不改變，即它是恆定的。除非您想縮小比例，否則您需要 – 2012-02-02 03:03:14

複雜性理論無關緊要，只有這個函數如何隨着輸入大小的增長而變化。

常量不會影響函數的行爲，因爲輸入大小根本無限增長。但是，如果您有興趣實際運行某段代碼，那麼您可能會對大量不斷的開銷感興趣，以及該函數如何針對較小的輸入大小執行操作。

複雜性理論與實踐之間的差異。

2012-02-02 03:07:30 Thilo

Big-O符號表示資源使用情況（時間，內存）在項目數發生變化時如何變化。因此，例如，如果我的計算機可以在1秒鐘內對10個項目進行排序，4秒鐘內完成20個項目，並且在9秒內完成30個項目，那麼它就是O（n ²）。

如果我可以在10秒，40秒和90秒分別手動分類這些相同的項目，那麼我仍然是O（n ²），但我的常數因子是10倍大：問題的大小相同我只要電腦十倍就可以了。

2012-02-02 02:58:55

答案是...定義。如果某個函數f(x)是某個函數g(x)的大-O，則意味着f(x)「最終」小於某個常數時間g(x)。（即足夠大的x）。常數的實際值並不重要; 「最終」行爲的位置也沒有 - 只要它足夠大並且足夠大的常量，那麼你就被覆蓋了。

您可以添加常量或任何小於O的東西，這並不重要 - 它全部關於哪個詞增長最快，以及哪個詞在x增長時占主導地位。

2012-02-02 03:03:31

大O解釋了複雜性如何變化作爲輸入變大。你的輸入越大，不重要的常量就越大。例如，當n增加到一百萬或十億時，乘以10就顯得不重要。大O並不是一個精確的度量，它是一種將算法放在一個粗略的複雜類中的方法，所以可以將常量四捨五入，因爲它們對於很大的n值沒有意義。

2012-02-02 03:05:45 nolt2232

實際上，有時常量做事。但是，當我們談到大O符號時，我們正在尋找漸近行爲。常數不影響漸近行爲的原因是因爲具有較快增長曲線的函數將始終以超長增長曲線取代具有較大常量的函數（儘管需要更長的時間才能達到此目的，當然）。

因此我們說常量「無關緊要」，因爲它永遠不會改變曲線之間的漸近關係。

2012-02-02 03:06:15 FatalError

常量在大O符號中並不重要，因爲問題是可伸縮性。

2012-02-02 03:10:18

... – Thilo 2012-02-02 03:11:45

回答