処理速度の分析の第２段階として、再帰を含む処理の処理速度について説明を行う。
再帰による階乗の処理速度
再帰で階乗の処理を記述し、その動きを説明したあと、処理速度を分析してみる。
((階乗の再帰))
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分探索法を再帰によって記述してみる。 この処理にかかる時間は、データ件数Nに対して….
((２分探索の再帰による記述))
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))