ソート処理時間の問題として、最大選択法の処理とクイックソートの処理の時間の解説。

最大選択法は、 IMG n /cgi-bin/mimetex.cgi?O(N^2) より IMG n /cgi-bin/mimetex.cgi?T_m(N)=T_aN^2 、クイックソートは、 IMG n /cgi-bin/mimetex.cgi?O(N\log{N}) より、 IMG n /cgi-bin/mimetex.cgi?T_q(N)=T_bN\log{N} となる。

IMG n /cgi-bin/mimetex.cgi?T_m(10)=10\mbox{msec} IMG n /cgi-bin/mimetex.cgi?T_q(10)=20\mbox{msec} ならば、 IMG n /cgi-bin/mimetex.cgi?T_a=1/10\mbox{[msec]} , IMG n /cgi-bin/mimetex.cgi?T_b=2\mbox{[msec]} (ただし、logの底は計算の都合で10とおく) よって、 IMG n /cgi-bin/mimetex.cgi?T_m(N)=T_q(N) となるNを求めると、 IMG n /cgi-bin/mimetex.cgi?T_aN^2=TbN\log{N} を解けばいい。ニュートン法などで解くと N = 29 ぐらいとなる。 よって、N=30以上では、クイックソートの方が効率がよい。

再帰呼出の処理時間

フィボナッチ数列の再帰呼び出しのプログラムを見せ、 再帰呼び出しプログラムの考え方を局所変数などの用語を交えて説明。 再帰を含む関数の処理時間ということで、階乗のプログラムの処理時間の オーダを解説する。

IMG n /cgi-bin/mimetex.cgi?T_{fact}(1)=T_A , IMG n /cgi-bin/mimetex.cgi?T_{fact}(N)=T_B+T_{fact}(N-1) この式を代入しながら繰り返し、一般式をだすと、 IMG n /cgi-bin/mimetex.cgi?T_{fact}(N)=T_A+T_B\times(N-1) となることを示す。

もっと現実っぽいプログラムの見積りということで、

int foo( int x )
{
if ( x == 1 ) {
return 1 ;
} else {
int s = 0 , i ;
for( i = 0 ; i < x ; i++ )
s = s + i ;
return s + foo( x - 1 ) ;
}
}

のプログラムの一般式を導出する。 IMG n /cgi-bin/mimetex.cgi?T_{foo}(1)=T_A , IMG n /cgi-bin/mimetex.cgi?T_{foo}(N)=T_B+T_CN+T_{foo}(N-1) を代入繰り返しで解いて、一般式を示す。

来週は、再帰による2分探索プログラムによる再帰方程式の作成と導出、 ハノイの塔の処理時間での再帰方程式の作成と導出をやる予定。