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

 

8.

リストの要素が一意になっている(つまり、複数回登場する要素がない)場合、長さNのリストで問題のslowsortアルゴリズムの期待される実行時間はN!(Nの階乗)。理由は、リストの要素をアットランダムに並べ替えた結果はNの階乗個で、要素が一意になっているのでNの階乗個のうちソートされているのは1個だから。

要素が一意かどうかが問題になっている理由は上記に書いたように、一意でない場合はNの階乗個のなかに重複する結果があるので、一意の場合よりも期待される実行時間は速くなるから。