algorithm - Big O 記法を比較する

Question

n 要素配列の並べ替え処理では、次の処理が必要です。
X アルゴリズムでは 10 ^-8 n ²秒、
Y アルゴリズムでは 10 ^-6 n log ₂ n 秒、
Z アルゴリズムでは 10 ^-5秒。

私の質問は、それらをどのように比較するかです。たとえば、y は x に応じて高速に動作します。どの要素数を選択すればよいでしょうか?

score 10 · Accepted Answer

Big-Oh 記法を比較するときは、すべての定数を無視します。

N^2 の成長率は N*log(N) よりも高く、それでも O(1) [定数] よりも急速に成長します。

N の累乗が成長率を決定します。

例：

O(n^3 + 2n + 10) > O(200n^2 + 1000n + 5000)

定数を無視すると (純粋に大規模な比較を行う必要があるため)、これは次のようになります。

O(n^3 + n) > O(n^2 + n)

低次の項を無視してさらに簡約すると、次の結果が得られます。

O(n^3) > O(n^2)

N の力だから3 > 2です。

Big-Oh は、次のような階層に従います。

O(1) < O(log[n]) < O(n) < O(n*log[n]) < O(n^x) < O(x^n) < O(n!)

(ここで、x は 1 より大きい任意の量であり、ごくわずかな値でもあります。)

ここには掲載しませんが、ウィキペディアで調べてください。O(n*log[n])並べ替えアルゴリズムではかなり一般的であるため、リストします。異なる底または異なる累乗を持つ対数の詳細については、参照元を確認してください (ウィキペディアについて言及しましたか?)

score 0 · Accepted Answer

まだ受け入れられた答えがないので、この別の解決策を提案します。

あるアルゴリズムが別のアルゴリズムよりも優れたパフォーマンスを発揮するの値を知りたい場合は、nアルゴリズムの時間を互いに等しく設定し、について解く必要がありnます。

例えば：

X = Z  
10^-8 n^2 = 10^-5  
n^2 = 10^3  
n = sqrt(10^3)
let c = sqrt(10^3)

したがって、とを比較するときXは、がより小さい場合とより大きい場合Zを選択します。これは、他の 2 つのペア間で繰り返される可能性があります。XncZnc

2 に答える 2