java - 该算法查找前缀的时间复杂度

Question

我写的这个算法是为了检查一个字符串是否是数组中另一个字符串的前缀。 复杂度为 O(n*(n-1)*k)，其中 n 是数组中字符串的数量， K是字符串的最大长度。我在进行复杂性分析吗？

public static void isPrefix(String[] strs){

    for(int i=0; i<strs.length; i++){
        for(int j=i+1; j<strs.length; j++){
            String a = strs[i];
            String b = strs[j];

            if(!commonStr(a,b).isEmpty()){
                System.out.println(a + "->" + b);
            }
        }
    }
}

private static String commonStr(String a, String b){
    int smaller = Math.min(a.length(), b.length());
    for(int k=0; k<smaller; k++){
        if(a.charAt(k) != b.charAt(k)){
            return "";
        }
    }
    return a.substring(0,smaller);
}

public static void main(String[] args){
    String[] strs = {"ab", "abc", "cde", "abef"};
    isPrefix(strs);
}

Answer 1

你是对的，我相信。只是K不完全是那。但粗略地说，这样说是可以的。

它也是 K * n * (n-1)/2 因为你没有检查所有
有序的字符串对(你只检查了其中的一半)。
在您的示例中，您检查了 6 对夫妇，而不是 12 对。

请注意，如果您的字符串长度介于 100 万到 200 万个字符之间，
但你的 n 只是说 20 或 50 或 100，然后 K 占上风并且这个估计
应谨慎解释。不过，通常人们会期望 n >> K，
我想这也是您的想法。