二重ループと (O(n^2)) の見方
全てのペアを比較する処理では、外側のループで (n) 個を選び、内側のループでもおおむね (n) 個を確認します。処理回数は (n × n) に比例するため、計算量は (O(n^2)) と評価します。正解は (O(n^2)) です。 (選択肢4が正しい)
正解の理由
全てのペアを比較する処理では、外側のループで (n) 個を選び、内側のループでもおおむね (n) 個を確認します。処理回数は (n × n) に比例するため、計算量は (O(n^2)) と評価します。正解は (O(n^2)) です。
仕組み・頻出ポイント
- 全組合せ、全ペア比較、距離行列の総当たり計算などは (O(n^2)) になりやすい典型例です。
- 定数倍や低次の項はビッグオー記法では省略し、入力サイズが大きくなったときの増え方に注目します。
- (n) が10倍になると処理量は約100倍になるため、大規模データでは急速に重くなります。
G検定で覚えるべきこと
二重ループが常に (O(n^2)) とは限りません。内側の回数が固定なら (O(n))、探索範囲が半分ずつ減るなら別の評価になります。G検定では、擬似コードを読むよりも「全ペア」「総当たり」「二つの添字の組合せ」という言葉から増え方を見抜くことが重要です。
他の選択肢の評価
- 選択肢1: (O(1)) は入力数に依存しない処理です。全ペア比較には当てはまりません。
- 選択肢2: (O(log n)) は二分探索のように候補が半分ずつ減る処理の典型です。
- 選択肢3: (O(n)) は1回の走査のように処理回数が入力数に比例する場合です。
- 選択肢4: 正解です。二重に全体を回すため、処理回数は二次的に増えます。
実務での見方
実務では、(O(n^2)) の処理はデータ件数が増えたときに最初のボトルネックになりやすいです。全ペア比較が必要に見える場合でも、近傍探索、サンプリング、ハッシュ、事前集計などで候補を減らせないか検討します。計算量は設計段階でのリスク評価にも使います。
確認観点
確認観点としては、ループの数だけでなく、各ループが入力サイズに対して何回回るかを見ることです。二重ループでも片方が定数なら二乗にはならないため、処理回数の増え方を言葉で説明できるようにします。
結論として、この問題では「用語の定義」だけでなく、どの前提で使えるのか、どの誤解を避けるべきか、実務では何を確認するのかまで結びつけて理解することが重要です。