我們如何減少鏈接列表中的搜索時間？

我在職業杯上看過這個問題，但沒有找到比'SkipList'更好的答案。我在維基百科找到的SkipList的描述很有趣，但是，我不理解「幾何/二項分佈」等術語......我讀了它的內容並深入到概率論中。我只是想實現一種更快速搜索的方法。所以這就是我做的： 1.創建索引。 - 我寫了一個函數來創建1000個節點。然後，我創建了一個類型鏈表的數組，並循環遍歷1000個節點，並選取每個第23個元素（我腦海中隨機數）並添加到我稱之爲'index'的數組中。我們如何減少鏈接列表中的搜索時間？

SLL index = new SLL[50]

現在的功能來創建索引：

private static void createIndex(SLL[] index, SLL head){ 
    int count=0; 
    SLL temp = head; 
    while(temp!=null) 
    { 
     count++; 
     temp = temp.next; 
     if((count==23){ 
      index[i] = temp; 
      i++; 
      count=0; 
     } 
    }  
}

現在終於 '發現' 功能。在這個函數中，我首先以769爲例說明輸入元素。我通過'索引'數組並找到索引[i]> 769。因此，現在我將head = index [i-1]和tail = index [i]傳遞給'find'函數。然後，它將搜索769個短的23個元素。因此，我計算出它總共需要43個跳轉（包括數組跳轉和node = node.next跳轉），以找到我想要的元素，否則它會有采取769跳。

請注意：我認爲創建索引數組的代碼不是搜索的一部分，因此我不會將時間複雜度（這太可怕了）與'查找'函數的時間複雜度相加。我認爲這個索引創建應該在創建列表之後作爲一個單獨的函數來完成，或者是及時地完成。就像網頁在谷歌搜索上顯示需要時間。另外，這個問題在微軟的一次採訪中被問到，我不知道我提供的解決方案是否會有好處，或者我是否會看起來像是一個傻瓜提供這樣的解決方案。該解決方案已用Java編寫。等待您的反饋。

來源

2013-04-20 Parikksit Bhisay

這個解決方案不可能在面試過程中幫助你，除非你能清楚地解釋爲什麼這個解決方案沒有提供任何顯着的好處。 – 2013-04-20 20:19:50

所以基本上，這個解決方案沒有提供任何重大的好處嗎？ – 2013-04-20 20:41:17

很難弄清楚你在這裏試圖解決什麼問題，或者你的解決方案應該如何工作。（提示：完整的工作代碼將有助於既！）

然而，有一對夫婦一般的東西，我們可以說：

無法搜索列表數據結構（例如發現在i列表）更好，O(N)除非某種排序已經被放在它上面。例如，對元素進行排序。
如果列表中的元素進行排序，然後將列表是可轉位（即獲得在i位置的元素是O(1)），那麼你可以使用二進制搜索和O(logN)找到的元素。
您無法獲取鏈接列表的位置i處的元素，其效果更好O(N)。

如果添加輔助數據（索引，等等），你可以在潛在的更多的存儲空間爲代價獲得一定的操作...更好的性能，並使得其他一些操作更加昂貴。但是，您不再有列表/鏈接列表。整個數據結構是「別的東西」。

來源

2015-11-01 02:04:28

我們如何減少鏈接列表中的搜索時間？

回答

相關問題