問題 No.2754
あるECサイトのシステム開発において、商品検索機能を改善するために、アルゴリズムの計算量に関する検証を行った。データ数$N$に対する処理時間の増加傾向を表すオーダー記法（ビッグオー記法）に関して、最も適切な記述はどれか。
【正解の解説】
データ数が多くなったときの処理時間の増加の度合いを大まかに表すために用いられる。
ビッグオー記法は、料理のレシピに例えると「人数が10人から100人に増えたとき、調理時間が直線的に増えるか、それとも爆発的に増えるか」の大まかなトレンドを把握するものです。実際のストップウォッチでの測定時間ではなく、データが増えたときの「伸び代のルール」を数学的にスッキリ表現するための便利な道具として使われます。
スポンサーリンク
【その他の選択肢の解説】
データ数が多くなったときの実際の実行時間をミリ秒単位で正確に予測するために用いられる。
初学者が陥りやすい罠として「オーダー $O(N)$ なら必ず何ミリ秒で終わる」と数字そのものを信じてしまう誤解があります。ビッグオー記法は定数倍を無視して大まかな傾向を見るため、パソコンの性能やプログラミング言語の違いによる実際のミリ秒単位の正確な実行時間は予測できません。
データ数が少なくなったときのハードウェアの消費電力を大まかに表すために用いられる。
アルゴリズムの計算量は基本的に「CPUがどれだけ計算の手間をかけるか」という時間的なコストやステップ数に着目します。消費電力や発熱量といった物理的なハードウェアの特性を直接測るものではないため、省電力性能と混同しないよう注意が必要です。
データ数が多くなったときのメモリ使用量の増減傾向を正確に排除するために用いられる。
ビッグオー記法はメモリの消費量を表すためにも使われることがありますが、この選択肢にあるような「正確に排除する」という目的ではありません。また、空間計算量としてメモリ増加の傾向を表すことはあっても、値を排除する概念とは全く異なるため出題者の巧妙な引っかけとなっています。