基本情報技術者 予想問題｜A 第21問

解説

正解はウ。外側のforループは変数iが1からnまでn回繰り返し、その各回について内側のforループも変数jが1からnまでn回繰り返す。したがって内側の「処理」の実行回数はn×n＝n²回となり、計算量はO(n²)である。アのO(1)はループのない定数時間の処理、イのO(n)は一重ループで全体をn回処理する場合、エのO(log n)は二分探索のように対象範囲が毎回半分になる処理のオーダーであり、いずれも本問の二重ループには当てはまらない。基本情報ではプログラムの構造から計算量を読み取る問題が頻出であり、一重ループ＝O(n)、二重ループ＝O(n²)、範囲半減の繰返し＝O(log n)を基本パターンとして、内側ループの回数がiに依存する変形にも対応できるようにしたい。