ランダム化されたクイック ソートの場合、少なくとも 25% から 75% の割合で分割されるようにピボットを選択すると、実行時間はO(n log n). また、これをマスター定理で証明できることも知りました。
しかし、私の問題は、各ステップで配列を 25% から 75% に分割した場合、どのように定義し、T(n)どのようにランタイム分析を証明できるかということO(n log n)です。
質問する
840 次
1 に答える
2
マスター定理を使用して、この種のアルゴリズムの複雑さを見つけることができます。この特定のケースでは、配列を 2 つの部分に分割するときに、これらの部分のそれぞれが最初の配列の 3/4 を超えないと仮定します。次に、T(n) < 2 * T(3/4 * n) + O(n)、またはT(n) = 2 * T(3/4 * n) + O(n)上限を探す場合。マスター定理は、この方程式の解を提供します。
更新:マスター定理はそのような再帰方程式を解くかもしれませんが、この場合、予想される O(n*log n) よりも悪い結果が得られます。それにもかかわらず、それは他の方法で解決できます。ピボットが常に小さい方のサイズが 1/4 サイズ以上になるように配列を分割すると仮定すると、再帰の深さを log_{4/3}N として制限できます (各レベルで配列のサイズが減少するため)少なくとも 4/3 回）。各再帰レベルの時間の複雑さは合計で O(n) であるため、全体の複雑さは O(n) * log{4/3}n = O(n*log n) になります。
さらに、より厳密な分析が必要な場合は、ウィキペディアの記事を検討してください。いくつかの優れた証拠があります。
于 2013-07-22T19:05:19.240 に答える