此代码的 运行 时间复杂度是多少？

Question

这段代码的 运行 时间复杂度是多少？

#include <cstdio>
#include <cstring>
int main()
{
    int n, i, l, j, c, ans = 25;
    scanf("%d", &n);
    char x[21], y[21];
    scanf("%s", &x);
    l = strlen(x);
    for(i=1; i<n; i++)
    {
        scanf("%s", &y);
        c = 0;
        for(j=0 ;j<l; j++)
            if(x[j] == y[j])
                c++;
            else
                break;
        strcpy(x, y);
        if(ans > c)
            ans = c;
    }
    printf("%d", ans);
    return 0;
}

我的讲师告诉我这段代码的复杂度是 O(n*n) 但我不相信这个答案，因为内部循环 运行s 字符串长度倍。

Answer 1

main()的运行时间由一些常量时间语句的运行时间和i循环的运行时间组成：

T_main(n, l) ∈ O(1) + T_fori(n, l)

i-loop 正好运行 (n - 1) 次，由一些常量时间语句和 j-loop 的运行时间组成：

T_fori(n, l) ∈ (n - 1) * (O(1) + T_forj(n, l))

j 循环的运行时间取决于数据。在最好的情况下，x 和 y 的第一个字符是不同的，因此：

T_forj_best(n, l) ∈ 1 * O(1)

在最坏的情况下，x 和 y 有 l 个相同的第一个字符，因此：

T_forj_worst(n, l) ∈ l * O(1) = O(l)

这产生：

T_fori_best(n, l)  ∈ (n - 1) * (O(1) + O(1)) = O(n)
T_fori_worst(n, l) ∈ (n - 1) * (O(1) + O(l)) = O(n * l)

和

T_main_best(n, l)  ∈ O(1) + O(n)     = O(n)
T_main_worst(n, l) ∈ O(1) + O(n * l) = O(n * l)