如何确定这个小程序的复杂性

Question

package maguen_3;
import java.util.Arrays;
public class Maguen_3_test {
public static void main(String[] args) {
randomPLaylist(10);
}
public static void randomPLaylist(int num) {
int[] songsArray = new int[num];
for(int i = 0; i < num; i++) {
songsArray[i] = (int)(Math.random()*num) + 1;
for(int j = 0; j < i; j++) {
if(songsArray[i] == songsArray[j]){
i--;
break;
}
}
}
System.out.println(Arrays.toString(songsArray));
}
}

这是一个打乱播放列表的小程序。函数randomPlaylist接收播放列表的长度。我凭直觉知道它是O(n*logn(，但我不知道如何用语言来解释它。

Answer 1

它不是O(n*log n)。

您应该计算两个循环的迭代次数。

外循环具有num迭代。让我们用n来表示num。

在最坏的情况下(如果条件从不为true(，内部循环具有i迭代。

内部循环第一次运行时有0次迭代。

第二次运行时，它有1次迭代。

上次运行时，它有n - 1次迭代。

因此总时间为1+2+…+n - 1=n * (n - 1) / 2=O(n^2)