0

n < 100 の場合は n^2 が nlogn よりも高速であり、n >= 100 の場合はその逆であることを理解しようとしています。正しい方向。n < 100 O(n^2) が高速で、n > 100 O(nlogn) が高速であるため、n = 100 で交差するグラフの 2 つの関数を描くことができます。

an^2+b と c*nlog(n)+d を思いついた

ここでの私の理解の鍵は、違いを生む定数です。しかし難しいのは、上記のシナリオを満たす定数を考え出す必要があることです。行われている方法やテクニックはありますか、それとも間違った方向に正しく進んでいますか?

元の質問: James と Brad は、並べ替えアルゴリズムのパフォーマンスについて議論しています。James は、彼の O(N logN) 時間アルゴリズムは、Brad の O(N2) 時間アルゴリズムよりも常に高速であると主張しています。この問題を解決するために、彼らはランダムに生成された多くのデータセットに対して 2 つのアルゴリズムを実装して実行しました。James ががっかりしたことに、N < 100 の場合、O(N2) 時間のアルゴリズムの方が実際には高速に実行され、N >= 100 の場合のみ O(N logN) 時間のアルゴリズムの方が優れていることがわかりました。上記のシナリオが可能な理由を説明してください。数値例を挙げることができます。

4

3 に答える 3

1

あなたがすでに持っている式、an^2+b と c*nlog(n)+d を取ります

n を 100 に置き換え、それらを等しく設定します。これにより、a、b、c、および d の関係が示されます。その制約に準拠する一連の値を選択します。

于 2013-09-12T03:03:32.440 に答える
1

各方程式の各変数が何を意味するかを考えてみてください。私は先に進み、特定の変数を無視し (必要に応じて 0 または 1 に設定します)、残された決定変数が何を意味するかに焦点を当てます。A、B、C、D はそれぞれ何を意味し、これらの変数の境界は何ですか? たとえば、負のランタイムは問題ではないため、変数が負になることはありません。当たり前のように聞こえますが、問題は内容ではなく方向性でした。追加の利点として、A = C = 1 にして、B と D を操作してみてください。

于 2013-09-12T03:25:09.640 に答える
0

以下のリンクは、2 つの関数が交差する明確なケースをプロットで示しています。具体的な例で理解するのに役立つと思います。

http://mohalgorithmsorbit.blogspot.com/2013/12/complexity-theory-approaching.html

于 2014-03-01T15:54:46.203 に答える