整列法評価のためのランダム順列の生成

スポンサーリンク

概要

論文の詳細を見る
整列法(ソーティングアルゴリズム)の性能評価のための入力列として、従来は多くの場合に一様乱数列が利用されてきた。しかし現実の問題としてソーティングを扱う場合には、与えられた数列はほとんど整列済みであることが多いと言われている。従って、ソーティングアルゴリズムの性能評価をする際には、入力列の整列度合を表す各種の事前整列性測度を制御しながら入力列を生成する必要がある。実際ある種の整列性測度で見ると一様乱数は非常に偏った値を持ち、整列法の性能評価には不適である。本稿では(1)事前整列性測度のうち、葉数(数列内で隣接する要素より小さい要素の個数)を制御し、任意に与えられた葉数mを持つ順列を一様に生成する方法、(2)生成された順列の一様性を検定する方法および(3)検定結果について報告する。葉数の事前整列性測度としての妥当性については[4]で述べた。
一般社団法人情報処理学会の論文
1995-03-15

著者

関連論文

もっと見る

スポンサーリンク