算法複雜度和大O表示法

讓我們討論算法的複雜性,尤其是我們如何在算法的上下文中對其進行度量。

給定要解決的相同問題和相同的輸入,不同的算法需要花費不同的時間來解決問題。

有時,時間會截然不同,尤其是隨著他們需要管理的元素數量的增長。

這種複雜性稱為大O,沒有其他原因,我們使用大寫字母o約定:O(n)O(1)等等。

您將看到的Big 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秒。

在下一課中,我們將分析和計算大量算法的Big O效率。

重要的是要注意,Big O標記不能提供我們判斷一種算法是否比另一種算法更快所需的所有信息,尤其是當它們的Big O值相同時。在這種情況下,您將需要使用其他工具來測試效率。

但是,當算法具有不同的類時(O(n)O(n^2)例如),毫無疑問。