読み方 ： けいさんりょう

概要

アルゴリズムが処理する入力データの規模が大きくなったときに、処理時間やメモリ使用量がどのように増加するかを表現するものである。一般に「時間計算量」と「空間計算量」の二種類に分けられ、時間計算量はアルゴリズムが完了するまでに要する処理ステップの回数、空間計算量は処理に必要なメモリの占有量を表す。単に「計算量」と言う場合は時間計算量を指すことが多い。

時間計算量を議論する際、あるアルゴリズムについての厳密な実行時間を計測しようとすると、プログラムの記述に用いた言語や実行環境の種類、実装の巧拙、与えるデータの量や内容の影響を受け、公正な比較が難しい。このため、入力データ量を増やしたときにどのような傾向で計算量が増加するかという傾向を抽象的に表す手法が用いられる。

これを表現する表記法として「O記法」（ビッグオー記法、ランダウの記号）が広く用いられる。これは、入力データの量（n）が増加したとき、処理ステップ数がどのような規則性で増えるかを表す。例えば、O（n） はデータ量と時間の関係がほぼ正比例（線形）であることを表し、データ量が2倍になれば処理時間もほぼ2倍になる。O（n²） ならばデータ量の二乗に、O（√n） ならばデータ量の二乗根に比例して計算時間が増える。データ量に依らず一定時間で計算が完了する関係は O（1） と書き表す。

同じ問題を解くアルゴリズムでも計算量が大きく異なる場合がある。例えば、n個のデータから特定の値を先頭から順に探す線形探索は O（n） である一方、整列済みデータを二分割しながら探す「バイナリサーチ」なら O（log n） であり、データ量が増えると処理時間に大きな差がつく。バブルソートのようなシンプルな整列アルゴリズムは O（n²） に分類され、データ量が多くなると実用的でなくなってしまうため、実用上は O（n log n） で済むクイックソートなどが重宝される。

計算量の概念は「計算量理論」と呼ばれる計算機科学の分野で体系的に研究されている。この分野では問題の難しさを計算量の観点から分類する研究が行われている。例えば、多項式時間で解ける問題の集合を表す「P問題」や、その解の検証が多項式時間で行える「NP問題」などの概念が知られている。

この記事の著者 ： (株)インセプト IT用語辞典 e-Words 編集部
1997年8月より「IT用語辞典 e-Words」を執筆・編集しています。累計公開記事数は1万ページ以上、累計サイト訪問者数は1億人以上です。学術論文や官公庁の資料などへも多数の記事が引用・参照されています。