A1からまでの整数をnランダムな順序で並べた配列です。
少なくともログ時間内にi、最初の要素の th 番目に大きい要素へのランダム アクセスが必要です。j
私がこれまでに思いついたのは、その位置の要素が最初の要素の中で最大のものであるn x n行列です。これにより、一定時間のランダムアクセスが可能になりますが、ストレージが必要です.M(i, j)ijn^2
構成によりM、行と列でソートされます。さらに、各列は隣接する列と 1 つの値だけ異なります。
ランダムアクセス時間以上で、スペースまたはそれ以上に圧縮する方法を誰かが提案できますMか?n log(n)log(n)
O(N log(N)) の前処理時間と O(N log(N)) の余分なスペースを考えると、O(log(N)) 時間でアクセスを実行できると思います。方法は次のとおりです。
赤黒木を拡張して、O(log(N)) 時間select(i)でランクの要素を取得する操作をサポートできます。iたとえば、この PDFまたはIntroduction to Algorithmsの該当する章を参照してください。
select(i)挿入操作が O(log(N)) 個を除くすべてのノードを古いツリーと共有する新しいツリーを返すように、機能的な方法で赤黒ツリー ( をサポートするように拡張されたものでも) を実装できます。たとえば、Chris Okasaki によるPurely Functional Data Structuresを参照してください。
ツリーが最大から最小にソートされた最初の要素のインデックスを格納するTように、純粋に機能的な拡張赤黒ツリーの配列を構築します。T[j]0 ... j-1jA
基本ケース: T[0]1 つのノードのみを持つ拡張赤黒ツリーを作成します。そのデータは、配列の最初の 1 要素の中で 0 番目に大きい要素のインデックスである番号 0Aです。
帰納的ステップ: j1 から までのそれぞれについて、インデックス付きの新しいノードをツリー に純粋に機能的に挿入することにより、増補赤黒ツリーを作成N-1します。これにより、最大で O(log(j)) 個の新しいノードが作成されます。残りのノードは と共有されます。これには O(log(j)) 時間がかかります。T[j]jT[j-1]T[j-1]
配列を構築するための合計時間Tは O(N log(N)) であり、使用される合計スペースも O(N log(N)) です。
が作成されると、 を実行することにより、 の最初の要素T[j-1]の th 番目に大きい要素にアクセスできます。これには O(log(j)) 時間がかかります。初めて必要になったときに遅延作成できることに注意してください。が非常に大きく、常に比較的小さい場合は、時間とスペースを大幅に節約できます。ijAT[j-1].select(i)T[j-1]Aj