0

整数要素のシーケンスSが与えられた場合、次のようなインデックス i とインデックス j (両方を含む) の間のシーケンスの最小要素を見つける関数が必要です。nmin(i,j)

  1. 初期化には時間がかかりO(n)ます。
  2. メモリ空間O(n);
  3. min(i,j)かかりますO(log(n))。

このためのアルゴリズムを提案してください。

4

3 に答える 3

0

Segmenttree は、すべての要件を満たすため、必要なものです。

  1. 初期化は、セグメント ツリーで O(n) かかります
  2. メモリもO(n)
  3. クエリは O(log n) で実行できます

これに加えて、ツリーは動的であり、O(log n) での更新をサポートできます。これは、O(log n) の要素 i の要素を変更しても、最小値を取得できることを意味します。

于 2014-09-07T12:50:10.640 に答える
0

セグメント ツリーはまさに必要なものです (時間内に構築できO(n)、1 つのクエリに時間がかかりますO(log n))。これに関する記事は次のとおりです: http://wcipeg.com/wiki/Segment_tree。初期化に時間を使用し、クエリごとに時間
を使用するアルゴリズムがありますが、セグメント ツリーの方がはるかに単純であるため、適切な選択になる可能性があります。O(n)O(1)

于 2014-09-07T12:36:09.053 に答える
0

この TopCoder チュートリアル: An < O(n), O(1) > approachでは、問題についてより詳細に説明しています。表記法では、アプローチがセットアップに f(n) の複雑さを要し、クエリに g(n) の複雑さを要することを意味します。

また、この記事でもアルゴリズムを噛み砕いています: Range Minimum Query <O(n), O(1)> approach (from tree to limited RMQ)。

彼らがあなたの質問を明確にしてくれることを願っています:)

于 2014-09-07T12:23:40.527 に答える