計算量とは
けいさんりょう
アルゴリズムが必要とする手間(時間計算量)や記憶領域(空間計算量)が、データの数 n に対してどのように増えるかを表したもの。O(n) や O(n log n)、O(n²) のようなオーダー記法(ビッグO記法)で、係数や低い次数の項を省いて書く。
「計算量」は、2分野の8問の練習問題に出てきます(データ構造とアルゴリズム, 性能評価・プロファイリングなど)。
この用語の分野: データ構造とアルゴリズム
オーダー記法の読み方
O(f(n)) は、n が十分大きいとき、手間がおよそ f(n) の定数倍以下に収まることを表します。比較の回数が 3n² + 5n + 2 回のアルゴリズムは、n が大きくなると n² の項が支配的になるので O(n²) と書きます。よく出てくる順に、O(1)(定数)、O(log n)(二分探索)、O(n)(線形探索)、O(n log n)(マージソート、ヒープソート)、O(n²)(バブルソート、選択ソート)、O(2ⁿ)(素朴な全探索)などがあります。n = 1000 のとき、log₂ n は約10、n log₂ n は約1万、n² は100万なので、大きなデータではオーダーの違いが決定的になります。
最良・平均・最悪の場合
同じアルゴリズムでも、入力によって手間が変わることがあります。挿入ソートは、整列済みのデータなら比較が n−1 回の O(n) ですが、逆順なら n(n−1)/2 回の O(n²) です。クイックソートは平均 O(n log n) ですが、ピボットの選び方とデータによっては最悪 O(n²) になります。応答時間に上限が必要なシステムでは最悪の場合を、全体の処理量を見積もるときは平均の場合を重視します。可変長配列への追加のように、ときどき重い処理があっても多数回の平均では一定になるものは、償却計算量 O(1) と表します。
オーダーだけでは決まらない実際の速さ
オーダー記法は定数倍を無視するので、同じ O(n) でも実際の速さは大きく違うことがあります。現在のコンピュータでは、主記憶へのアクセスがL1キャッシュより100倍近く遅いので、配列を順に読む処理は、連結リストをたどる処理より何倍も速くなります。また、n が小さい範囲では、オーダーの大きい単純な方法の方が速いこともあり、実際のソートの実装では短い区間に挿入ソートを使います。性能を改善するときは、まずオーダーの大きいアルゴリズムを使っていないかを確かめ、そのうえでメモリのアクセスの仕方などを測定して詰めていきます。
計算量の練習問題に挑戦
要素数 n の配列で、異なる2つの要素の組をすべて1回ずつ比べる処理(i 番目の要素を、それより後ろにあるすべての要素と比べることを、i を1つずつ進めて繰り返す二重ループ)の計算量はどれか。
- AO(n)
- BO(n log n)
- CO(n²)
答えと解説を見る
正解：C. O(n²)
比べる組の数は (n−1) + (n−2) + … + 1 = n(n−1)/2 で、n = 10 なら45回、n = 1000 なら499,500回です。計算量のオーダーは n が大きくなったときの増え方だけを見るので、係数の1/2や低い次数の項を省いて O(n²) と表します。n が2倍になると回数はおよそ4倍になります。O(n) は全要素を1回ずつ見るだけの処理、O(n log n) はマージソートのように半分に分けることを繰り返す処理の計算量です。
計算量が O(n²) のプログラムで、データ数が1,000のときに処理時間が0.5秒だった。データ数を4,000にすると、処理時間はおよそ何秒になるか。
- A2秒
- B8秒
- C32秒
答えと解説を見る
正解：B. 8秒
O(n²) では処理時間がデータ数の2乗に比例するので、データ数が4倍になると処理時間は 4² = 16倍になり、0.5秒 × 16 = 8秒です。2秒はデータ数に比例する O(n) の場合、32秒は3乗に比例する O(n³) の場合(4³ = 64倍)の値です。実際には、データがキャッシュに入りきらなくなるなどの影響で、これより遅くなることもあります。
よくある質問
O(log n) の log の底は何ですか?
底を変えても定数倍しか違わない(log₂ n = log₁₀ n ÷ log₁₀ 2)ので、オーダー記法では底を書かないのが普通です。二分探索のように半分ずつに分ける場合は、実際の回数は log₂ n に近くなります。
時間計算量と空間計算量の違いは何ですか?
時間計算量は処理の手間(実行時間)の増え方、空間計算量は必要な記憶領域の増え方です。マージソートは時間 O(n log n)、作業用の空間 O(n) で、ヒープソートは時間 O(n log n)、空間 O(1) のように、両方を合わせて比べます。
解説の中の「計算量」
計算量のオーダーは n が大きくなったときの増え方だけを見るので、係数の1/2や低い次数の項を省いて O(n²) と表します。
要素数 n の配列で、異なる2つの要素の組をすべて1回ずつ比べる処理(i 番目の要素を、それより後ろにあるすべての要素…データの個数は計算量に関係しません。
クイックソートの計算量が O(n²) になる典型的な場合はどれか。最良の場合(先頭にある)は1回、最悪の場合(末尾にある)は100回で、平均も最悪も n に比例するので計算量は O(n) です。
異なる100個の値が入った配列から、先頭から順に1つずつ比べる線形探索で目的の値を探す。目的の値は必ず配列の中にあり、…計算量は O(log n) で、100万個でも最大20回で済みます。
昇順に整列された異なる1,000個の値から二分探索で値を探す。1回の比較で「一致・より小さい・より大きい」が分かるもの…計算量のオーダーが同じでも、メモリのアクセスの仕方によって実際の速さは大きく変わります。
要素数が多く、負荷率を0.5程度に保ったハッシュテーブルで、線形探査のオープンアドレス法が、チェイン法(連結リストでつ…
「計算量」が出てくる問題(8問)
- 要素数 n の配列で、異なる2つの要素の組をすべて1回ずつ比べる処理(i 番目の要素を、それより後ろにあるすべての要素と比べることを、i を1つずつ進めて繰り返す二重ループ)の計算量はどれか。
- 計算量が O(n²) のプログラムで、データ数が1,000のときに処理時間が0.5秒だった。データ数を4,000にすると、処理時間はおよそ何秒になるか。
- 最悪の場合でも計算量が O(n log n) で、作業用の配列などの追加の記憶領域をほとんど使わずに並べ替えられるソートはどれか。
- クイックソートの計算量が O(n²) になる典型的な場合はどれか。
- 異なる100個の値が入った配列から、先頭から順に1つずつ比べる線形探索で目的の値を探す。目的の値は必ず配列の中にあり、どの位置にある確率も等しいとき、比較の回数の平均はいくらか。
- 昇順に整列された異なる1,000個の値から二分探索で値を探す。1回の比較で「一致・より小さい・より大きい」が分かるものとすると、見つかる場合も見つからない場合も含めて、比較の回数は最大で何回か。
- 要素数が多く、負荷率を0.5程度に保ったハッシュテーブルで、線形探査のオープンアドレス法が、チェイン法(連結リストでつなぐ方法)より速くなりやすい理由として最も適切なものはどれか。
- 大量のデータを処理するプログラムで、最も大きな速度向上が得られる可能性が高い改善はどれか。
データ構造とアルゴリズムの参考書を探す PR
Amazonの検索結果へのリンクです。Amazonのアソシエイトとして、半導体教室は適格販売により収入を得ています。