次のアルゴリズムのビッグO複雑さを計算する方法
-
29-09-2020 - |
質問
次のアルゴリズムのBIG-Oを計算しようとしており、MEのO(N ^ 5)になりました。私は正しい答えが何であるかわからないが、私の同僚のほとんどがo(n ^ 3)を手に入れています。
for(i=1;i<=n;i++)
{
for(j=1 ; j <= i*i ; j++)
{
for(k=1 ; k<= n/2 ; k++)
{
x = y + z;
}
}
}
.
私がやったことが最も内側のループから始められました。したがって、最も内側のループがn/2
時間を実行すると、i^2
がi
からi
に変わるため、1
がn
時間を実行すると、2番目にネストされたループに入ります。これは、2番目のネストされたループがSigma(i^2) from i=1 to i=n
で合計を実行することで、合計のn*(n+1)*(2n+1)/6
時間が実行されます。したがって、コードが実行される合計金額は、n^5
の順序で発行されました。このアプローチと私が計算した答えに何か問題がありますか?
私はDSAから始めたばかりで、これは私の最初の課題でしたので、私が作ったかもしれない基本的な間違いをお詫び申し上げます。
解決
for(i=1;i<=n;i++)
{
for(j=1 ; j <= i*i ; j++)
{
for(k=1 ; k<= n/2 ; k++)
{
x = y + z;
}
}
}
.
トリプルネストされたループは合計に相当します $$ \ sum_ {i= 1} ^ {n} \ sum_ {j= 1} ^ {i ^ 2} \ sum_ {1} ^ {n / 2} 1$$ $$=frac {n} {2}(\ sum_ {i= 1} ^ {n} \ sum_ {j= 1} ^ {i ^ 2} 1)$$ $$=frac {n} {2}(\ sum_ {i= 1} ^ {n} i ^ 2)$$ $$=frac {n} {2} \ Cdot(\ frac {1} {6} n(n + 1)(2n + 1))$$ $$= o(n ^ 4)$$
実際のコード効率の観点から、
x=y+z
はループ内に不変であるため、任意の良好な最適化コンパイラがループからステートメントを抽出します(コンパイラ語、Loop Preheaderへのステートメントをホイスト)したがって、コンパイル済みコードが $ o(1)$ で実行されるようにする。 所属していません cs.stackexchange