3

行列Aは、行と列でソートされます。ここで、A [i] [j] <A [i] [j+1]およびA[i][j] <A [i +1][j]です。追加情報は、各行の最初の要素が前の行の最後の要素よりも小さいことです。次に例を示します。

⎡1  3   5  17⎤
⎢2  4   6  18⎥
⎣7  9  11  20⎦

そして、この追加情報がO（lgn）の複雑さを決定する上でどのような役割を果たしているのか混乱しています。

私は次のようにO（m）+ O（n）を思い付くことができます：

int search(int mat[4][4], int n, int x)
{
   int i = 0, j = n-1;  //set indexes for top right element
   while ( i < n && j >= 0 )
   {
       if ( mat[i][j] == x )
       {
          printf("\n Found at %d, %d", i, j);
          return 1;
       }
       if ( mat[i][j] > x )
           j--;
       else //  if mat[i][j] < x
           i++;
       }

       printf("\n Element not found");
       return 0;  // if ( i==n || j== -1 )
  }

しかし、私は情報を使用したとは思いません。各行の最初の要素は、前の行の最後の要素よりも小さいです。

誰かplzは私にいくつかのヒントを与えることができますか？さらに、これは宿題ではありません。ありがとうございました！

4

1 に答える 1

1

現在行っているのは、徹底的な検索（つまり、すべての要素を1回チェックする）、つまりO（n * m）です。マトリックスのソートされた性質を利用していません。

ソートされたリストが与えられると、バイナリ検索ではO（lg n）で検索できます。基本的に、リストの中央の要素を確認します。それが目標よりも大きい場合は、リストの後半を無視できることがわかります。要素または検索スペースが1アイテムに等しくなるまで、検索スペースを毎回半分にして、このプロセスを繰り返します。Pythonコードの場合：

import math

def binSearch(value, data):
    bottom = 0 #first entry
    top = len(data) -1 #last entry

    while bottom <= top: #if bottom ever becomes greater than top then the object is not in the list
        i = int(bottom + math.floor((top - bottom)/2)) #find the mid-point
        if data[i] == value: #we found it
            return i
        elif data[i] > value:
            top = i - 1 #value must be before i
        else:
            bottom = i + 1 #value must be after i

    return None #not found

ここで、マトリックス構造から収集できる情報について考えてみましょう。あなたは、あなたが説明したようにソートされた与えられたanxm行列matが、どの行に対しても、iそのmat[i][0]行の最も低い項目でありmat[i][n]、最も高いことを知っています。同様に、任意の列jについて、mat[0][j]はその列の最小値でmat[m][j]あり、最大値です。つまり、mat[i][0] <= value <= mat[i][n]trueでない場合、値を行iに含めることはできません。同様に、mat[0][j] <= value <= mat[m][j]trueでない場合、値を列jに含めることはできません。

したがって、明らかな改善は、値を含む可能性のある各行に対して、二分探索を実行することです。

for row in mat:
    if (row[0] <= value) AND (row[len(row) - 1] >= value): #if the value could possibly be in the row
        result = binSearch(value, row)

        if result: #if we found it
            return result

binSearch()O（lg m）です。最悪のシナリオはbinSearch()すべての行で実行されているため、O（n * lg m）です。

O（lg n * lg m）ソリューションを実装しようとしましたが、理解できません。問題は、マトリックスの左上隅と右下隅しか削除できないことです。左下または右上を削除することはできません。

于 2012-06-19T05:49:17.753 に答える