0

Range Minimum Queries のウィキペディアのリンクを読み、さらにいくつかのチュートリアル (topcoder およびその他のリンク) を見ましたが、非常に基本的な質問があります。

RMQ の正式な定義は次のとおりです: 順序付けられたセット (数値など) から取得されたオブジェクトの配列が与えられた場合、範囲最小クエリ (または RMQ) はサブ配列内の最小要素の位置を要求します。

私が理解できないのは、線形探索で問題を解決できないのはなぜですか? 配列 A[0...n] で、RMQ(i,j) が必要な場合

min = A[i]
index = i
for iter=i; iter <j; iter ++
if A[iter] <= min
min = A[iter]
index = iter;

ループの終わりまでに、最小値と最小値が存在するインデックスがわかります。

私は間違いなくここに何かが欠けています...なぜRMQが必要なのか誰かが理解するのを手伝ってくれますか?

4

2 に答える 2

2

RMQ は、説明した問題を解決することを目的としていますが、アプローチよりもはるかに高速です。いくつかの事前計算を行う静的バージョン (非常に洗練された最も最適化されたバージョンは線形事前計算を行います) と、その後、各クエリに対して常に応答する静的バージョンと、各クエリに対して log(n) 時間を使用する動的アプローチです。

静的な場合は初期配列を変更できませんが、動的な場合はその値が時間とともに変化することが許可されています。

どちらの場合も、大量のクエリに回答することを意図していることに注意してください。これは、定数時間または対数時間で回答すると、線形アプローチよりもはるかに高速になるため、アイデアが遅すぎる場合に機能することを意味します。これがアイデアを説明することを願っています。

于 2012-08-27T13:23:20.537 に答える
1

速度。線形検索は遅いです。

同じ理由で、大規模なデータベースの並べ替えに単純な挿入並べ替えではなく、クイック並べ替え(またはマージ並べ替えなど)を使用します。

巨大なデータベースがあり、RMQ に対して何百万回もクエリを実行するとします。各クエリの線形検索は効率的ではありません。数百万回の線形検索が必要になりますが、より高度なアルゴリズムでは、小さな前処理と必要な情報の高速検索が必要です。

于 2012-08-27T13:21:37.380 に答える