4．4 計算量
番号 以下をクリックすると，該当箇所にジャンプします （１） 計算量の種類 （２） 線形探索法の時間計算量 （３） ２分探索法の時間計算量 （１）計算量の種類 計算量（complexity）には，以下の２種類があります。 ■時間計算量（time complexity） 　　実行に要する時間の評価 ■領域計算量（space complexity） 　　どのくらいの記憶域が必要かを評価 一般には，両者のバランスに配慮して，アルゴリズムを選択します。 （２）線形探索法の時間計算量 要素数をＮとすると線形探索の各ステップの実行回数は， 　　I = 0; 　　while ( I < N){　　　　 　　　if (A[I] == key) 　　　return I; 　　　I++; 　　} 　　return -1; // (1) 実行回数＝１ // (2) 実行回数＝平均Ｎ／２　　　　 // (3) 実行回数＝平均Ｎ／２ // (4) 実行回数＝１ // (5) 実行回数＝平均Ｎ／２ // (6) 実行回数＝1 となります。 実行回数がＮに比例するとき， 　　Ｏ（Ｎ） と記述します。 これを「Ｎのオーダ(order)」または 「オーダＮ（Order N)」等 といい，大雑把な計算量を示します。 単に比例するかどうかを示す量ですから， ２Ｎに比例しても，Ｎ／２に比例しても，Ｏ（Ｎ）とします。 オーダでは，次の関係式が成立します。 　　O( f ( N )) + O( g ( N ))＝O( max( f ( N ), g ( N ))) すなわち，計算量はより大きい方の計算量に支配されます。 したがって，線形探索の計算量は，以下のようになります。 　　　O(1) + O(N) + O(N) + O(1) + O(N) + O(1) 　　 　= O(N) （３）２分探索法の時間計算量 　PL=0;　　　　　　　　　　 　PR=N - 1; 　while (PL <= PR) { 　　PC = (PL + PR) / 2; 　　if (A[PC] == key) 　　　return PC; 　　else if (A[PC] < key) 　　　PL = PC + 1; 　　else 　　　PR = PC - 1; 　} 　return -1; // ( 1) 実行回数＝１ // ( 2) 実行回数＝１ // ( 3) 実行回数＝log N // ( 4) 実行回数＝log N // ( 5) 実行回数＝log N // ( 6) 実行回数＝１ // ( 7) 実行回数＝log N // ( 8) 実行回数＝(log N)/2 // ( 9) 実行回数＝(log N)/2 // (10) 実行回数＝(log N)/2 // (11) 実行回数＝1 実行回数＝log N，実行回数＝(log N)/2の 両者ともにlog Nに比例する計算回数であるため 　　　O(log N) となります。 1. 基本的なアルゴリズム 2. 基本的なデータ構造 3. 操作を伴うデータ構造 4. 探索 5. 再帰的アルゴリズム 6. ソート 7. 集合 8. 文字列処理 9. 色々なアルゴリズム 上のタイトルをクリックします