2分探索法の処理時間の見積もり

コンピュータで2分探索法で、データ100件で10[μsec]かかったとする。
データ10000件なら何[sec]かかるか？

解答

2分探索法なので、処理時間はO(logN) であり、T(N) = T_α+T_β✕N で表される。

T(100) =10μsec = T_β✕ log 100

となる。ここで、logの底は、底変換の公式を使うと、底の違いはT_β に含めて考えればいいので、今回は10を底にして考える。

10μsec = T_β ✕ log₁₀100=T_β✕2

T_β=5μsec

よって、

T(10000) = 5μsec✕log₁₀10000=20μsec

処理時間の式をオーダ表記

の処理時間を要するアルゴリズムを、オーダー記法で書くとどうなるか？

解答

ここで問題となるのは、 との値が、Nが巨大な値の時にどっちが大きいかが問題となる。

そこで、それぞれの値を分子分母にして N→∞で、∞に拡散するか、0に収束するかを判定すればいい。

ここで、ロピタルの定理より、分子分母をそれぞれ微分すると、

よって、分子の方が巨大な値になるので、この処理時間は、で表せる。