N*C*(logN +N) がアルゴリズム 1 の計算時間ステップを表し、N*C*(logN +N*C) がアルゴリズム 2 の計算時間ステップを表す場合、両方の計算の複雑さがO(N^2)?
※Cは定数値
4 に答える
1
はい、これが私の論理です：
O(Cn(log n + Cn))
定数を削除する
= O(n(log n + n))
分割乗算
= O(n * log n + n^2)
短い用語を削除する
= O(n^2)
が「非常に大きい」かどうかは関係ありません。Big -O表記でCのみ気にします。これは、成長する用語であるためです。nnが十分に大きくなると（たとえば、無限大に近づくと）、C意味がなくなります。実際Cには大きな影響を与える可能性がありますが、これはBig-Oで抽象化されています。
于 2013-02-26T05:39:21.193 に答える
1
はい、正しいです。 f \element O(g) ( Landau -Notation) は、アルゴリズムfがgよりも遅く増加することを意味するためです。どちらのアルゴリズムも n^2 より遅く増加するため、仮定は正しいです。
定数を書きます-これを説明させてください:)
複雑さがO(n^2)であるということは、nlog(n) から n^2 までの平面全体を意味します。それはあなたが定数を無視するところです。したがって、アルゴリズム a はアルゴリズム b よりもはるかに優れている可能性がありますが、これは上限を与えるだけであるため、同じランダウの複雑さのままです。
于 2013-02-26T05:43:57.213 に答える
0
はい、ステップ数に定数を掛けても、複雑さの Big-Oh 表記には影響しません。
また、N 2項は、N が大きくなるにつれて N log(N) を支配します。これは、Big-Oh 表記法が伝達するように設計されているものです。
于 2013-02-26T05:40:36.697 に答える
-1
覚えておくべきことの 1 つ.. c 値は重要な役割を果たします..
あるアルゴリズムが配列に対して 32 回のパスを実行するとします。
したがって、アルゴリズムの複雑さは 32*n = C*n = O(n) です。
30 の配列サイズでアルゴリズムを実行してみましょう。SO その 32*30 。これは n^2 操作です。
私たちは通常、大きなセットに対して Big O 分析を計算します..本当に大きいので、理にかなっています
あなたの質問に来ます。
定数 C が同等である限り、両方とも O(n^2) で実行されます。したがって、アルゴリズムに依存します
于 2013-02-26T05:47:15.063 に答える