0

randpermMatlab の関数が使用するアルゴリズムはどこで確認できますか? Fisher-yates (Knuth) シャッフル アルゴリズムですか、それとも何か他のものですか?

4

1 に答える 1

2

R2009b の初期の MATLAB リリースでrandpermは、次のように実装されています。

function p = randperm(n)
    [ignore, p] = sort(rand(1, n));

次のように入力して、自分で確認できます。

type randperm

基本的に、 n 個randpermの数値を生成して並べ替え、順序付けられたインデックスの結果の配列をランダム順列として返します。この時間計算量はせいぜいO ( n log n ) であり、 O ( n )で実行されるFisher-and-Yates の shuffleよりも悪いです。p

編集: Dennis は、後のリリースではO ( nrandperm ) 時間で実行されると指摘しているため、明らかに改善されています。ただし、これは組み込み関数であるため、その実装を確認することはできません。

于 2013-05-07T14:06:50.017 に答える