プログラミング学習の記録 628.3 11章(探索とソート)の練習問題１ 『初めてのコンピュータサイエンス』(Jennifer Campbell, Paul Gries, Jason Montojo, Greg Wilson 著、長尾 高弘 訳、オライリー・ジャパン、2010年、ISBN978-4-87311-463-7)

開発環境

• Mac OS X Snow Leopard (OS)
• WingIDE
• Script言語: Python

『初めてのコンピュータサイエンス』(Jennifer Campbell, Paul Gries, Jason Montojo, Greg Wilson 著、長尾 高弘 訳、オライリー・ジャパン、2010年、ISBN978-4-87311-463-7)の11章(探索とソート), 11.7(練習問題), 1を解いてみる。

 

1.

組込みの探索はリストの長さNに比例、二分探索はソートでNlog_2N、実行時間はリストの長さの対数log_2Nに比例ということで、おおよそ(n*log_2n)/(n-log_2n)回以上探索した時、ソートした方が高速になる？あってるのかな〜