كيفية calcualte الكبير-O تعقيد الخوارزمية التالية?
-
29-09-2020 - |
سؤال
كنت أحاول حساب 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 و كانت هذه أول مهمة لذا أعتذر عن أي الأخطاء الأساسية التي ارتكبتها.
المحلول
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)$.