クイックソートアルゴリズムに必要なパス数を計算する式はありますか？

クイックソートアルゴリズムを使っている間に、特定の値のセットが昇順で完全にソートされるために必要な数式や種類のパスが見つからないかどうかは疑問でした。クイックソートアルゴリズムに必要なパス数を計算する式はありますか？

クイックソートアルゴリズムには、パス数を計算する計算式はありますか？

2011-12-24 Dinesh

平均して、 'O（nlog n）'です。最悪の場合は 'O（n²）'です。それはあなたが探しているものですか？または、既知の量のデータがあれば、*特定のケースについて計算しますか？ –

あなたはピボットnaively_を選んだ場合、_O（N log（N））ベストケース、O（N^2）最悪の場合とは異なる何かをお探しですか？あなたが探しているものはどのように違うのですか？ – sarnold

任意の指定された値のセットは、ピボットの値の選択方法とソートされる実際の値に基づいて、異なる数の操作を持ちます。

「O（N log（N））とO（N^2）の間の近似が十分に良い場合を除き、そうではありません。 1は最悪のケースに対する平均を修飾する必要があります

は、操作の数を決定する唯一の方法は、実際にクイックソートを実行することであることを示すために十分なはずです。

2011-12-24 09:38:53 Cyberfox

答えて