0

N * N行列が与えられているので、その大きな行列で考えられるすべての一意の正方行列を見つける必要があります。どうすればそれを高速かつメモリ効率よく達成できますか？

直面している問題：実際に作成されるマトリックスはN-> [2,50,000..3,00,000]であり、各要素は実際にはビット[オン/オフ]または[0/1]としてマークされており、特定の制限（たとえば20、つまりN> = 20）よりも大きいすべての一意の正方行列、および正方行列のすべての要素は1である必要があります。その後、行列のみが以降の処理に使用されます。したがって、基本的に必要です。そのような行列を見つけるために。

4

1 に答える 1

1

アルゴリズムは単純です:

  1. 正方行列の数を数える
  2. この番号でループを使用する
  3. 各行列について 、 、 をi_min計算j_minしi_maxます。j_max特定のサイズの行列を見つけるために、この行列をループするだけです。
  4. i_minデータ範囲、j_min、i_maxをj_max新しい行列にコピーします。

ヒント:正方行列の数は大きな行列サイズに依存します

  • 1x1 -> 1 * (1x1)
  • 2x2 -> 4 * (1x1) + 1 * (2x2)
  • 3x3 -> 9 * (1x1) + 4 * (2x2) + 1 * (3x3)
  • 4x4 -> 16 * (1x1) + 9 * (2x2) + 4 * (3x3) + 1 * (4x4)

ここで四角形のポイントが得られたことを願っています。

注: これには、連続した行/列の組み合わせが含まれます。

于 2012-09-11T09:02:37.133 に答える