再帰アルゴリズムの計算量を表す漸化式の立式

再帰アルゴリズムの計算量を表す漸化式の立式は、入力サイズに応じた時間または領域の増加率を表す分析概念である。

仕組み

基本操作の回数をnの関数T(n)として数え、十分大きなnで定数倍を無視して上界O、下界Ω、同程度の界Θを記述する。

計算量・性質

逐次処理は和、入れ子反復は積、分岐の最悪解析は最大を取る。

具体例

3n²+5n+2はn²項が支配するためΘ(n²)である。

限界と注意点

Big Oを実測時間や常に成立するタイトな界と同一視せず、解析ケースと入力モデルを明記する。