計算量とO記法 — データが10倍で100倍遅くなる
テストデータ100件では一瞬だった処理が、本番の10万件で固まりました。原因は「遅いコード」ではなく「データが増えると時間が何倍になるか」を見ていなかったことでした。この記事ではVMの中に小さな計測台を作り、O(1)・O(log n)・O(n)・O(n log n)・O(n²)・O(2ⁿ) の6つを実際に走らせて、nを10倍にしたとき時間が何倍になるかを表にします。定数を無視する理由も、nとn²/100が逆転する交差点を実測して確かめます。最後に、同じO(n)でもメモリのアクセス順で数倍変わることを測り、なぜ最後は必ず測るのかまで見ます。