二分探索– tag –
-
コンピュータ科学 深掘り
計算量と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)でもメモリのアクセス順で数倍変わることを測り、なぜ最後は必ず測るのかまで見ます。 -
コンピュータ科学 深掘り
線形探索と二分探索 — 1回引くだけなら並べると損
「二分探索のほうが速い」は、並べる時間を勘定に入れていない。ソートは O(n log n)、探索は O(log n)。1回しか引かないなら、線形探索のほうが速い。何回引いたら並べるべきかを、実際に交差点が出るまで測る。二分探索の実装でよく踏む3つの間違いをわざと出して直し、「見つからないときどこに入れるか」を返す版まで作る。最後にハッシュとの使い分け、総当たりが正解になる場面、そして git bisect が二分探索そのものだという話。 -
プログラム
1万件で100倍になる — 計算量とO記法を測る
O記法は見たことがあるけれど説明はできない、という状態を終わらせます。数学は使いません。配列から1件探す処理を1000件から100万件まで測って、時間が件数に比例することを表で見る。Mapに変えると件数を増やしても変わらないことを見る。二重ループの重複検出が1000件から1万件で100倍になるところを実測し、Setで書き換えて桁を戻す。二分探索が100万件を20回で終えることをカウンタで数え、並べ替えのコストと、nが小さいときは二重ループのほうが速いという実測まで。証明はしません。全部、自分のVMで数字を出します。
1