كيفية calcualte الكبير-O تعقيد الخوارزمية التالية?

Question

كنت أحاول حساب Big-O من الخوارزمية التالية و هو يخرج إلى 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.هذا يعني أن الثانية متداخلة حلقة سيتم تشغيل ما مجموعه Sigma(i^2) from i=1 to i=n لذلك ما مجموعه n*(n+1)*(2n+1)/6 مرات.وبالتالي فإن إجمالي المبلغ الذي رمز تشغيل خرج أن يكون في أمر من n^5 لذلك خلصت إلى أن النظام يجب أن يكون O(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_{k=1}^{n/2} 1$$ $$=\فارك{ن}{2}(\sum_{i=1}^{n}\sum_{j=1}^{i^2}1)$$ $$=\فارك{ن}{2}(\sum_{i=1}^{n}ط^2)$$ $$=\فارك{ن}{2} \cdot (\فارك{1}{6}n(n+1)(2n+1))$$ $$=O(n^4)$$

---

حيث الفعلية رمز الكفاءة ، حيث x=y+z ثابتة في حلقة ، أي خير أمثلية برنامج التحويل البرمجي استخراج بيان من الحلقة (مترجم في الكلام ، يرفعون بيان حلقة preheader) ، ومن ثم جعل التعليمات البرمجية المترجمة تشغيل في $O(1)$.