java - 这段代码的大O

Question

以下代码来自topcoder网站。我试图计算这段代码的时间复杂度。 isRandom 方法中有 1 个 for 循环和 1 个 while 循环，diff 方法中有 1 个 for 循环。我猜最坏的情况是 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 = 歌曲列表.长度，SS = 所有歌曲长度的总和。因此，您的复杂性取决于各种输入，并且不能用简单的值来表示。

附注请注意，String 是不可变对象(immutable对象)，因此最好使用 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 对象