はじめに
今回は前回までの続きになる。今回は二分探索と$O$記法についての学びをメモ程度にまとめていきたい。
目次
1. 前回の補足
2. 二分探索
3. ランダウのO記法
4. まとめ
1. 前回の補足
前回の記事では$O(N)$のように計算量としては示したが、実行時間はどう計算すんねんと。
今読んでいるアルゴリズム×数学が基礎からしっかり身につく本曰く、一般家庭にあるコンピュータの計算速度は $1s$あたりに$10^9$回程度であるらしいので、その前提で行くと以下のように計算できる。
(使用しているPCのCPUスペックなどにもよって変わる)
-
$O(N)$の場合
$N=10^7$の時、$\frac{10^7}{10^9}=10^{-2}[s]$ -
$O(N^2)$の場合
$N=10^6$の時、$\frac{10^6*10^6}{10^9}=10^3[s]$
他にも$O(logN)$(二分探索で扱うよ)とかもあるので興味ある人は計算してみると良いかも。
2. 二分探索
二つの枝に分かれた木のようなイメージ。
これに関しては本の例が一番わかりやすかったのでそれを参考に書く。
(例)
あなたの友人に1~8までの整数を思い浮かべてもらいその数字をいくつか質問をして求める
というゲームをしたと仮定する。
例えば普通に1から昇順に「あなたが思い浮かべてるのは1ですか？」のように質問していくと相手が8を思い浮かべているときは最後まで質問しなければならず、$O(N)$の線形探索となる。
二分探索は上記の例で行くとまず半分に割ってしまおう。
「4以下ですか？」
こうすることでYESであろうとNOであろうと数字を半分に絞れる！
後は繰り返すだけですね！
これを数式として追っていくと以下のようになる。
$2^{B-0}, 2^{B-1}, 2^{B-2},2^{B-3} = 8, 4, 2, 1$
$B$は質問の残り回数とでも思ってください。
今回のケースだと最大3回質問すれば絞れるので上記のように3回目で1となっています。
このように半分に絞れていくことから質問回数Bは(オーダー)は以下のようになる。
$N=2^B$より両辺対数をとって$B=\log_2N$となる。
今回だと$N=8$あるので代入すると$B=3$となる。
対数なんで$N$が小さければあまり変わりはないもしくは線形探索のほうが若干速いかも。
しかし！！！
前回も体感した通り、データ数が多いと全探索なんてやってらんねぇ！
そこで対数を扱う関数にです！
上記の例だと、たとえ$N=1000000$であろうと質問回数は20回で済みます！
速いって正義ですね。
3. ランダウのO記法
実際には上記のようにプログラムが簡単な関数で表せればいいのですが実際はより複雑な式になると思います。
でも大丈夫！
だって支配的な項だけ残してやればいいんだもん。(とか言いつつ、すべてがすべてそうであると私は言えませんが^_^;)
以下の例で上記について説明できればと思う。
- (例)
$T(N)=N^2+2N$
という関数を考えたとき、$N=1000$とすると$N^2=1000000$、$2N=2000$となりボトルネックなのは明らかに$N^2$となるので$N^2$が支配的な関数といえます。
なので$2N$を消して簡略化してやる。すると
$T(N)=N^2$となる。
あら、きれい。
他にも以下のようにしてきれいにできる。
- (例2)
$T(N)=2N^2+5N+7$
二次関数ですね。
でも上記通りでいくと支配的なのは$2N^2$ですね。
ほか、消しちゃいましょう。
$T(N)=2N^2$
2の係数も倍になったところで指数の変化量に比べれば微々たるもの。
消してしまえ！ (はいぃぃぃ！！！)
$T(N)=N^2$
うむ、きれいである。よろしい。
と、計算量を見積もるときは関数の支配的にとなっている部分の項を残すようにして簡略化して考えようということ。
4. まとめ
結論、速いは正義！
まじめな話、私自身あまり処理時間やその見積もり、$O$記法について知識がなかったのでとても勉強になりました。ただ、データ数が少なければ直感的で実装が簡単な線形、全探索あたりでもいいとは思うので塩梅大事ですね。
そのために今日学んだ知識を生かして私もこれから見積もりを立てて実装していきたいですね。