オーダ記法と再帰方程式
前回の授業で、単純サーチ、2分探索法、最大選択ソートの 処理時間の一般式を示した。今回は、これをアルゴリズム の比較という視点で、オーダ記法の説明を行う。
オーダ記法
オーダ記法とは、データ件数Nが巨大であった場合に、 処理時間がどういった式に依存するのかをビッグオー に合わせて、O(N),O(log N),O(N^2)などと記載する方法。 Nが巨大になった時の最大項について、Nの式以外の 定数項を省いた式となる。
複雑な一般式のオーダ記法として、最大項を判断するために、 lim を用いて、ロピタルの定理などを使う方法を説明する。
再帰方程式
次に、再帰処理の処理速度分析について説明する。
// 階乗 int fact( int x ) { if ( x <= 1 ) return 1 ; else return x * fact( x - 1 ) ; } // 変な再帰 int foo( int x ) { if ( x <= 1 ) { return 1 ; } else { int s = 0 ; for( int i = 1 ; i <= x ; i++ ) s += i ; return s + foo( x - 1 ) ; } } // フィボナッチ数列 int fib( int x ) { if ( x <= 2 ) return 1 ; else return fib( x - 1 ) + fib( x - 2 ) ; }
このプログラムの処理時間を分析するための再帰方程式を示す。 最初の2つについては、代入を繰り返すことで、一般式を示すことは容易である。
最後に、再帰方程式の応用として、ハノイの塔の再帰方程式を示す。 次回までに、この再帰方程式を解く方法について予習しておくように伝える。