3

私はちょうど質問への答えを書きました：

最長の共通部分列: なぜこれが間違っているのですか?

この関数は、2 つの文字列の間で最も長い部分文字列を見つけることになっていますが、最悪の場合の実行時間とそれを引き起こす入力を突き止めようとすると、わからないことに気付きました。コードは C 疑似コードであると考えてください。

// assume the shorter string is passed in as A
int lcs(char * A, char * B)
{
  int length_a = strlen(A);
  int length_b = strlen(B);

  // This holds the length of the longest common substring found so far
  int longest_length_found = 0;

  // for each character in one string (doesn't matter which), look for 
  //   incrementally larger strings in the other
  // once a longer substring can no longer be found, stop
  for (int a_index = 0; a_index < length_a - longest_length_found; a_index++) {
    for (int b_index = 0; b_index < length_b - longest_length_found; b_index++) {

      // check the next letter until a mismatch is found or one of the strings ends.
      for (int offset = 0; 
           A[a_index+offset] != '\0' && 
             B[b_index+offset] != '\0' && 
             A[a_index+offset] == B[b_index+offset]; 
           offset++) {          
        longest_length_found = longest_length_found > offset ? longest_length_found : offset;
      }
    }
  }
  return longest_found_length;
}

これまでの私の考えは次のとおりです。

以下では、A B Aと言う必要がないように、A と B はほぼ同じサイズであると仮定します。単に n^3 とだけ言います。これがひどく悪い場合は、質問を更新できます。

コードにいくつかの最適化がなければ、ランタイムはN^3 ランタイムのA B A になると思います。

ただし、文字列が類似しておらず、長い部分文字列が見つからない場合、最も内側の for ループは定数にドロップアウトし、A*B が残りますよね?

文字列がまったく同じである場合、各文字列を同時に通過するパスは 1 つだけであるため、アルゴリズムは線形時間かかります。

文字列が類似しているが同一ではない場合、longest_length_found は A または B の小さい方のかなりの割合になり、N^3 の要因の 1 つを分割して N^2 になりますよね? 私は、それらが非常に似ているが同一ではない場合に何が起こるかを理解しようとしています.

声に出して考えてみると、最初の文字に、A の長さの約半分の長さの部分文字列が見つかったらどうなるでしょうか。これは、最初のループの A/2 反復、B-(A/2) 反復を実行することを意味します。 2 番目のループの、そして 3 番目のループで最大 A/2 反復 (文字列が非常に似ていると仮定) まで、より長い部分文字列を見つけることなく。文字列の長さがほぼ等しいと仮定すると、N/2 * N/2 * N/2 = O(N^3) になります。

この動作を示すサンプル文字列:

A A A B A A A B A A A B A A A B

A A A A B A A A A B A A A A B A

私は近くにいますか、それとも何かを見逃しているか、何かを誤って適用していますか?

トライ/プレフィックス ツリーを使用すればもっとうまくやれると確信していますが、繰り返しになりますが、この特定のコードの動作を理解することに本当に興味があります。

4

2 に答える 2

1

コメントでロリウが言ったことは、大金を払っていると思います。あなたのアルゴリズムはO(N 3 )で、ベストケースはO(N 2 )だと思います。

私が実際に指摘したかったのは、このアルゴリズムが甘やかされすぎていることです。おわかりのように、各文字列のすべての可能な開始オフセットについて、後続のすべての一致文字をテストして、一致数をカウントします。しかし、次のようなことを考えてみてください:

A = "01111111"
B = "11111110"

ほとんど最初に見つけるのは、A[1]とで始まる最大一致部分文字列B[0]です。その後、 で始まる正確なオーバーラップの部分をテストしA[2]ますB[1]... ここで重要なのは、相対オフセットです。これを実現することで、アルゴリズムのN 3部分を完全に削除できます。次に、配列の 1 つを他の配列の下にシフトすることが問題になります。

A         01111111
B  11111110
B   11111110
B    11111110
B        ... -->
B                11111110

コードの複雑さを軽減するために、システムの半分だけをテストしてから、配列を交換して残りの半分をテストできます。

// Shift B under A
A  01111111
B  11111110
B      ... -->
B         11111110

// Shift A under B
B  11111110
A  01111111
A      ... -->
A         01111111

これを行うと、O((A+B-2) * min(A,B) / 2)、またはより便利にはO(N 2 )のようなものになります

int lcs_half(char * A, char * B)
{
    int maxlen = 0, len = 0;
    int offset, i;
    for( offset = 0; B[offset]; offset++ )
    {
        len = 0;
        for( i = 0; A[i] && B[i+offset]; i++ )
        {
            if( A[i] == B[i+offset] ) {
                len++;
                if( len > maxlen ) maxlen = len;
            }
            else len = 0;
        }
    }
    return maxlen;
}

int lcs(char * A, char * B)
{
    int run1 = lcs_half(A,B);
    int run2 = lcs_half(B,A);
    return run1 > run2 ? run1 : run2;
}
于 2013-05-20T03:26:21.437 に答える
1

そのため、コメントでそれについて話し合った後、問題はコードの最悪の場合のランタイムを見つけることであることに同意しました。少なくともOmega(n^3)次の証拠があると主張できます。

という
A = aaaa...aabb...bbbb意味で、と|A| = nで構成されています。どこで。n/2 an/2 b
B = aaaa....|B| = n

ここn/2で、最も外側のループの最初の反復 (つまり、文字列の最初のn/2開始インデックスA) を検討します。最も外側のループのi最初の反復のいくつかの反復を修正します。n/22 番目のループの上限は、少なくとも n-n/2 = n/22 つの文字列の LCS が length であるためn/2です。2 番目のループの反復ごとに、長さの文字列を照合しますn/2 - i(これは矛盾によって証明できます)。したがって、n/2最も外側のループの最初の繰り返しの後、次の行になります。

longest_length_found = longest_length_found > offset ? longest_length_found : offset;

実行しました:

n/2*(n/2) + n/2*(n/2-1) + n/2*(n/2-2) + ... + n/2*(2) + n/2*(1) = n/2*Omega(n^2) = Omega(n^3)

具体的には、最も外側のループの最初の反復では、 string にn/2 aの文字列Aがあり、 にn/2開始点がありBます。開始位置ごとBに、長さの完全な共通部分文字列に一致しますn/2(つまり、その行n/2時間に到達します)。というわけでn/2*(n/2)。最も外側のループの次の反復では、 string にn/2-1 aの文字列Aがあり、 にはまだn/2開始点がありBます。この場合n/2-1、各開始インデックスの長さの共通部分文字列に一致します=> n/2(n/2-1)。同じ引数が まで帰納的に機能しi = n/2ます。

n/2とにかく、入力に対するアルゴリズムの実行時間は、最も外側のループの最初の反復の実行時間よりも長いことがわかっているので、それもOmega(n^3).

于 2013-05-20T04:02:49.860 に答える