真的很困惑時間複雜

Question

我知道如何計算每個算法的bigO，一般來說，它是如何工作的。例如，在鏈表中找到一個特定的數字就是O（N），因爲你可能需要從頭到尾遍歷鏈表中的每個輸入。然而，bigO實際上對於時間意味着什麼？即使插入排序具有更快的「時間複雜度」，合併排序的運行速度還是可以比插入排序快嗎？請給我你的意見，所以我可以理解。非常感謝你。

Answer 1

有一個看看這個例子：

比方說你有兩個算法A₁和A₂。這樣做，但第一個複雜度爲Θ(n)，第二個複雜度爲Θ(n²)。兩種算法都有不同的運行時間。您無法從複雜性中計算運行時間，因爲它取決於具體的實現方式，運行的計算機，複雜性和其他方面無法看到的東西。但是，您可以通過複雜性預測運行時間的變化。 假設您將輸入從長度n更改爲長度2n，表示您將輸入長度加倍。那麼運行時間也應該（幾乎）爲A₁的兩倍，但它應該是A₂以上的約4倍，因爲(2n)² = 4n²。

要解決插入排序與合併排序示例： 插入排序的複雜性爲O(n²)，合併排序的複雜度爲O(n log n)。所以合併排序比插入排序有更好的複雜性，並且運行速度也應該更快。可能（對於非常短的列表）插入排序運行速度比合並排序快，因爲合併排序有一個更大的常數因子隱藏在大O符號中。

Answer 2

您遇到的問題/問題在初學者級別非常普遍。我建議你閱讀更多有關「漸近符號」的內容（網絡上有很多有用的視頻和網站可以解釋這一點）漸近分析正在考慮將算法應用於大型數據庫時的性能。 漸近概念基本上是三種類型 -

1. 大O
2. 大歐米茄
3. 西塔的時候，我們有一個漸近上限

大O使用，這是 大當存在正的常數c和n時，g（n）的O等於f（n）{O（g（n））= f（n）}，使得 = f（n）< = cg ）對於所有n> = n0。 （也就是你以這樣的方式，你的曲線F（N）始終位於或低於該點定義了一個最大值。

大歐米茄使用時，我們有一個漸近下界

和當我們有兩者的上限和下限西塔使用。

現在，回到你的question-插入排序有一個O（N²）的複雜性和歸併排序爲O（n log n）的。在大數值（n 2）往往比（n log n）大。
可以說n = 100。
in insertion sort t他的值將是10000和
合併排序它將是（100日誌100）100.2 - > 200。

因此，您可以看到合併排序的運行速度比插入排序快很多。