先週の最大選択法の処理時間の分析を、解説する。 具体的な説明は、先週の資料に記載したのでそちらを参照。 この後、2分探索法のブログラムを示し、オーダ記法の説明を行う。

2分探索法の分析

int data[ N ] ;     // dataはあらかじめ昇順にソート
int key = 探す値 ;
int L = 0 , R = N ; // [0,N)
while( R-L > 1 ) {
   int M = (L + R) / 2 ; // [L,M) , M , [M+1,R)
   if ( data[ M ] == key )
      break ;
   else if ( data[ M ] > key )
      R = M ;     // [L,M)
   else
      L = M+1 ;   // [M+1,R)
}

このプログラムでは、ループ1回につき、対象データ件数が約半分になる。 よって、m回ループをすれば、対象データ件数は、 となり、 データが見つからない最悪ケースでは、対象データ件数が1件になるまで繰り返す。 よって、 となり、 処理時間は、以下のように示される。

オーダ記法

処理速度の見積もりでは、単純ループはNに比例、 最大選択法では、に比例、 2分探索法では、 に比例ということが、アルゴリズムの処理時間の分析では重要となる。 そこで、「Nについてのどのような式に比例するのか？」を、オーダ記法で表す。 単純ループでは、、 最大選択法では、、 2分探索法では、といったように表記する。