ホーム » スタッフ » 斉藤徹 » オーダ記法と再帰関数

2012年4月
« 3月   5月 »
1234567
891011121314
15161718192021
22232425262728
2930  

最近の投稿(電子情報)

アーカイブ

カテゴリー

オーダ記法と再帰関数

先週は、単純サーチ、最大選択法などの説明だったので、 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 ) ;
}