二分探索の計算量がなんでO(log2 N)になるのか、
FEの勉強などで出てきても適当に飛ばしていましたが、
最近アルゴリズムを改めて書くようになり、触れる機会があったので
計算してみました。
図にするとこのようになります。
最大の探索回数で考えるので、
N個のデータからある値を二分探索する場合
計算回数をx回とすると、N/(2^x)が１となるまで繰り返します。
N/(2^x)=1
2^x=N
log2(2^x)=log2N
x=log2N
となり
二分探索の計算量は
O(log2N)
となることがわかります。
対数って感覚的に掴みずらくて、今までサラッと通り過ぎていましたが
図にすることで理解しやすくなりました。