計算量（オーダー記法）

📖 もうちょい詳しく

何が新しいの？

これは新しい技術というより、プログラムの「速さの見立て方」として昔から使われている考え方です。同じ結果を出すプログラムでも、データが増えたときに急に遅くなるものと、あまり遅くならないものがあります。その違いを共通のものさしで比べるために、計算量という見方が生まれました。

どうやって動いてるの？

計算量は、扱うデータの個数（よく n で表します）が増えたとき、処理の手間がどんな勢いで増えるかをざっくり表します。たとえば O(n) はデータが2倍になれば手間もおよそ2倍、O(n^2) はデータが2倍なら手間はおよそ4倍に増える、という意味です。細かい秒数ではなく「増え方の形」だけに注目するのがポイントです。

何ができるの？

コードを書く前に「このやり方はデータが多くなると耐えられるか」を予想できます。たとえば1万件で動いていた処理が100万件で急に固まる、といった事故を、実際に動かす前に見抜く手がかりになります。

🌱 身近なたとえ

本棚から1冊の本を探す手順で例えると分かりやすいです。背表紙を端から1冊ずつ見ていく探し方は、本が増えるほど見る回数も比例して増えるので O(n) です。あいうえお順に並んでいて「真ん中を見て前か後ろか絞る」探し方なら、本が2倍に増えても見る回数は1回増える程度で済み、これが O(log n) です。並べ方を工夫するだけで、増え方の勢いがこれだけ変わります。

✅ まず覚えるポイント

• n は扱うデータの個数を表します。
• O( ) の中身は「データが増えたときの手間の増え方」を表します。
• O(1) は件数に関係なく一定、O(n) は比例、O(n^2) は二乗で増えます。
• 細かい秒数ではなく、増え方の「形」を比べるための目安です。
• データが少ないうちは差が出にくく、増えると差が大きく開きます。

🧭 よくある勘違い

O(n) は O(n^2) よりいつも速いの？

増え方が緩やかなだけで、いつも実際に速いとは限りません。データが少ないうちは、O(n^2)のやり方のほうが速い場合もあります。計算量はあくまで「データが増えたときの傾向」を示すもので、その時々の実測の速さを保証するものではありません。

計算量が小さければそれで完成なの？

増え方の目安が分かるだけで、実際の速さはマシンの性能やメモリの使い方にも左右されます。計算量は設計の方向性を選ぶための材料の一つで、最後はやはり実際に測って確かめることが多いです。

🧩 関連して覚えると楽な言葉

• アルゴリズム: 問題を解く手順のことで、計算量はその手順の良し悪しを測るものさしです。
• データ構造: データの並べ方・しまい方で、選び方しだいで計算量が大きく変わります。
• インデックス（索引）: データベースで目的の行を速く探す仕組みで、探す計算量を下げてくれます。
• キャッシュ: 一度使った結果を取っておく仕組みで、同じ処理の手間を減らせます。

🏁 ひとことでまとめ

データが増えたときに処理がどれくらいきつくなるかを、O(n)のような形で先読みするための見方です。