Временная сложность поиска этого префикса

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.

Обратите внимание, что если ваши строки говорят между 1 млн и 2 млн символов длиной,
но ваша п просто сказать, 20 или 50 или 100, то K и эта оценка
должна интерпретироваться с осторожностью. Обычно можно было бы ожидать n >> K, хотя,
Я думаю, это то, что вы имели в виду.