while在for循环内的时间复杂度?

Question

我有以下算法:

for(int i=0; i<list.size(); i++){
String cur = list.get(i);
int cnt =0;
while(output.contains(cur)){
cur= cur.substring(0,5) + String.valueOf(cnt);
cnt++;
}
output.add(cur);
}

Not that "list"one_answers";output"ArrayLists。

我认为时间复杂度是O(n^2)。但是有一个output.contains(cur)的while循环呢?

Answer 1

该算法的复杂度似乎与outputlist的初始内容有关:

• output为空，不执行while循环，复杂度为O(N)，其中N为list的大小

• list和output被精心制作以符合output.contains(cur)条件例如,

List<String> list = Arrays.asList("abcde0", "abcde1", "abcde2", "abcde3", "abcde4", "abcde5", "abcde6");
List<String> output = new ArrayList<>(list);

output的大小将会增长，因此迭代的次数将会像这样:

1) n+1
2) n+1 + n+2 = 2 (n+1) + 1
3) n+1 + n+2 + n+3 = 3 (n+1) + 3
4) n+1 + n+2 + n+3 + n+4 = 4 (n+1) + 6
...
n) n (n+1) + (1 + n-1)*(n-1)/2 = n (n+1) + n (n - 1)/2 = n (3n + 1)/2 

因此，在这种情况下(可能不是最坏的情况)，复杂度可以是O(N^2)。