我试图弄清楚下面函数的复杂性。我猜它会是 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 之间的任意数字。
最佳答案
Building the map elements: O(n)--->for loop
Checking if the random value is in the map: O(1+α) with a good hash function
Trying to find a random value which your map does not have: O(n)
(because you are using integer. Even floats would give very good resolution)
array length=1000, random-value range=1000(from 0 to 999)
think you are at the last element. probability of getting proper value is:
%0.1 which takes an average of 1000 trials only for the last element (n)
nearly same for the (n-1)st element (%0.2-->n/2 trials)
still nearly same for (n-2)nd element (%0.3-->n/3 trials)
what is n+n/2 + n/3 + n/4 + n/5 ... + 1 = a linear function(O(n)) +1
α2=1 but neglecting :) and this is on top of a O(n)
Result: O(n*n+α*n*n) close to O(n*n)
关于java - 随机播放函数复杂性,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/12293248/