計算量の比較
O(n log n)はO(n^2)より高速。nが大きいほどオーダ差が拡大とは？
意味
計算量O(n log n)はO(n^2)よりも増加が緩やかで、データ数が増えるほど処理時間の差が広がる。オーダの比較が速さの判断基準になる。 ▍なぜ正解 nが十分大きいとき、計算量の増え方が小さいほど高速になる。表でクイックソートだけがO(n log n)で、他のO(n^2)より緩やかに増えるため平均的に最も高速である。 ▍よくある間違い 少数データの体感で判断し、オーダの違いを無視する。 ▍試験の狙い 「nが大きいとき」の速さ比較はオーダ（計算量）だけを見る。
?応用情報技術者試験での問われ方
表は代表的な整列アルゴリズムと平均計算量を示す。データ数nが十分に大きいとき、平均的に最も高速に整列できるアルゴリズムはどれか。
答え：O(n log n)はO(n^2)より高速。nが大きいほどオーダ差が拡大
✓覚え方
nlognは二乗より速い。
「O(n log n)はO(n^2)より高速。nが大きいほどオーダ差が拡大」を、演習で定着させる。
無料ではじめる →応用情報技術者試験の過去問を、一問ごとの8-ways解説つきで。まずは無料で。
登録は1分・クレジットカード不要。無料のまま練習・暗記カード・模試まで使えます。
ukamiru 用語集 · 応用情報技術者試験