0
for(int i = 1; i < str1.length(); i++)
{
    for(int j = 1; j < str2.length(); j++)
    {
        if(str1[i] == str2[j]) c[i][j] = c[i-1][j-1] + 1;
        else c[i][j] = max(c[i-1][j], c[i][j-1]);
    }
}

これがアルゴリズムです。これの時間複雑度を見つける必要があります。次のように仮定します。

m = str1.length()
n = str2.length()

したがって、明らかに O(m*n) です。

しかし、いくつか質問があります。

  1. 比較と割り当てが 1 時間の複雑さを与えることを考えると、これは本当ですか。

    O( 3*m*n*(3+1+2+2) ) 時間の複雑さ?

  2. 配列を完全に割り当てる必要がある場合、ここで最悪の場合、最良の場合、または平均的な場合の複雑さを数えることは可能ですか?

4

0 に答える 0