基礎理論 - 1.基礎理論 - 3.情報に関する理論 - 7.計算量

Last Update : January 02 2021 16:00:16

　 　 　

a. アルゴリズムの評価

良いアルゴリズムとは、

  • 仕組みが単純
  • 処理時間が短い
  • 使用メモリ量が少ない

とくに、処理時間は重要になる。その処理時間の目安にするものを時間計算量という。
時間計算量を尺度としてアルゴリズムを評価する場合がある。


b. 計算量の求め方

アルゴリズムによる処理の時間に関する計算量を「時間計算量」といい、アルゴリズムで必要となる変数領域の大きさ(メモリ領域の大きさ)に関する計算量を「空間計算量」という。
時間計算量は、アルゴリズムでの主要な操作に着目して、解に達するまでに必要な操作回数のことを計算量（オーダー）といい、Ｏ (ｎの式) で表現します。
計算量での評価とは、「扱うデータ件数が増えるにつれ、どのような割合で計算量が増加するか」ということ。


c. オーダ記法

　O(n2)計算時間　大
　O(nlogn)　↑
　O(n)　
　O(logn)↓
　O(1)　計算時間　小　
 　　　


　 アルゴリズム オーダー
探索 線形探索 O(n)
2分探索法 O(logn)
ハッシュ表探索法 O(1)
整列 バブルソート O(n2)
選択ソート O(n2)
挿入ソート O(n2)
マージソート O(nlogn)
クイックソート O(nlogn)
ヒープソート O(nlogn)

　　[ 例題 ]　
  1. 平成24年度秋期　問03　　探索時間
  2. 平成19年度秋期　問11　　探索時間
  3. 平成17年度春期　問15　　探索回数
  4. 平成14年度秋期　問13　　ソート　比較回数
  5. 平成12年度秋期　問14　　探索回数


　 　 　

www.it-shikaku.jp