1

質問はclrsからです（演習12.4-5）

n個の入力番号のシーケンスで動作するRANDOMIZED-QUICKSORTについて考えてみます。任意の定数k>0に対して、nのO（1 / n ^ k）を除くすべてを証明します。入力順列は、O（n lg n）の実行時間を生成します。

最悪の場合のモデルを構築し、その最大限界を取得するにはどうすればよいですか。

4

1 に答える 1

1

簡単な紹介のためにこのメモを読むことをお勧めします。次に、これ（特にセクション3.1）を読んで完全な説明を得ることができます。

于 2012-06-06T06:57:33.163 に答える