櫻井より
---------------------------------------------------
課題1:締切りは12月01日。管理工学科事務室に提出されたし。
(1) 次の big-O 記法に関する式を証明しなさい
(2) 次のプログラムの実行時間を n の関数としてオーダー表記しなさい。Θをつかいなさい。
なお、Θ( ) の括弧の中には、n と log n の多項式が現れる。分かりやすい説明をつけてください。
(2-1) n は正の整数
for ( i=1; i<n; i++ )
for ( j=2n; j>i ; j-- )
a[i][j] = i*j+3;
(2-2) n は正の整数
i = 0;
while ( n>1 ) {
n = n/2;
i++;
}
(2-3) n は正の整数
usort( 0, n-1 );
但し
usort( int i, int j) {
int k;
if ( i=>j ) return;
k = ( i+j )/2;
usort( 1, k );
usort( k+1, j);
return ;
}
(3) Java でバブルソートとクイックソートのプログラムを書き、その実行速度を比較しなさい。
ただし、クイックソートは講義で話したアルゴリズムでプログラムして下さい。クイックソートは
他にもいくつか方法が考えられていて、書籍やwebにも他の形のアルゴリズムが掲載されて
いますので、ご注意ください。
また、データ数や実験回数は、実験しながら、適宜選択しなさい(速度差、速度の変化の違い
がわかるだけの回数、データ数を変えながら実験しなさい)。
一つのデータ数(例えば1000個)についても複数回実験し、その平均時間を求めそれを元に
報告しなさい。平均値は(手で計算するのではなく)プログラムを用いて求めなさい。
データは、一様ランダムに選んだ値を用いなさい。
注意1:
下記の java プログラムを参考にしてください。
Sort.java
以上(2003.11.09)