オーダー記法（ビッグオー） とは？

データの個数がnのとき、処理にどのくらいのステップがかかるかを表しているよ。O(n)はデータが2倍になれば処理も2倍かかる。O(log n)はデータが2倍になっても処理はたった1ステップ増えるだけの超効率的な処理。O(n²)はデータが2倍になれば処理は4倍かかる。

ビッグオーは「データが大量になったとき全体の傾向」を見るためのものだから。「2n」と「3n」はどちらもO(n)で、データが100万件になれば「2倍か3倍か」より「n倍かn²倍か」の違いの方がはるかに重要になる。大きな絵を見るための記法だよ。

パフォーマンスが問題になったときに考えるよ。「なんでこんなに遅いんだろう」と調べると、O(n²)のループが入れ子になっていてデータが増えると急激に遅くなっていた、というケースはよくある。コードレビューでも「これはO(n²)になってない？」という指摘は実際によく出てくるよ。

ソートアルゴリズムの代表格だね。マージソートやクイックソート（平均ケース）がO(n log n)で、これは「比較ベースのソートの理論上の最速」なんだ。面白いのは、O(n log n)は「データをn回処理するけど、毎回半分に分割していくからlog n回で済む」というイメージで理解できること。100万件のデータでもlog₂(1,000,000)≒20だから、O(n²)の1兆回に対してO(n log n)は2000万回程度。この差が実務で「使い物になるかどうか」を分けるんだよ。