先週は、単純サーチ、最大選択法などの説明だったので、 2分探索方の説明を行い、
単純サーチ T(N) = Ta + Tb×N 最大選択法 T(N) = Ta + Tb×N + Tc×N^2 2分探索法 T(N) = Ta + Tb×log N
これらのTa,Tb,Tcは、計算機の性能に依存し、アルゴリズムの優劣判断には使えないので、 これらを記載しないオーダ記法を用い、 O(N) , O(N^2) , O(log N) のように記載する。
再帰関数
for 分による繰り返しの分析ができても、再帰処理を含む場合は、面倒になる。
以下のような再帰関数を示し、動作トレースのあと、一番簡単な fib について、 処理時間を示す。
int fact( int x ) { if ( x == 0 ) return 1 ; else return x * fact( x - 1 ) ; } int fib( int x ) { if ( x < 2 ) return 1 ; else return fib( x - 2 ) + fib( x - 1 ) ; }