ホーム » スタッフ » 斉藤徹 » 再帰方程式の説明

2009年4月
« 3月   5月 »
 1234
567891011
12131415161718
19202122232425
2627282930  

最近の投稿(電子情報)

アーカイブ

カテゴリー

再帰方程式の説明

処理速度の分析の第2段階として、再帰を含む処理の処理速度について説明を行う。

再帰による階乗の処理速度

再帰で階乗の処理を記述し、その動きを説明したあと、処理速度を分析してみる。

((階乗の再帰))
int fact( int x ) {
if ( x <= 0 )
return 1 ;
else
return x * fact( x - 1 ) ;
}
((処理速度の再帰方程式))
 T(0) = Ta
 T(N) = Tb + T(N-1)   |  N≧1
((再帰方程式を代入法で予測))
 T(0) = Ta
 T(1) = Tb + T(0) = Ta + Tb
 T(2) = Tb + T(1) = Ta + 2*Tb
    :
 T(N) = Ta + N * Tb
よって、再帰による階乗の処理は、O(N)

再帰による2分探索の処理速度

次に2分探索法を再帰によって記述してみる。 この処理にかかる時間は、データ件数Nに対して….

((2分探索の再帰による記述))
int find( int data[] , int L , int R , key ) {
if ( L+1 == R ) {
if ( data[ L ]  == key )
return L ;
else
return -1 ;
} else {
int  M = (L + R) / 2 ;
if ( data[ M ] == key )
return M ;
else if ( data[ M ] > key )
return find( data , L , M , key ) ;
else
return find( data , M , R , key ) ;
}
}
int array[8] = { 12 , 23 , 34 , 45 , 56 , 67 , 78 , 89 } ;
void main() {
printf( "%d番目に見つかった" , find( array , 0 , 8 , 78 ) ) ;
}
((処理速度の分析))
この関数は、対象となるデータ件数によって時間が変化し、
対象となるデータ件数(R-L) の関数Tであるとして...
 T(1) = Ta
 T(N) = Tb + T( N / 2 )
で表すことができる。
代入法で予測してみると、
 T(1) = Ta
 T(2) = Tb + T(1) = Ta + Tb
 T(4) = Tb + T(2) = Ta + 2 * Tb
   :
 T(2^m) = Ta + m * Tb
ただし m = log2( N ) だから、
 T(N) = Ta + Tb * log(N)
よって、O(log(N))

ハノイの塔や再帰によるフィボナッチ数列の処理速度