NOTE: 演算法的各種時間複雜度

• 有些情況下基本運算執行次數與輸入大小以及輸入皆有關，例如循序搜尋中，目標值位置就會影響實際執行時間：假設目標 \(x\) 在第一位，那只需要比較一次；\(x\) 不在陣列中就需要比較 \(n\) 次
• 但對另一些演算法而言，基本運算執行次數只與輸入大小有關，這時我們稱存在 \(T(n)\)

對 \(T(n)\) 存在的演算法而言，\(W(n) \equiv T(n)\)

同樣地，只要 \(T(n)\) 存在，則 \(A(n) \equiv T(n)\)。事實上只要 \(T(n)\) 存在就不需要分析剩下的情況了，因為 \(T(n)\) 是一對一的函數。分析 \(A(n)\) 需要對 n 的可能輸入指定機率，例如對循序搜尋法處理不知情況下的陣列，目標 \(x\) 出現在每個位置的機率相等。但有些時候我們知道要處理的資料有特殊分佈，這時候就不能這機率相等的假設。Example:

循序搜尋對目標 \(x\) 在 \(k\) 處的陣列需要執行比較 \(k\) 次，對輸入大小為 \(n\) 的陣列，目標 \(x\) 在每個位置出現機率皆為 \(\frac{1}{n}\)。換句話說循序搜尋有 \(\frac{1}{n}\) 的機率需要執行 \(k\) 次比較，而對所有 \(n\) 分析如下

\[ A(n) = \sum_{k=1}^{n} (k \times \frac{1}{n}) = \frac{1}{n} \times \sum_{k=1}^{n} (k) = \frac{1}{n} \times \frac{n(n+1)}{2} = \frac{n+1}{2} \]

重點：不要把平均時間當成執行時間，尤其在執行時間分佈並不集中時，循序搜尋正是這類案例，因為對所有 \(n\)，任意 \(k\) 值的機率都是一樣的

最佳情況複雜度就是對所有 \(n\) 能輸出的最小值，一樣用循序搜尋法作為案例，最佳情況為 \(x\) 在第一個位置時，此時對所有 \(n\) 執行的比較次數都是 \(1\)。

最佳情況通常不是分析時的重點，除非該演算法具有 \(T(n)\)。通常將精力放在平均情況上，但對特定有時限的任務最差情況分析也很重要。