前回の授業で、単純サーチ、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つについては、代入を繰り返すことで、一般式を示すことは容易である。

最後に、再帰方程式の応用として、ハノイの塔の再帰方程式を示す。 次回までに、この再帰方程式を解く方法について予習しておくように伝える。