オーダ記法

先週の最大選択法の処理時間の分析を、解説する。 具体的な説明は、先週の資料に記載したのでそちらを参照。 この後、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分探索法では、といったように表記する。

 

2015年12月

    1 2 3 4 5
6 7 8 9 10 11 12
13 14 15 16 17 18 19
20 21 22 23 24 25 26
27 28 29 30 31    

アーカイブ

Google

このブログ記事について

このページは、T-Saitohが2011年4月20日 12:49に書いたブログ記事です。

ひとつ前のブログ記事は「変数の寿命と有効範囲、関数と引数」です。

次のブログ記事は「手続き抽象・データ抽象」です。

最近のコンテンツはインデックスページで見られます。過去に書かれたものはアーカイブのページで見られます。