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

解説

階乗n!は1×2×3×…×nという乗算の繰返しで求められ、ループ変数を1からnまで動かして順に掛ければ乗算の回数はn−1回である。処理回数が入力nに比例するため、計算量はO(n)となり、イが正解である。再帰関数で実装した場合も関数呼出しがn回発生するだけなので同じくO(n)である。アのO(1)は入力サイズによらず一定時間で終わる処理（配列の添字アクセスなど）、ウのO(n^2)は二重ループを伴う処理（単純なソートなど）、エのO(2^n)は組合せ爆発を起こす指数時間の処理に対応し、いずれも単純なループ1つで計算できる階乗には当てはまらない。基本情報技術者試験では、プログラムのループ構造から計算量のオーダを判定する問題が頻出であり、ループの重なりの数と計算量の対応（1重→O(n)、2重→O(n^2)）を押さえることがポイントである。