プログラミング学習の記録 634.3 11章(探索とソート)の練習問題7 『初めてのコンピュータサイエンス』(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(練習問題), 7を解いてみる。

 

7.

値の挿入位置を判断するためにかかる時間はlog_2 Nだが、さらに値の挿入にも同じように時間がかかるので合計時間はN log_2 NではなくN(N + log_2 N)になる。よってNが大きい値なら、合計時間はN^2に近づいていくので選択ソートや挿入ソートに比べてあまり速度向上の貢献は無くなる。