使用O（logN）中的HashMap在節點的鏈表上進行二進制搜索時間複雜度

您可以在時間複雜度爲O（logN）的已排序鏈接節點（對象）列表上執行二分搜索嗎？我知道鏈表不支持直接索引，所以你不能像list [3]或list.get（3）那樣做，所以基本上你需要迭代列表中的所有元素來找到索引中間元素。但是如果你有一個額外的數據結構，比如HashMap（key = index，value = node）呢？這可以工作嗎？使用O（logN）中的HashMap在節點的鏈表上進行二進制搜索時間複雜度

例子：比方說，我們有名單：

1 -> 4 -> 7 -> 9 -> 14 -> 18

，並用於獲得O（1）節點的HashMap：

0 -> 1 
1 -> 4 
2 -> 7 
3 -> 9 
4 -> 14 
5 -> 18

現在，如果我們想找到14我們做：

binarySearch(0,5) : middle = 2 -> get node 7 from the Hashmap. 14 > 7 so -> 
binarySearch(3,5) : middle = 4 -> get node 14 from the Hashmap. 14 == 14 ->Voila

當然，要構建這個散列映射，你必須做N個操作，所以O（N）時間複雜但如果你已經有了HashMap可以工作嗎？

如果是，您不能使用此方法在鏈接列表中使用額外的HashMap在O（nlogn）時間複雜度中進行插入排序嗎？

基本上：

1. for each element (O(n)) 
    2. find the position of the element in the list in O(logN) with binary search that uses the Hashmap to get the element at the middle position in O(1). 
    3. insert the element in the Linked List in O(1) 
    4. insert the (index,element) into the Hashmap in O(1)

O（nlogn）時間複雜度。或者我在做/假設有什麼問題？

來源

2016-11-15 Eman Yalpsid

是的，這樣的事情會奏效。您甚至可以使用數組而不是間接索引的哈希映射。只需在啓動時創建一次索引，並且每當添加或刪除節點時都需要。如果名單不經常改變，那麼這是一個好方法。 –

是的，後來我意識到第一個問題（在二進制搜索中（O（logN）時間複雜度在鏈表上）是愚蠢的，因爲我實際上是在一個數組上進行二分搜索，而不是在鏈表上。插入排序將不起作用，因爲當我在hashmap中插入新對時，我還需要更新hashmap中的其他鍵（索引），這將需要O（N）時間複雜度... –

@EmanYalpsid：聽起來你應該[爲自己的問題寫一個答案]（http://stackoverflow.com/help/self-answer）。:-) – ruakh

這個想法非常好，下面是你如何使它工作：作爲關鍵你可以使用節點的價值。如果列表節點值是唯一的，那麼您可以使用節點作爲哈希映射的值（否則爲節點列表）。因此，您仍然可以像列表中一樣從節點到節點，但您也可以通過O（1）中的值獲取訪問權限。

如果值在插入和刪除時發生更改，但是所有內容都是O（1）或O（c），其中c是列表中重複值的最大數量，則必須更新哈希映射，如果c doesn不依賴於n，那麼即使有重複也是O（1），否則O（n）。

來源

2016-11-15 20:57:05 maraca

使用O（logN）中的HashMap在節點的鏈表上進行二進制搜索時間複雜度

回答

相關問題