ホーム » スタッフ » 斉藤徹 » 講義録 » 情報構造論 » 処理時間のオーダー(回答編)

2019年4月
« 3月   5月 »
 123456
78910111213
14151617181920
21222324252627
282930  

最近の投稿(電子情報)

アーカイブ

カテゴリー

処理時間のオーダー(回答編)

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β ✕ log10100=Tβ✕2

Tβ=5μsec

よって、

T(10000) = 5μsec✕log1010000=20μsec

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

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

解答

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

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

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

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