跨越串列
維基百科,自由的 encyclopedia
在電腦科學中,跨越串列是一種數據結構。它使得包含n個元素的有序序列的尋找和插入操作的平均時間複雜度都是,優於陣列的複雜度。
Quick Facts 跨越串列, 類型 ...
跨越串列 | |||||||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
類型 | 串列 | ||||||||||||||||||||
發明時間 | 1989 | ||||||||||||||||||||
發明者 | W. Pugh | ||||||||||||||||||||
用大O符號表示的時間複雜度 | |||||||||||||||||||||
|
Close
快速的查詢效果是通過維護一個多層次的鏈結串列實現的,且與前一層(下面一層)鏈結串列元素的數量相比,每一層鏈結串列中的元素的數量更少(見右下角示意圖)。一開始時,演算法在最稀疏的層次進行搜尋,直至需要尋找的元素在該層兩個相鄰的元素中間。這時,演算法將跳轉到下一個層次,重複剛才的搜尋,直到找到需要尋找的元素為止。跳過的元素的方法可以是隨機性選擇[2]或確定性選擇[3],其中前者更為常見。