O（logN）のHashMapを使用するノードのリンクリストのバイナリ検索時間複雑度

Question

時間複雑度O（logN）のノード（オブジェクト）のソートされたリンクリストに対してバイナリ検索を実行できますか？リンクされたリストは直接インデックスをサポートしていないので、list [3]やlist.get（3）のようなことはできないので、リストのすべての要素を繰り返してインデックスを検索する必要があります中間の要素。しかし、HashMap（key = index、value = node）のような追加のデータ構造を自由に使いたい場合はどうでしょうか？これは動作しますか？

例： のは、我々がリストを持っているとしましょう：

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

とHashMapのは、（1）O内のノードを取得するために使用：

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）時間複雑。あるいは私は何か間違っていると思いますか？

Answer 1

アイデアはかなり良いです、ここであなたはそれを動作させる方法があります：キーとして、ノードの値を使用することができます。リストノードの値が一意の場合、ハッシュマップの値としてノードを使用できます（それ以外の場合はノードのリスト）。だから、リストの中でいつものようにノードからノードに移動することができますが、O（1）の値でアクセスすることもできます。

挿入と削除時に値が変更された場合、ハッシュマップを更新する必要がありますが、すべてがO（1）またはO（c）です.cはリスト内の重複値の最大数です。 nに依存していなければ、それは重複であってもO（1）であり、そうでなければO（n）である。