【資料結構與算法】複雜度

什麼是算法？

◼ 算法是用于解決特定問題的一系列的執行步驟

◼使用不同算法，解決同一個問題，效率可能相差非常大

如何評判一個算法的好壞？

◼如果單從執行效率上進行評估，可能會想到這麼一種方案

• 比較不同算法對同一組輸入的執行處理時間，這種方案也叫做：事後統計法

◼然而，上述方案有比較明顯的缺點：

• 執行時間嚴重依賴硬體以及運作時各種不确定的環境因素必須編寫相應的測算代碼測試資料的選擇比較難保證公正性

◼一般從以下次元來評估算法的優劣

• 正确性、可讀性、健壯性（對不合理輸入的反應能力和處理能力）

• 時間複雜度（time complexity）：估算程式指令的執行次數（執行時間）
• 空間複雜度（space complexity）：估算所需占用的存儲空間

大O表示法（Big O）

◼一般用大O表示法來描述複雜度，它表示的是資料規模n對應的複雜度

◼忽略常數、系數、低階

• 9 >> O(1)
• 2n+3 >> O(n)
• n^2+2n+6 >> O(n2)
• 4n^3 + 3n^2+22n+100 >> O(n3)

注意：大O表示法僅僅是一種粗略的分析模型，是一種估算，能幫助我們短時間内了解一個算法的執行效率

對數階的細節

◼對數階一般省略底數

log2n = log29 ∗ log9n

是以 log2n、log9n 統稱為 logn

常見的複雜度

◼O(1)< O(logn) < O(n) < O(nlogn) < O(n^2) < O(n^3) < O(2n) < O(n!) < O(n^n)

• 資料規模較小時

  

• 資料規模較大時

  

  ◼一個用于練習算法的好網站

  ​​​https://leetcode.com/​​​​​​https://leetcode-cn.com/​​​