Большой O для этого кода

Question

Ниже код с сайта topcoder.Я пытался понять сложность времени для этого кода.1 для цикла и 1 для цикла в методе isRandom и 1 для цикла в методе diff.Я предполагаю, что в худшем случае будет O (n ^ 2).Это верно?

public class CDPlayer { 
private boolean[] used; 

public boolean diff(String str, int from, int to) { 
Arrays.fill(used, false); 
to = Math.min(to, str.length()); 
for (int i = from; i < to; i++) { 
  if (used[str.charAt(i) - 'A']) { 
    return false; 
  } 
  used[str.charAt(i) - 'A'] = true; 
} 
return true; 
} 

public int isRandom(String[] songlist, int n){ 
  String str = ""; 
  for (int i = 0; i < songlist.length; i++) { 
    str += songlist[i]; 
  } 

  used = new boolean[26]; 
  for (int i = 0; i < n; i++) { 
    if (!diff(str, 0, i)) { 
      continue; 
    } 

    int j = i; 
    boolean bad = false; 
    while (j < str.length()) { 
      if (!diff(str, j, j + n)) { 
        bad = true; 
        break; 
      } 
      j += n; 
    } 
    if (bad) { 
      continue; 
    } 
    return i; 
  } 

  return -1; 
} 
}

Answer 1

Я понял, что-то вроде этого O(S) + O(n^2) + O(SS)*O(n^2), где

S = songlist.length, SS = сумма всех длин песен. Таким образом, ваша сложность зависит от различных входных данных и не может быть представлена ​​простым значением.

P.S. Обратите внимание, что String является неизменным объектом, поэтому лучше использовать StringBuilder.

До:

String str = ""; 
  for (int i = 0; i < songlist.length; i++) { 
    str += songlist[i]; 
  }

После того, как:

StringBuilder builder = new StringBuilder(); 
  for (int i = 0; i < songlist.length; i++) { 
    builder.append(songlist[i]); 
  }

В этом случае вы не будете создавать новый объект String на каждой итерации

Answer 2

Поскольку «n» не является размером ввода, на самом деле оно не может быть O (n) или O (n ^ 2). Если m - длина всех строк в списке песен, то вы перепрыгиваете через эту строку с шагом n. Таким образом, сходство связано с м не п. Я не вычислял в больших O и т. Д. В течение нескольких десятилетий ... однако я бы предположил, что сложность составляет O (m).