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

2 years ago

source link: https://dannypsnl.github.io/blog/2020/05/12/cs/algorithm-time-complexity/
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.

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

演算法時間複雜度分析：對每個不同的輸入大小，其基本運算所執行的次數

所有情況時間複雜度 T(n)T(n)T(n)

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

最差情況時間複雜度 W(n)W(n)W(n)

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

平均情況時間複雜度 A(n)A(n)A(n)

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

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

A(n)=∑k=1n(k×1n)=1n×∑k=1n(k)=1n×n(n+1)2=n+12A(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}A(n)=k=1∑n(k×n1)=n1×k=1∑n(k)=n1×2n(n+1)=2n+1

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