DSA 選擇排序時間複雜度

有關時間複雜度的通用解釋，請參閱此頁面。

二分查詢時間複雜度

二分查詢 透過檢查中間值來在已排序的陣列中查詢目標值。如果中間值不是目標值，則線性搜尋會選擇左側或右側的子陣列，並繼續搜尋，直到找到目標值。

要找到二分查詢的時間複雜度，讓我們看看在具有 \(n\) 個值的陣列中查詢目標值需要多少次比較操作。

最佳情況是第一個中間值與目標值相同。如果發生這種情況，目標值會立即找到，只需一次比較，因此在這種情況下時間複雜度為 \(O(1)\)。

最壞情況是搜尋區域必須反覆減半，直到搜尋區域只剩下一個值。發生這種情況時，無論是否找到目標值，都不會影響時間複雜度。

我們來考慮長度為 2 的冪的陣列，例如 2、4、8、16、32、64 等。

在將 2 除以二直到我們只看到一個值之前，需要多少次？只需要一次，對吧？

那 8 呢？我們需要將一個 8 個值的陣列減半 3 次才能得到一個值。

一個 32 個值的陣列必須減半 5 次。

我們可以看到 \(2=2^1\)，\(8=2^3\)，\(32=2^5\)。因此，我們需要減半陣列多少次才能得到一個元素，可以在以 2 為底的冪中找到。另一種看待它的方式是問“我必須將 2 乘以自身多少次才能得到這個數字？”。在數學上，我們可以使用以 2 為底的對數，這樣我們就可以發現長度為 \(n\) 的陣列可以被分成 \( \log_{2}(n)\) 次。

這意味著二分查詢的時間複雜度是

\[ \underline{\underline{O( \log_{2} n )}} \]

平均情況並不那麼容易確定，但是由於我們使用大 O 表示法將演算法的時間複雜度視為最壞情況的上限，因此平均情況並沒有那麼有趣。

如果我們繪製二分查詢在具有 \(n\) 個值的陣列中查詢值所需的時間與線性查詢的比較圖，我們將得到這個圖

二分查詢模擬

執行不同數量值 \(n\) 的陣列的模擬，看看二分查詢找到目標值需要多少次比較

正如您在執行二分查詢模擬時所看到的，即使陣列很大並且我們正在尋找的值未找到，搜尋也只需要很少的比較。