IT PASSPORT
ITパスポートの問題解説
問題
データ件数 n に対する処理時間の増え方を表す計算量のうち、n が大きくなったときに最も処理時間の増加が緩やかなものはどれか。
- ア O(n²)
- イ O(n)
- ウ O(n log n)
- エ O(log n)
出典：オリジナル問題｜参考範囲：IPA ITパスポート試験シラバス（最新版）、情報処理技術者試験の基礎知識
正解と解説
正解：O(log n)
解説：計算量（オーダー）はデータ件数 n が増えたときに処理時間がどの程度増えるかの目安を表します。O(log n) は範囲を半分ずつ絞る二分探索のような処理で、n が1,000倍になっても処理回数はおよそ10倍程度しか増えません。これに対し O(n) は比例、O(n log n) は効率の良い整列、O(n²) は二重ループの単純な整列などに対応し、この順に増え方が急になります。一般的な大小関係は log n ＜ n ＜ n log n ＜ n² であり、アルゴリズムを選ぶ際はこの増え方の違いが大規模データで決定的な差を生みます。
覚え方：「log n は半分ずつ＝最も省エネ」「n² は二重ループ＝最も重い」。グラフにすると log n は寝そべった曲線、n² は急上昇する曲線とイメージできます。
他の選択肢はなぜ違う？
- アO(n²)はデータが10倍になると処理時間が約100倍になり、選択肢の中で最も急激に増加します。
- イO(n)はデータ件数に比例して増えるため、対数的に増えるO(log n)よりも増加は速くなります。
- ウO(n log n)はO(n)よりさらに大きく、効率の良い整列法などの計算量で、O(log n)より増加は速いです。
この問題について
IPAのITパスポート試験シラバスとIT基礎知識を参考に、Sikaku Master向けに独自作成した問題です。公式試験問題・過去問題の転載ではありません。
IPAの過去問題の転載ではなく、シラバス・公開情報に基づく独自問題として作成しています。