お、もう日付が変わるなー。 じゃあ、もうおしまいにしよう。 疲れる前に止める。堅苦しくないのが続ける秘訣。次はハッシュ法だよ。

2-2-3はデータ挿入のコストの話。 そうか、検索だけじゃなくて挿入のコストを考えなきゃいけないときも多いよな。 リニアとバイナリのデータ挿入における違い。 リニアはソート不要なので、リストの最後にデータをくっつけるだけ。 一方、バイナリは常にリス…

2分探索法の肝をメモ ポイント 最初にデータをソートすることが必要 着目範囲の上限と下限を常に設定する 上限と下限から真ん中を算出し、目的のキーと真ん中を比較する キーと真ん中との大小をみることで、真ん中を上下に移動させる。 真ん中を移動するとき…

おっと、わすれてた。2-4は途中で力尽きて放棄してたんだ。 線形探索法の計算量 ループの中は各回に1回づつ実行される処理なので、ループ内はO(1)。 そしてwhileループの平均実行回数はO(n/2)となる。 これは、ちょっと回すと結局O(n)になってしまう。 あと…

ということで、今日はバイナリサーチこと、2分探索法をやる。 binary search。いい響き。 2分探索法って 前回の線形探索法との違いは、ほとんど以下の関数に集約される。 前回のsearch()を以下に置き換えればok。 int binary_search(int key){ int low, high…

なんか、前回の日記からずいぶんと間があいてしまったなー。 時間が空いた理由は、きっちりやろうとしすぎていたからかな。 ともかく手が伸びなかったのだから心の奥底で気が重かったんだと思う。改善策は、ここのところ考えていたので導けた。いままでは「…