計算量はアルゴリズムの効率を表す指標。O記法で表現することで、データ量が増えたときの動作予測ができます。
日野 こむぎ
O(n) とか O(log n) って、よく出てくるけど何なの?
藤森 さやか 先生
計算量を表すO記法 (Big-O notation) ね。
データ量 n が増えたとき、処理時間がどう増えるかを表すの。
青木 澪
代表的なものを整理しておくわね。
O(1) は定数時間、O(log n) は対数時間 (二分探索)、O(n) は線形 (線形探索)、O(n log n) は線形対数 (高速ソート)、O(n²) は二乗 (基本ソート)、O(2ⁿ) は指数 (ナップサック等) よ。
桃井 すみれ
比べるとどれくらい違うんですかぁ?
藤森 さやか 先生
n=100なら、O(n)=100、O(n²)=10000、でもO(2ⁿ)になると宇宙の年齢でも終わらないのよ。
データが大きくなるほど、計算量の差は劇的に広がるの。
日野 こむぎ
じゃあ O(n²) より O(n log n) の方が断然いいんだね!
青木 澪
そう。
だから大規模データには O(n log n) のソートを使うの。
アルゴリズム選びは計算量で決めるのが基本ね。
藤森 さやか 先生
試験では「計算量を比較して選ぶ」「具体的な n に対して何回の操作が必要か」が問われるわ。
桃井 すみれ
オーダーには順番があるんですねぇ♪ O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ) < O(n!)
確認クイズ
次の計算量を遅い順に並べたときの先頭はどれか。 O(n²), O(log n), O(n), O(2ⁿ)
- O(n²)
- O(log n)
- O(n)
- O(2ⁿ)
こたえを見る
正解: 4. O(2ⁿ)
計算量の大小: O(log n) < O(n) < O(n²) < O(2ⁿ)。最も遅い (大きい) のは O(2ⁿ) です。指数時間はデータが10〜20個程度でも実用的でなくなります。