演算法設計是發展解決問題的數學過程。演算法分析是預測演算法的效能。前面兩章介紹了經典的資料結構（列表、堆疊、佇列、優先權佇列、集合和映射）並應用它們來解決問題。本章將使用各種範例來介紹用於開發高效演算法的常用演算法技術（動態規劃、分而治之和回溯）。

Big O表示法獲得了一個根據輸入大小衡量演算法時間複雜度的函數。您可以忽略函數中的乘法常數和非支配項。假設兩種演算法執行相同的任務，例如搜尋（線性搜尋與二分搜尋）。哪一個比較好？要回答這個問題，您可以實作這些演算法並運行程式以獲得執行時間。但這種方法有兩個問題：

• 首先，許多任務在電腦上同時運作。特定程式的執行時間取決於系統負載。
• 其次，執行時間取決於特定的輸入。例如，考慮線性搜尋和二分搜尋。如果要搜尋的元素恰好是清單中的第一個元素，線性搜尋將比二分搜尋更快找到該元素。

透過測量演算法的執行時間來比較演算法是非常困難的。為了克服這些問題，開發了一種理論方法來分析獨立於計算機和特定輸入的演算法。這種方法近似改變輸入大小的影響。透過這種方式，您可以看到演算法的執行時間隨著輸入大小的增加而增加的速度，因此您可以透過檢查兩個演算法的成長率。

考慮線性搜尋。線性搜尋演算法將鍵與陣列中的元素順序進行比較，直到找到鍵或陣列耗盡。如果鍵不在陣列中，則需要對大小為 n 的陣列進行 n 比較。如果鍵在陣列中，則平均需要 n/2 次比較。此演算法的執行時間與數組的大小成正比。如果將陣列大小加倍，則比較次數也會加倍。該演算法以線性速率增長。成長率的數量級為n。計算機科學家使用大 O 符號來表示「數量級」。使用此表示法，線性搜尋演算法的複雜度為 O(n)，發音為「n階」。我們將時間複雜度為 O(n) 的演算法稱為線性演算法，並且它呈現線性成長率。

對於相同的輸入大小，演算法的執行時間可能會有所不同，具體取決於輸入。導致執行時間最短的輸入稱為最佳情況輸入，導致執行時間最長的輸入稱為最壞情況輸入。最佳案例分析和
最壞情況分析是分析演算法的最佳情況輸入和最壞情況輸入。最好情況和最壞情況分析不具代表性，但最壞情況分析非常有用。您可以放心，演算法永遠不會比最壞情況慢。
平均情況分析嘗試確定相同大小的所有可能輸入之間的平均時間量。平均情況分析是理想的，但很難執行，因為對於許多問題來說，很難確定各種輸入實例的相對機率和分佈。最壞情況分析比較容易進行，所以一般都是針對最壞情況進行分析。

如果您幾乎總是在尋找清單中已知的內容，則線性搜尋演算法在最壞情況下需要n 次比較，在平均情況下需要n/ 2 次比較。使用 Big O 表示法，兩種情況都需要 O(n) 時間。乘法常數 (1/2) 可以省略。算法分析的重點是成長率。乘法常數對成長率沒有影響。 n/2 或 100_n_ 的成長率與 n 相同，如下表 成長率 所示。因此，O(n) = O(n/2) = O(100n).

考慮在 n 個元素的陣列中尋找最大數字的演算法。如果n為2，則需要比較一次才能找到最大數；如果n為3，則進行兩次比較。一般來說，需要 n - 1 次比較才能找到 n 個元素清單中的最大數量。演算法分析適用於大輸入量。如果輸入量很小，那麼估計演算法的效率就沒有意義。隨著 n 變大，表達式 n - 1 中的 n 部分在複雜性上占主導地位。大 O 表示法允許您忽略非主導部分（例如，
中的 -1 表達式 n - 1）並反白顯示重要部分（例如，表達式 n - 1 中的 n）。因此，此演算法的複雜度為O(n)。

Big O 表示法根據輸入大小估計演算法的執行時間。如果時間與輸入大小無關，則演算法稱為採用恆定時間，符號為O(1)。例如，檢索數組中給定索引處的元素的方法
需要常數時間，因為時間不會隨著陣列大小的增加而增加。

以下數學求和在演算法分析中通常很有用：

時間複雜度是使用 Big-O 表示法來衡量執行時間。同樣，您也可以使用 Big-O 表示法來測量空間複雜度。 空間複雜度衡量演算法使用的記憶體空間量。書中介紹的演算法大多的空間複雜度都是 O(n)。即，它們對輸入大小表現出線性增長率。例如，線性搜尋的空間複雜度為 O(n).