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

2.3

 最良、平均、最悪時の分析

■

15

ここで示された実験結果が実装に間違いないことを示しているので、満足してよい。

2.3

 最良、平均、最悪時の分析

前の節での結果が、すべての入力問題インスタンスに成り立つかどうかは、調べ

なければならない。

Sort-2

の振る舞いは、異なる同じサイズの入力問題インスタン

スに対してどのように変化するのだろうか。

●

データが既にソート済みの多数の要素を含む可能性がある。

●

入力値が重複していることもある。

●

入力集合のサイズ

n

にかかわらず、要素がさらに小さな集合から取り出され、

重複値が多いこともある。

図2-1の

Sort-4

は、

n

個のランダム文字列をソートする

4

つのアルゴリズムの中で

最も遅いが、データがほとんどソートされている場合には、最速となる。この利点

は図2-2に示されるように

32

個のランダムに選ばれた要素が本来の位置にないだけ

で急速に失われる。

しかし、

n

個の文字列の入力配列が、「ほぼソートされている」すなわち、文字列

の

4

分の

1

（

25

％）が、

4

個分だけ離れた要素と入れ替わったような場合には、驚く

べき結果となる。図2-3では、

Sort-4

は、他のどれよりも速くなる。

多くの問題に当てはまる結論とは、「すべてに対する唯一の最適アルゴリズムは存

在しない」ということだ。アルゴリズムの選択は、解くべき問題の理解、インスタン

スの裏にある確率分布、そして、候補アルゴリズムの振る舞いによって決められる。

1

つの指針として、アルゴリズム性能が通常は次の

3

つの場合について提 ...