櫻井より
---------------------------------------------------
課題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)