Thinkers'Studio
JavaとC言語の自習ツール
アルゴリズムと計算量(オーダ)
 基本情報技術者試験のアルゴリズム問題で、計算量のオーダを問う問題が出題されました。
 次のようなループで行う処理の計算量はどんな式で表わすでしょうか。
  (平成24年秋期 基本情報技術者試験より)
Via: 1, Via <= N, 1
    From: 1, From <= N, 1
        To: 1, To <= N, 1
             :
 3重ループで、いずれもN回繰り返します。 計算量は N×N×N 回の O(N3) となります。

計算量とは

 アルゴリズムの良し悪しでプログラムの効率が変わりますが、それを量として評価する計算量という考え方があります。
 計算量(オーダ)は、大文字の O を使った記法で表現されます。
 データ数 N に応じて、どのように計算量が増加するかを表わすものです。
 上の出題例のほかに、たとえば O(N) は、N の値に比例して計算量が変わることを意味します。N 個の要素を持つ配列の先頭から終わりまで、単一ループで順に調べるような場合です。

[ 関連記事 ] 用語集:アルゴリズム, 計算量(オーダ), 基本情報:過去問ページ

計算量の増加傾向

 おもな計算式とその増加傾向を表にしました。

 おもな計算量