演算法複雜度與大O符號

讓我們討論演算法複雜度，特別是在演算法的背景下如何衡量複雜度。

不同的演算法在解決相同問題且輸入相同的情況下，需要不同的時間來解決問題。

有時候，這個差異非常巨大，特別是當它們需要處理的元素數量增加時。

這種複雜度被稱為大O符號，沒有別的原因，只是因為我們通常使用大寫字母O來表示：O(n)、O(1)等等。

最常見的大O符號度量，按效率從高到低排列，是：

• O(1)
• O(log n)
• O(n)
• O(n * log n)
• O(n^2)
• O(n!)

其中n是輸入的數量。例如，如果你需要對2個項目進行排序，則n為2；如果你需要對20,000個項目進行排序，則n為20,000。

但你不需要將值替換到O()的計算中。那只是一個符號，旨在向開發人員和查看演算法的任何人傳達它的效率。

具有O(1)效率的演算法是我們能找到的最佳演算法。執行所需的時間不取決於輸入的數量，它總是花相同的時間來執行。

具有O(n)的演算法與輸入的數量呈線性縮放。如果對於10個項目，它需要1秒，那麼對於100個項目，它將需要10秒。

具有O(n^2)的演算法，如果對於4個項目需要16秒，那麼對於10個項目將需要100秒。

在接下來的課程中，我們將分析和計算許多演算法的大O效率。

重要的是要注意，大O符號並不能給我們所有判斷一個演算法是否比另一個更快所需的所有信息，特別是當它們的大O值相同時。在這種情況下，你需要使用其他工具來測試效率。

但是，當演算法有不同的類別（例如O(n)與O(n^2)）時，毫無疑問。

tags: [“algorithm complexity”, “big O notation”, “efficiency”, “algorithm analysis”]