プログラム板雑談スレッド Part 3

プログラム板雑談スレッド Part 3 at TECH

219:デフォルトの名無しさん
08/06/11 11:04:54
>>217
拾ってきたコードで試したら、比較回数はクイックソートより少し多かった。

>>218
引き分けがないとすると、140!通りの並べ替えがありうる。
140!通りに分岐させるためにはlog(140!)/log(2)回以上の比較が必要。
log(140!)/log(2)を計算すると801.01...。
だから、（比較のみによる）どんなに優れたソートアルゴリズムを使っても、
ワーストケースでは必ず802回以上の比較を要する。

次ページ

続きを表示

1を表示