1

以下の関数の複雑さを理解しようとしています。Random クラスは O(1) と put() で乱数を生成し、O(1) でもあるため、O(n) になると思いますcontainsKey()。

しかしdo-while、ループ内に a があるため、値が 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 の範囲です。

4

1 に答える 1

1 
 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)
于 2012-09-06T05:07:52.350 に答える