使用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在节点的链表上进行二进制搜索时间复杂度

回答

相关问题