2

複雑さの分析と、それを第一原理から実行する方法について学ぼうとしています。例として QuickSort を取り上げます。このアルゴリズムの平均的なケースの複雑さの O 表記法を導出できるようにしたいと考えています。

私は QuickSort が O(nlog(n)) であることを知っており、その理由を理解しています。反復ごとに n 要素をパスする必要があり、再帰の深さは log n です。しかし、基本的な操作を数えることなど、第一原理でこれをどのように示すかわかりません。

4

1 に答える 1

1

Knuth は、The Art of Computer Programming、Volume 3 (Sorting and Searching)のセクション 5.2.2 (Sorting by Exchanges) で、(もちろん MIX で) クイックソートの具体的な実装の詳細な分析を示しています。彼はおそらく、人間が消費するために、この種の分析を手作業で行うのに十分気を配る世界で唯一の人物です.

于 2012-05-02T14:03:21.100 に答える