計算量とオーダの試験問題への適用
本番ではコード断片から繰返し回数を数え、支配項を見つけてオーダを求める。連続処理は足し算、入れ子処理は掛け算で考える。
この単元で学ぶこと
- 連続処理の意味と役割を説明できる
- 入れ子処理の意味と役割を説明できる
- 半減ループの意味と役割を説明できる
- ループ構造を分解してO(log n)、O(n log n)、O(n²)などを求められる
本文解説
O(n)+O(n²)なら大きいn²が支配してO(n²)。外側n回・内側log n回ならO(n log n)。内側の回数が外側変数に依存する場合は総和も考える。
連続処理 前後に並ぶ処理の計算量を加える。 支配項だけ残す。
入れ子処理 外側と内側の反復回数を掛ける。 独立なら積で見積もる。
半減ループ 変数を2倍/半分にし閾値まで進む反復。 回数はlog n級。
三角形ループ 内側回数が1,2,...,nのように増えるループ。 総和n(n+1)/2でO(n²)。
支配項 入力増加時に最も速く増える項。 低次項を無視する。
各ループの反復回数を書き、連続は加算・入れ子は乗算・最後に支配項を残す。
for i=1..n の中でjを1からnまで回すならO(n²)。内側jが2倍ずつならO(n log n)。
図解
重要ポイント
- 連続処理: 前後に並ぶ処理の計算量を加える。
- 入れ子処理: 外側と内側の反復回数を掛ける。
- 半減ループ: 変数を2倍/半分にし閾値まで進む反復。
- 三角形ループ: 内側回数が1,2,...,nのように増えるループ。
- コード行数ではなく、nに応じた実行回数を見る。
間違えやすい点
- 二つの連続ループをO(n²)としない。
- 2倍更新のループをO(n)としない。
- 三角形ループの総和をO(n)としない。
用語解説
- 連続処理
- 前後に並ぶ処理の計算量を加える。
- 入れ子処理
- 外側と内側の反復回数を掛ける。
- 半減ループ
- 変数を2倍/半分にし閾値まで進む反復。
- 三角形ループ
- 内側回数が1,2,...,nのように増えるループ。
- 支配項
- 入力増加時に最も速く増える項。
関連教材
参考資料
教材データに登録された参考リンクです。リンク先の内容や更新日は提供元でご確認ください。
確認問題の出題・採点や学習履歴の保存にはログインが必要です。