搜尋演算法
維基百科,自由的 encyclopedia
在電腦科學中,搜尋演算法是解決搜尋問題的任何演算法,即檢索儲存在某個數據結構中的資訊,或者在問題的可行域中計算的資訊。這種結構的例子包括但不限於鏈結串列,陣列或搜尋樹。合適的搜尋演算法通常取決於正在搜尋的數據結構,並且還可能包括有關數據的先前知識。搜尋還包含查詢數據結構的演算法,例如SQL SELECT命令[1]。
![]() |
搜尋演算法可以根據搜尋機制進行分類。線性搜尋演算法以線性方式檢查每個與目標關鍵字關聯的記錄。二分或折半搜尋(二分尋找演算法)重複定位搜尋結構的中心,並將搜尋空間分成兩半。比較搜尋演算法通過基於鍵的比較相繼地消除記錄來改進線性搜尋,直到找到目標記錄為止,並且可以按照定義的順序應用於數據結構。數字搜尋演算法基於使用數字鍵的數據結構中的數字屬性工作。最後,雜湊根據雜湊函數直接將鍵對映到記錄。線上性搜尋之外進行搜尋需要以某種方式對數據進行排序。此外,使用了啟發式資訊的方法稱為啟發式搜尋。
搜尋功能常根據其複雜性或最大理論執行時間進行評估。例如,二分尋找演算法的最大複雜度為,即對數時間複雜度,這意味着尋找搜尋目標所需的最大操作次數是搜尋空間大小的對數函數。其它評估方式包括完備性、空間複雜性、最佳性。