最佳、最差和平均情況
衡量算法的三種方式
每個算法的代價取決於其輸入。相同大小的兩個輸入可能會產生截然不同的運行時間。複雜度分析形式化了三種看待這種變化的視角。
最佳情況 — Ω (Omega)： 使算法完成最快的輸入。對於線性搜索一個 N 項的列表：Ω(1) — 目標佔據第一個位置。一次比較，完成。
最差情況 — O (Big O)： 使算法完成最慢的輸入。對於線性搜索：O(N) — 目標位於列表的最後，或根本不出現。每個元素都需要檢查。
平均情況 — Θ (Theta)： 假設均勻分佈，所有可能輸入上的預期成本。對於線性搜索，目標等可能地佔據任意 N 個位置之一：Θ(N/2) = Θ(N)。常數 1/2 被丟棄，因為 Theta 表示緊漸近增長，而不是精確係數。
為什麼最差情況佔主導
系統必須處理最差情況。平均耗時 10 毫秒但偶爾需要 60 秒的數據庫查詢會產生用戶可見的故障。工程師為最差情況界限設計，以便無論輸入如何，性能都保持可預測。平均情況分析在概率設置中有價值，但最差情況分析提供保證。
二分搜索情況分析
二分搜索只能在排序數組上工作。在每一步：將目標與中點處的元素進行比較。如果目標等於中點，返回它。如果目標更小，在左半邊遞歸。如果更大，在右半邊遞歸。
每次比較都消除了剩餘候選者的一半。
記憶體增長和時空權衡
計數記憶體，而不是操作
時間複雜度衡量算法執行的操作數。空間複雜度衡量它在輸入之外分配的額外記憶體。這兩者在生產系統中都很重要：一個快速算法如果分配 O(N²) 記憶體將耗盡服務器資源。
O(1) 空間： 常數額外記憶體，與 N 無關。原地排序（例如插入排序）在原始數組內交換元素。它使用幾個臨時變數 — O(1)，無論數組多大。
O(N) 空間： 記憶體與輸入大小成正比。創建一個 N 元素數組的副本需要 N 個插槽。從 N 個字符串的列表構建哈希集合最多存儲 N 個條目。
O(N²) 空間： 記憶體與 N² 成正比。為具有 N 個頂點的圖構建一個 N×N 鄰接矩陣需要 N² 個單元。在 N = 10,000 個頂點時，這是 10^8 個條目 — 一個簡單布爾網格需要數百兆字節。
時空權衡
算法設計中的基本動作之一：用空間換取時間，或用時間換取空間。
哈希表使用 O(N) 額外空間來實現 O(1) 查找。沒有哈希表，掃描列表實現 O(N) 查找，只需要 O(1) 額外空間。哈希表花費記憶體來購買速度。
記憶化存儲先前計算的結果（O(N) 或更多空間）以避免重新計算。沒有記憶化的遞歸斐波那契運行時間為 O(2^N)。有記憶化：O(N) 時間和 O(N) 空間。空間投資指數級縮小時間。
哈希字典與排序列表
比較在 N 個單詞的文檔中計數單詞出現次數的兩種策略：
策略 A： 一個字典（哈希映射）。插入每個單詞；增加其計數。
策略 B： 維護已看到的單詞的排序列表；使用二分搜索在插入前檢查成員資格。
攤銷分析：分散成本
當偶爾的開銷不會破壞平均性能時
有些操作偶爾很昂貴，但在序列中平均成本較低。攤銷分析計算整個序列上每個操作的 平均 成本 — 而不是單個操作的最差情況成本。
動態數組（Python 列表、Java ArrayList）： 以容量 1 開始。滿時，容量加倍。加倍複製所有現有元素：一個附加需要 O(N) 工作。但加倍很少見。在 N 個總附加後，發生了多少總複製操作？
加倍發生在大小 1、2、4、8、...、N/2。複製計數：1 + 2 + 4 + ... + N/2。這是一個幾何級數，在所有 N 個附加中總計為 N − 1 次複製。每個附加的平均複製：(N − 1) / N < 1，所以 O(1) 攤銷每附加 儘管每次加倍有 O(N) 最差情況成本。
為什麼攤銷分析很重要
一個偶爾暫停以調整大小、重新平衡或壓縮結構的系統可能看起來有驚人的最差情況單個操作。攤銷分析揭示了這個警告是錯誤的：罕見的昂貴事件由許多便宜的事件支付。理解攤銷成本可以防止過度設計：為避免罕見的 O(N) 操作而增加複雜性（只貢獻 O(1) 攤銷）是浪費的工作。
更深入： unhamming 課程將複雜度分析應用於生產軟件中的實際缺陷。見 缺失的章節：算法複雜度 & MOAD-0001：沉積缺陷。
哈希表攤銷插入
哈希表從空開始，當負載因子超過 0.75 時容量加倍。插入 1,000 個元素在容量 1、2、4、8、16、32、64、128、256、512 時恰好觸發 10 次加倍。