0

特定の配列の連続したサブ配列を見つけるための FAST メソッドを求めたいと思います。連続したサブ配列の最大合計を探しているのではなく、取得したサブ配列に対して他の操作を実行したいことに注意してください。私はすでに次のアルゴリズムを認識していますが、これは時間の複雑さが非常に低いため、より効率的なアルゴリズムを探しています。

// N = number of elements in array A.
void subarr(int N, int A[]) {
  for (int i = 0; i < N; i++) {
    for (int j = i; j < N; j++) {
      for (int k = j; k < N; k++) {
        cout << A[k] << ' ';
      }
      cout << endl;
    }
  }
}
4

1 に答える 1

0

他の人がコメントで指摘しているように、あなたの例は正しくありません。次のように読む必要があります

for (int i = 0; i < N; i++) {
   for (int j = N-1; j >= i; j--) {
      for (int k=i; k<=j; k++) {
         cout << "A[" << k << "] ";
     }
     cout << endl;
   }
}

出力を文字通り印刷するだけに変更したことに注意してくださいA[k]。これにより、すべてのサブアレイが正確に 1 回出力されます。

あなたの質問に関しては、繰り返しますが、他の人が指摘したように、このアルゴリズムは各サブアレイを1回印刷し、余分な作業は必要ありません。これはあなたがしなければならない作業のほとんど最小量であるため、実行時間を節約できるとは思いません。ネストされた 3 つのループによるオーバーヘッドは確かにありますが、おそらく 3 つすべてが必要です。部分配列は、たとえば次のように指定されます。

  1. その出発点
  2. その終点またはその長さのいずれか

そして、その間にあるものを印刷/切り取る必要があり、3 番目のループが発生します。

于 2015-08-10T10:12:40.337 に答える