次のアルゴリズムのビッグO複雑さを計算する方法

Question

次のアルゴリズムの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から始めたばかりで、これは私の最初の課題でしたので、私が作ったかもしれない基本的な間違いをお詫び申し上げます。

Answer 1

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）$ で実行されるようにする。