O（n*n）…（nlognまたはn）未満でこれを計算できますか

https://stackoverflow.com/questions/3659506

01-10-2019
|

質問

これは非常に有名なMNCから私に尋ねられた質問です。質問は次のとおりです...

0と1の2D n*n配列を入力します。 a（i、j）= 1の場合、ith行に対応するすべての値とjth列が1になります。

例として、配列がある場合

出力を取得する必要があります

入力マトリックスはまばらになります。

これはO（n^2）未満で可能ですか？

別の条件は追加のスペースが提供されていません。スペース<= o（n）を使用して複雑さを達成する方法があるかどうかを知りたいです。

PS：O（n*n）の複雑さを与える答えは必要ありません。これは宿題の問題ではありません。私は多くのことを試みましたが、適切な解決策を得ることができず、ここでいくつかのアイデアを得ることができると思いました。複雑さのために印刷を脇に置いてください

私の大まかなアイデアは、移動した要素の数を動的に排除して、それらを約2n程度に制限することでした。しかし、私は適切なアイデアを得ることができませんでした。

解決 7

hii guys、

MB14からのコメントのおかげで、私はそれをO以下で解決できると思います（nn）時間...最悪の場合はO（nn）...

実際、指定された配列が想定されています

サイズnの2つの配列（これは最悪の場合）を持っています... 1つは行やその他の列のインデックスのインデックスに専念しています... [i] [1] = 0を1つの配列に入れてから[1] ] [j] = 0別の。

次に、これらの値のみを取得し、2列目とコロンをチェックします...この方法で、わずか0しかない行とコロンの値を取得します。

行アレイの値の数は、結果アレイの0の数を与え、ポイントA [Row-Array値] [列配列値]がそれらのポイントを与えます。

以下で解決できます（nn）そして最悪はo（nn）...私たちが見ることができるように、（サイズn）の配列は減少します...

私はこれをいくつかのアレイで行い、それらすべての結果を得ました... :)

私がどこでも間違っているなら私を修正してください...

すべてのコメントのみんなに感謝します...あなたはすべてとても親切で、私は途中でかなりのことを学びました... :)

他のヒント

最悪の場合、出力を生成するためにn * n -nビットを0から1に切り替える必要がある場合があります。 O（n*n）にかなり詰まっているようです。

私はあなたが最良のケースのためにそれを最適化できると想像しますが、あなたの最悪のケースはまだo（n*n）であると言いたいと思います：あなたの最悪のケースはすべての0の配列です、そしてあなたはあなたが調べなければならないでしょうすべての要素。

最適化には、「1」を見つけたらすぐに行または列をスキップすることが含まれます（詳細を提供できますが、O（n*n）は気にしないと言いましたが、メタデータがない限り、行/列全体が空であるか、複数のフィールドを一度にチェックするSIMDスタイルの方法がない限り（たとえば、すべての行が4で揃っていて、32ビット価値データを読むことができます。ビットマスク）、あなたは常に全ゼロ配列の問題に対処する必要があります。

明らかに、出力マトリックスもその否定バージョンもスパースでなければなりません（最初の行の半分が1に設定されているマトリックスを1つに、0に見るために0にしてください）。したがって、時間は出力に使用できる形式に依存します。（入力は要素のリストまたは同等のもののリストであると仮定しています。そうしないと、マトリックスがまばらであることを活用できなかったからです。）

O（M+N）空間と時間の単純なソリューション（Mは入力マトリックス内のものの数です）：長さnで満たされた2つのアレイを取り、入力内のすべてのものを反復し、それぞれxをドロップする最初のアレイから、2番目の配列からyから調整します。出力は2つの配列であり、結果マトリックスを明確に定義します。ITS（x、y）座標は0の場合、最初の配列のx座標と2番目のy座標は0です。

アップデート： 言語に応じて、同じ行を複数回参照することにより、通常の2D配列を返すためにいくらかのトリックを使用できます。たとえば、PHP：

// compute N-length arrays $X and $Y which have 1 at the column 
// and row positions which had no 1's in the input matrix
// this is O(M+N)
$result = array();
$row_one = array_fill(0,N,1);
for ($i=0; $i<N; $i++) {
    if ($Y[$i]) {
         $result[$i] = &$row_one;
    } else {
         $result[$i] = &$X;
    }
}
return $result;

もちろん、これはあなたがそれを書こうとしない限り、通常の配列です。

マトリックスのすべてのエントリをチェックする必要があるため、最悪の場合は常にn*nになります。

小さな2*nの追加ストレージを使用すると、O（n*n）で操作を実行できます。各行のマスクと各列の別のマスクを作成するだけです - 配列をスキャンして、行くときにマスクを更新します。次に、再度スキャンして、マスクに基づいて結果マトリックスを入力します。

入力マトリックスが変更されていることをしている場合は、入力の各行と列のゼロ以外のエントリのカウントを（単純なマスクではなく）保存できます。次に、入力のエントリが変更されたら、それに応じてカウントを更新します。その時点で、出力マトリックスを完全にドロップし、出力マトリックスを維持するのではなく、マスク/カウントを直接照会します（これは、n未満で変化するように更新することもできます。n時間を維持したい場合は時間）。したがって、初期マトリックスをロードするとo（nn）しかし、更新ははるかに少ないかもしれません。

入力マトリックスはまばらな場合がありますが、スパース形式で取得できない限り（つまり、 (i,j) 最初に設定されたペア）、入力を読むだけでω（n^2）時間が消費されます。入力がまばらであっても、o（n^2）出力を書き込むのは簡単です。チートとして、セット行のリストとセット列のリストを出力することを許可された場合、線形時間に到達することができます。アルゴリズムが実際に「はい」や「いいえ」よりも重要な結果を生成する必要がある場合、魔法はありません。

別の答えに対するMcDowellaのコメントは、別の代替入力形式であるRun-Length Encodingを示唆しています。スパース入力の場合、それは明らかにそれを読むのにO（n）時間以下では必要ありません（0から1の間にある遷移の数を考慮してください）。しかし、そこから故障します。次のように構成された入力マトリックスを考えてみましょう。

0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 . . . 
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 . . .
.     .
.       .
.         .

つまり、最初の行で0と1を交互に、他のどこでも0を交互にします。あるので、明らかにまばらです n/2 合計で。ただし、RLE出力はすべての行でこのパターンを繰り返す必要があり、O（n^2）出力につながる必要があります。

あなたは言う：

として出力を取得する必要があります...

したがって、n^2要素を持つマトリックス全体を出力する必要があります。これはo（n*n）です。

問題自体はo（n*n）ではありません。マトリックス全体を計算して保存する必要はありません。サイズnのそれぞれ2つのベクトル、lとcのみが必要です。

L [x]は1の場合は1です。xが1つの行、0それ以外の場合は0です。

c [x]は、行xが1つの行の場合、0、それ以外の場合は0です。

初期マトリックスがまばらであるため、これらのベクトルをO（n）で作成できます。入力データはマトリックスではなく、各ゼロ要素の座標（行、列）を含むリストです。このリストを読んでいる間、l [line] = 1およびc [column] = 1を設定し、問題が解決します：m [l、c] == 1 [l] == 1またはc [c] = = 1

明らかにあります O(N^2) やらなければならないこと。マトリックス内

すべてのビットを1に設定する必要があり、 N*(N-1) この5x5ケースでは、1つに設定されていません（20）。

逆に、あなたは常にそれを行うアルゴリズムを思いつくことができます O(N^2) 時間：一番上の行に沿って合計して列をletし、行または列がゼロ以外の回答を取得した場合は、行全体または列に記入します。次に、小さい（n-1）x（n-1）問題を解決します。

したがって、少なくとも必要なケースは存在します N^2 そして、どんなケースでも解決できます N^2 余分なスペースなし。

マトリックスがまばらである場合、複雑さは入力エンコードに大きく依存します。² またはそのようなものですが、あなたの入力の複雑さの点でm^のと出力の複雑さm^アウト. 。 O（n + mのようなものが期待されます^の + m^アウト）しかし、エンコーディングとそれで遊ぶことができるトリックによっては大きくなります。

それはあなたの入力データ構造によって完全に依存します。マトリックス（1Sおよび0S）を2D配列として渡すと、それを通過する必要があります。それはO（n^2）です。しかし、データはまばらであるため、1を入力として渡すだけの場合、それを行うことができます。それはこれに似たものです（以下のPseudocode）：

list f(list l) {
   list rows_1;
   list cols_1;

    for each elem in l {
        rows_1[elem.row] = 1;
        cols_1[elem.col] = 1;
    }

    list result;
    for each row in rows_1 {
        for each col in cols_1 {
             if (row == 1 || col == 1) {
                 add(result, new_elem(row, col));
             }
        }
    } 
   return result;
}

値をチェックしているときは、マトリックスの中心を埋めないでください。要素を通過すると、最初の行と最初の列に対応する要素を1つ設定したとき。その後、戻って記入します。

編集：実際、これはアンディのものと同じです。

データ構造に依存します。

行に可能なケースは2つしかありません。

入力に要素（i、_）がある場合、私は1を満たしています
他のすべての行は同じです。つまり、j番目の要素は1つの場合、入力に要素（_、j）があります。

したがって、結果は、行への参照の配列としてコンパクトに表現できます。 2行しか必要ないので、結果はO（n）メモリのみを消費します。例として、これは次のようにPythonで実装できます。

def f(element_list, N):
  A = [1]*N
  B = [0]*N
  M = [B]*N
  for row, col in element_list:
    M[row] = A
    B[col] = 1
  return M

サンプル呼び出しはそうでしょう

 f([(1,1),(2,2),(4,3)],5)

結果とともに

[[0, 1, 1, 1, 0], [1, 1, 1, 1, 1], [1, 1, 1, 1, 1], [0, 1, 1, 1, 0], [1, 1, 1, 1, 1]]

重要な点は、ここで配列がコピーされないことです。つまり、m [row] = aは単なる参照の割り当てです。したがって、複雑さはo（n+m）で、mは入力の長さです。

#include<stdio.h>

含む

int main（）{int arr [5] [5] = {{1,0,0,0,0,0}、{0,1,0,0,0}、{0,0,0,0,0} 、{1,0,0,1,0}、{0,0,0,0,0,0}}; int var1 = 0、var2 = 0、i、j;

for(i=0;i<5;i++)
   var1 = var1 | arr[0][i];

for(i=0;i<5;i++)
   var2 = var2 | arr[i][0];

for(i=1;i<5;i++)
   for(j=1;j<5;j++)
      if(arr[i][j])
         arr[i][0] = arr[0][j] = 1;

for(i=1;i<5;i++)
   for(j=1;j<5;j++)
          arr[i][j] = arr[i][0] | arr[0][j];

for(i=0;i<5;i++)
   arr[0][i] = var1;

for(i=0;i<5;i++)
   arr[i][0] = var2;

for(i=0;i<5;i++)
{
   printf("\n");             
   for(j=0;j<5;j++)
      printf("%d ",arr[i][j]);
}

getch();

}

このプログラムは、2つの4つの一時変数（var1、var2、i、j）のみを使用しているため、時間の複雑さo（n^2）で一定の空間で実行されます。 O（n^2）。

ライセンス： CC-BY-SA と帰属

所属していません StackOverflow