ソートされたリストを一定時間に追加/更新することはできますか？

Question

（1,7,13,14,50）のようにすでにソートされている整数のリストが与えられたとします。リストには重複が含まれないことに注意してください。

これを保存できるデータ構造がありますが、一定の時間内に新しい要素（適切な場所に）を追加できますか？ add（10）は（1,7,10,13,14,50）を返します。

同様に、（7から19に変更するなど）要素を更新し、それに応じて一定の時間内に順序を変更することはできますか？ （7,19）利回り（1,13,14,19,50）を変更する。

クラスの場合、できるだけ早くこれらの操作を実行するデータ構造を記述する必要がありますが、一定の時間を実行できるかどうかを知りたければ、理想的な実行時間は何ですか？

Answer 1

これは、一定時間O（1）で挿入するには、データ構造のいずれかの場合にのみ最適なケースとして発生します。ハッシュテーブルは一般的に挿入時間が最適ですが、衝突があり、別々の連鎖がある場合、常にO（1）になるとは限りません。複雑さが無限になるように、ハッシュをソートしないでください。

バイナリツリーは挿入時間が長く、ボーナスとして、新しいノードを挿入するときに既にソートされています。しかしこれは平均O（logn）時間を要する。ツリーが空の場合、挿入するための最良のケースはO（1）です。一般的にはhttp://bigocheatsheet.com/

Answer 2

：

者は、これらの操作の複雑さに関する詳しい情報は、こちらを参照して、ほんの一例でしたか？いいえ。新しい要素を挿入する場所や挿入後にリストを並べ替える場所を決定するには、リストの内容の分析を実行する必要があります。リストの要素の読み込み（一般的にはリストの長さの一部を繰り返します） 。これは（一般的に）これは、リスト内にいくつの要素があるかに依存します。定義によると定数ではありません。したがって、特別な場合を除いて、一定時間ソートされたインサートは単に不可能です。

Answer 3

バイナリツリーTreeSetが適切です。 Arrays.binarySearchとArrays.copyを持つ配列は、ここではintを持ち、Integerというラッパークラスは必要ありません。

本物の一定時間では、O（1）は、スペースで支払う必要があります。 BitSetを使用してください。 17を追加するには、単に17をtrueに設定します。次のセットビットを見つけるなどの最適化されたメソッドがあります。

しかし、この場所では最適化が本当に必要なのか疑問です。ファイルI/Oは、より多くの報酬を得るかもしれません。