学んだこと 計算量オーダー
ここに答えがありました。
全く関係ない記事ですがメモ用↓
値渡しと参照渡しの違いを理解する
またもやわかりやすい記事様です、それを自分用に改悪まとめます。間違ってたらごめんなさい。
そもそもlog(n)ってなんやねん
- 25とかでの5を求めるということ。
log2 8 の値を求めよ。とかいわれたら、2を何乗すると8になるかを求めよ、ということ。このとき2を底という。
以上復習です。
では記事に戻って、例えば1～32までの数字に対して5を見つけようという2分探索をするとして、
1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32
この32個の数からとりあえず16と比べて(1)
1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16
さらに8と比べて(2)
1,2,3,4,5,6,7,8
さらに4と比べて(3)
5,6,7,8
さらに半分して6と比べてどっちに含まれてるか調べて(4)
5,6
さらに半分してry(5)
5
やった！5が見つかりました。
これで、2分割の5乗で計算量は5ステップ (log(n)) となりました。
log_2 32は5なのでlog(n)のnはたぶん32のことです。32個データがあるということなので。
より一般に「n が毎ステップごとに定数分の１になる」場合の繰り返し回数は O(logn) になります。とのこと。
というか、上の参考元の記事の二つにすべてが載っています。知識0で読んでも？？？なので読む前の事前知識として考えていただけたら。
以上改悪でした。数学もう忘れててボロボロなのでほんとに高校の参考書でも買わないといけません。
何度も言いますが、間違ってる可能性大なので間違ってたら教えてください。
