処理速度の分析の第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))