1

整数値を持つ NxM 行列の場合、0 <= x1<=x2 < M および 0 <= y1 <= y2 < N である領域 (x1,y1) (x2,y2) の最小要素を見つける最も効率的な方法は何ですか?

さまざまな地域に対して何度もクエリを実行すると想定できます。

範囲最小クエリ メソッドをこの質問に拡張できるかどうか疑問に思っています。 http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=lowestCommonAncestor

非常に簡単な解決策は、RMQ（セグメントツリー）の最も効率的な解決策を使用してから、行または列ごとに適用することです。

最悪の場合の複雑さは min(N,M)*log(max(N,M)) になります

それでも、私たちはそれよりもうまくやれると信じています。

4

3 に答える 3

2

マトリックスの内容や保存方法に関する他の情報がないため、特定の領域のすべてのエントリをスキャンする以外に提案を行うことはできません。それはO（（x2-x1）*（y2-y1））です。あなたの質問は曖昧すぎて他に何も述べることができません。

たとえば、要素が何らかの方法でソートされていることがわかっている場合など、マトリックスについて何か他のことを知っていれば、おそらく（確率的には、平均的な場合）もっとうまくいく可能性があります。

于 2013-01-09T21:09:16.637 に答える
2

それは、「最も効率的な方法」が何を意味するかによって異なります。クエリ時間自体、または前処理時間、またはメモリ要件を最小限に抑えることができます。

クエリ時間のみを最小限に抑える必要がある場合、「最も効率的な方法」は、可能なすべての領域を事前に計算することです。次に、各クエリは、事前に計算された値を返すことによって処理されます。クエリ時間は O(1) です。メモリと前処理時間の両方が膨大です: O((NM) 2 )。

より実用的なのは、OP で参照されているページからスパース テーブル アルゴリズムを使用することです。このアルゴリズムは、すべての 2 のべき乗長間隔のテーブルを準備し、これらの間隔のペアを使用して範囲最小クエリを処理します。クエリ時間は O(1) です。メモリと前処理時間は O(N log N) です。また、このアルゴリズムは簡単に 2 次元の場合に拡張できます。

2D のスパース テーブル アルゴリズム

長さが 2 の累乗で高さが 2 の累乗の四角形のテーブルを用意し、これらの四角形を 4 つ使用して範囲最小クエリを処理します。結果は、これらの各長方形の最小 4 つの最小値になります。クエリ時間は O(1) です。メモリと前処理時間は O(NM*log(N)*log(M)) です。

この論文: Amihood Amir、Johannes Fischer、Moshe Lewenstein による「Two-Dimensional Range Minimum Queries」では、このアルゴリズムのメモリ要件と前処理時間をほぼ O(MN) に減らす方法が提案されています。

この論文: Hao Yuan と Mikhail J. Atallah による「多次元配列の範囲最小クエリのデータ構造」は、O(1) クエリ時間と O(NM) メモリと前処理時間で異なるアルゴリズムを提供します。

于 2013-01-10T14:59:02.413 に答える
0

擬似コード：

function getMax(M, x1, x2, y1, y2)
    max = M[x1,y1]
    for x = x1 to x2 do
        for y = y1 to y2 do
            if M[x,y] > max then max = M[x, y]
    return max

これは入力サイズのO（n）であり、行列領域のサイズ（x2-x1）*（y2-y1）としてのみ合理的に解釈できます。最小値が必要な場合は、maxをminに、>を<に変更します。O（n）よりも優れた方法はありません。つまり、考えられる各要素をチェックします。O（n）よりも高速なアルゴリズムがあると仮定します。次に、すべての要素をチェックするわけではありません。アルゴリズムの失敗ケースを取得するには、チェックしない要素の1つを取得し、それを（max + 1）に置き換えて、アルゴリズムを再実行します。

于 2013-01-09T21:08:59.350 に答える