我试图弄清楚下面函数的复杂性。我猜这将是 O(n),因为 Random 类在 O(1) 和 put() 中产生一个随机数,并且containsKey()
也是 O(1)。
但由于do-while
循环内部有一个,我不确定复杂性是否会改变,因为如果值包含在 HashMap 中,则可以多次调用 random()。我将不胜感激任何帮助!
HashMap<Integer, Integer> values = new HashMap();
for(int i=0 ; i<a.length; i++){
do{
// set variable random to some integer between 0 and a.length using Random class in Java, 0 is included.
}while(values.containsKey(random) == true);
b[i] = a[random]
values.put(random,0);
}
数组的长度约为 1000,生成的随机数在 0 到 999 之间。