アルゴリズムクイックリファレンス 第2版

386

■

12

章 結び：アルゴリズムの諸原則

を持たないことがわかっていれば単純になる。

6

章の

ダイクストラ法

では、辺の重み

の和が負となる閉路があれば、永遠に実行が続く。選択したアルゴリズムの特殊な

場合と仮定とをしっかり理解しておかねばならない。

既に述べたように、どのような状況にも常に最良の性能を提供する、ただ

1

つの

アルゴリズムは存在しない。どのような選択肢があるかさらにわかれば、データに

基づいて、最も適当なアルゴリズムを選ぶことができる。表12-1は、

4

章で述べた

整列アルゴリズムの結果をまとめている。当然、各アルゴリズムの最悪時性能が気

になるだろうが、これらのアルゴリズムを実装し使用するときの概念にも注意を払

うべきだ。

表12-1　整列アルゴリズム

アルゴリズム 最良 平均 最悪 概念 該当する節

バケツソート

n n n

ハッシュ 「4.6 バケツソート」

ヒープソート

n log n n log n n log n

再帰、二分ヒープ「4.3 ヒープソート」

挿入ソート

n n

2

n

2

貪欲 「4.1.1 挿入ソート」

マージソート

n log n n log n n log n

再帰、安定、分割

統治

「4.7.1 マージソート」

クイックソート

n log n n log n n

2

再帰、分割統治 「4.4 分割ベースのソート」の

「クイックソート」

選択ソート

n

2

n

2

n

2

貪欲 「4.2 選択ソート」

12.2

 問題を小さく分割せよ

問題を効率的に解くアルゴリズムを設計するときに、その問題が

2

つ（あるいは

それ以