ホーム » 「オーダー記法」タグがついた投稿

タグアーカイブ: オーダー記法

2018年12月
« 11月    
 1
2345678
9101112131415
16171819202122
23242526272829
3031  

最近の投稿(電子情報)

アーカイブ

カテゴリー

マージソートのオーダー

マージソートの分析

マージソートは、与えられたデータを2分割し、 その2つの山をそれぞれマージソートを行う。 この結果の2つの山の頂上から、大きい方を取り出す…という処理を繰り返すことで、 ソートを行う。

このことから、再帰方程式は、以下のようになる。

  • Tm(1)=Ta

この再帰方程式を、N=1,2,4,8…と代入を繰り返していくと、 最終的に処理時間のオーダが、 となる。






よって、

選択法とクイックソートの処理時間の比較

データ数 N = 20 件でソート処理の時間を計測したら、選択法で 10msec 、クイックソートで 20msec であった。

  1. データ件数 N= 100 件では、選択法,クイックソートは、それぞれどの程度の時間がかかるか答えよ。
  2. データ件数何件以上なら、クイックソートの方が高速になるか答えよ。

設問2 は、通常の関数電卓では求まらないので、数値的に方程式を解く機能を持った電卓が必要。

再帰処理の処理時間

再帰関数と再帰方程式

再帰関数は、自分自身の処理の中に「問題を小さくした」自分自身の呼び出しを含む関数。プログラムには問題が最小となった時の処理があることで、再帰の繰り返しが止まる。

// 階乗
int fact( int x ) {
   if ( x <= 1 )
      return 1 ;
   else
      return x * fact( x-1 ) ;
}
// ピラミッド体積
int pyra( int x ) {
   if ( x <= 1 )
      return 1 ;
   else
      return x*x + pyra( x-1 ) ;
}
// フィボナッチ数列
int fib( int x ) {
   if ( x <= 2 )
      return 1 ;
   else
      return fib( x-1 ) + fib( x-2 ) ;
}

これらの関数の結果について考えるとともに、この計算の処理時間を説明する。 最初のfact(),pyra()については、 x=1の時は、関数呼び出し,x<=1,return といった一定の処理時間を要し、 で表せる。 x>1の時は、関数呼び出し,x<=1,*,x-1,returnの処理に加え、x-1の値で再帰の処理時間がかかる。 このことから、 で表せる。 これを代入によって解けば、 で表せる。 こういった式は、再帰方程式と呼ばれ、一般式を求めることとなる。

fact() や pyra() のような関数は、プログラムの末端に再帰が行われている。(fib()は、再帰の一方が末尾ではない)
このような再帰は、末尾再帰と呼ばれ、関数呼び出しの return を、再帰処理の先頭への goto 文に最適化が可能である。つまり繰り返し処理に書き換えが可能である。このため、ループにすれば局所変数を消費しない。

最後に、再帰方程式の事例として、ハノイの塔の処理時間について説明し、 数学的帰納法での証明を示す。

ハノイの塔


ハノイの塔は、3本の塔にN枚のディスクを積み、ディスクの上により大きいディスクを積まずに、移動させるパズル。

一般解の予想

ハノイの塔の移動回数を とした場合、 少ない枚数での回数の考察から、 ということが予想ができる。
この予想が常に正しいことを証明するために、ハノイの塔の処理を、 最も下のディスク1枚と、その上の(N-1)枚のディスクに分けて考える。

再帰方程式

これより、


ということが言える。
ディスクが枚の時、予想が正しいのは明らか。
ディスクが 枚で、予想が正しいと仮定すると、 枚では、



となり、 枚でも、予想が正しいことが証明された。 よって数学的帰納法により、1枚以上で予想が常に成り立つことが証明できた。

再帰を含む一般的なプログラム例

ここまでの再帰方程式は、再帰の度にNの値が1減るものばかりであった。もう少し一般的なプログラムで再帰方程式を使って処理時間を考えてみよう。
以下のプログラムを実行したらどんな値になるであろうか?それを踏まえ、処理時間はどのように表現できるであろうか?

int array[ 8 ] = {
  3 , 6 , 9 , 1 , 8 , 2 , 4 , 5 ,
} ;
int sum( int a[] , int L , int R ) {
    if ( R - L == 1 ) {
        return a[ L ] ;
    } else {
        int M = (L + R) / 2 ;
        return sum( a , L , M ) + sum( a , M , R ) ;
    }
}
int main() {
    printf( "%d¥n" , sum( array , 0 , 8 ) ) ;
    return 0 ;
}
//                         s(0,8) ← sum(a,0,8)
//                      /      \ 
//                  /               \ 
//            s(0,4)                      s(4,8)
//           /  \                   /  \
//     s(0,2)        s(2,4)        s(4,6)        s(6,8)
//    /    \      /   \        /   \       /   \
// s(0,1) s(1,2) s(2,3) s(3,4) s(4,5) s(5,6) s(6,7) s(7,8)

このプログラムでは、配列の合計を計算しているが、引数の L,R は、合計範囲の 左端・右端を表している。そして、再帰のたびに2つに分割して解いている。

このような、処理を分割し、分割した処理を再帰で計算し、その分割した処理結果を組み合わせて結果を求めるような処理方法を、分割統治法と呼ぶ。

このことから、以下の再帰方程式が得られる。

これを、代入法により解いていくと、

ということで、このプログラムの処理時間は、 で表される。

繰り返し処理とオーダ記法

先週に、単純繰り返し処理の時間分析をやったので、次のステップに。

2分探索法の処理時間

データを探す処理において、単純検索より速い方法ということで、2分探索法の処理速度見積もりを行う。

// 2分探索法 O(log N)
int a[ 1000 ] ;
int size ;      // データ数 N
int L = 0 ;     // L=下限のデータの場所
int R = size ;  // R=上限のデータ+1の場所
while( L != R ) {
   int M = (L + R) / 2 ;  // 計算は整数型で行われることに注意
   if ( a[M] == key )     // 見つかった
      break ;
   else if ( a[M] < key ) // |L         |M.         |R
      L = M + 1 ;         // |----------|-+---------|
   else                   // |L---------|M|
      R = M ;             //              |M+1------|R
}

上記のようなプログラムの場合、処理に要する時T(N)は、

 # Mは繰り返し回数

処理は、対象となるデータ件数が繰り返し毎に半分となり、対象データ件数が1件になれば処理が終わる。このことから、

となることから、 の関係が成り立つ。よって、は、以下のように表せる。

単純なソート(最大選択法)の処理時間

次に、並べ替え処理の処理時間について考える。

int a[ 1000 ] ;
int size ;

for( int i = 0 ; i < size - 1 ; i++ ) {
    int tmp ;
    // i..size-1 の範囲で一番大きいデータの場所を探す
    int m = i ;
    for( int j = i + 1 ; j < size ; j++ ) {
        if ( a[j] > a[m] )
            m = j ;
    }
    // 一番大きいデータを先頭に移動
    tmp = a[i] ;
    a[i] = a[m] ;
    a[m] = tmp ;
}

このプログラムの処理時間T(N)は…

となる。

オーダー記法

ここまでのアルゴリズムをまとめると、処理時間に大きく影響する部分は、赤字の部分であり、特にその項の係数は、コンピュータの処理性能に影響を受けるが、アルゴリズムの優劣を考える場合は、それぞれ、 の部分の方が重要である。

単純サーチ
2分探索法
最大選択法

そこで、アルゴリズムの優劣を議論する場合は、この処理時間の見積もりに最も影響する項で、コンピュータの性能によって決まる係数を除いた部分を抽出した式で表現する。これをオーダー記法と言う。

単純サーチ オーダーNのアルゴリズム
2分探索法 オーダー log N のアルゴリズム
最大選択法 オーダー N2 のアルゴリズム

練習問題

  1. コンピュータで2分探索法で、データ100件で10[μsec]かかったとする。
    データ10000件なら何[sec]かかるか?
  2. の処理時間を要するアルゴリズムを、オーダー記法で書くとどうなるか?また、このようなアルゴリズムの例を答えよ。
  3. の処理時間を要するアルゴリズムを、オーダー記法で書くとどうなるか?