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