計算量とオーダを理解する
オーダ記法は入力サイズnが大きくなったとき、処理時間やメモリ量がどの程度増えるかを大まかに表す。
この単元で学ぶこと
- O(1)の意味と役割を説明できる
- O(log n)の意味と役割を説明できる
- O(n)の意味と役割を説明できる
- コード構造や代表アルゴリズムから時間計算量のオーダを判定できる
本文解説
定数係数や低次項を無視し、支配的な増え方でO(1)、O(log n)、O(n)、O(n log n)、O(n²)などに分類する。
O(1) 入力サイズに関係なく処理回数がほぼ一定。 配列の添字アクセスなど。
O(log n) 入力を一定割合で縮める処理。 二分探索が代表。
O(n) 入力要素を1回ずつ処理する線形処理。 線形探索や全要素走査。
O(n log n) n個の処理と対数段階を組み合わせる増え方。 効率的な比較整列で現れる。
O(n²) 二重ループなどでn×n程度の処理を行う増え方。 単純整列で現れやすい。
最も大きく増える項を残し、定数係数と低次項を捨てる。
3n²+5n+10はnが大きいとn²項が支配するのでO(n²)。
図解
重要ポイント
- O(1): 入力サイズに関係なく処理回数がほぼ一定。
- O(log n): 入力を一定割合で縮める処理。
- O(n): 入力要素を1回ずつ処理する線形処理。
- O(n log n): n個の処理と対数段階を組み合わせる増え方。
- オーダは正確な秒数ではなく、入力増加に対する増え方を表す。
間違えやすい点
- 定数係数をそのままオーダへ残さない。
- O(log n)とO(n)を入力半減の有無で区別する。
- 二重ループでも必ずO(n²)とは限らず範囲を見る。
用語解説
- O(1)
- 入力サイズに関係なく処理回数がほぼ一定。
- O(log n)
- 入力を一定割合で縮める処理。
- O(n)
- 入力要素を1回ずつ処理する線形処理。
- O(n log n)
- n個の処理と対数段階を組み合わせる増え方。
- O(n²)
- 二重ループなどでn×n程度の処理を行う増え方。
関連教材
参考資料
教材データに登録された参考リンクです。リンク先の内容や更新日は提供元でご確認ください。
確認問題の出題・採点や学習履歴の保存にはログインが必要です。