الواجب المنزلي للتدوين الكبير - تحليل خوارزمية جزء التعليمات البرمجية؟[مغلق]

Question

بالنسبة للواجب المنزلي، تم إعطائي أجزاء التعليمات البرمجية الثمانية التالية لتحليلها وإعطاء تدوين Big-Oh لوقت التشغيل.هل يمكن لأحد أن يخبرني إذا كنت على الطريق الصحيح؟

//Fragment 1
for(int i = 0; i < n; i++)
    sum++;

أفكر في O(N) للجزء 1

//Fragment 2
for(int i = 0; i < n; i+=2)
    sum++;

O(N) للجزء 2 أيضًا

//Fragment 3
for(int i = 0; i < n; i++)
    for( int j = 0; j < n; j++)
        sum++;

O(N^2) للجزء 3

//Fragment 4
for(int i = 0; i < n; i+=2)
    sum++;
for(int j = 0; j < n; j++)
    sum++;

O(N) للجزء 4

//Fragment 5
for(int i = 0; i < n; i++)
    for( int j = 0; j < n * n; j++)
        sum++;

O(N^2) للجزء 5 لكن n * n يزعجني قليلاً لذلك لست متأكدًا تمامًا

//Fragment 6
for(int i = 0; i < n; i++)
    for( int j = 0; j < i; j++)
        sum++;

O(N^2) للجزء 6 أيضًا

//Fragment 7
for(int i = 0; i < n; i++)
    for( int j = 0; j < n * n; j++)
        for(int k = 0; k < j; k++)
            sum++;

O(N^3) للجزء 7 ولكن مرة أخرى فإن n * n يطردني

//Fragment 8
for(int i = 1; i < n; i = i * 2)
    sum++;

O(N) للجزء 8

Answer 1

أعتقد أن الجزء 5 هو O(n^3)، وبالمثل الجزء 7 هو O(n^5)*.يبدو أيضًا مثل O(log(n)) للجزء 8.

بالنسبة لمشاكل n * n، يجب عليك تنفيذ نص الحلقة n * n مرات، بحيث يكون O(n^2)، ثم تقوم بتركيب ذلك بترتيب الكود الآخر.يقوم الجزء 8 في الواقع بمضاعفة العداد بدلاً من زيادته، لذا كلما كبرت المشكلة، قل العمل الإضافي الذي يتعين عليك القيام به، لذا فهو O(log(n))

*يحرر: الجزء 7 هو O(n^5)، وليس O(n^4) كما اعتقدت سابقًا.وذلك لأن كلاً من j و ك انتقل من 1 إلى ن * ن.آسف لم أتمكن من فهم هذا في وقت سابق.

Answer 2

وجزء 7 هو O (ن ^ 5)، وليس O (ن ^ 4) كما يدعي تعليق المقبولة حاليا. خلاف ذلك، فمن الصحيح.

Answer 3

لحالة 8 حاول أن تكتب بها عدد التكرارات لبعض قيم N ونرى ما يبدو نمط مثل ... أنها ليست O (N)

Answer 4

ويبدو أنك على الطريق الصحيح. وفيما يتعلق N * N ما تأثير هل تعتقد أنه سيكون؟ ذلك هو عامل آخر من N لذلك من المرجح أن تكون مرتبة أعلى.

ومجرد تحذير، ورأيت وظيفة أخرى من هذا القبيل، وكان صوت عليه للغاية. كن حذرا. هنا هو آخر.

Answer 5

أنت على الطريق الصحيح، ولكن إليك نصيحة حول كيفية جعل الأمور أكثر وضوحًا على طول الطريق.لنفترض أن لديك بعض التعليمات البرمجية:

for(i = 0; i < n; i++) {
   for(j = 0; j < 100; j++){....}
}

حسنًا، ضع في اعتبارك حقيقة أن لديك تعليمات برمجية على مستويات مختلفة.في هذا المثال، يمكنك رؤية 3 مستويات فقط حتى الآن:

1. الحلقة for الخارجية التي تبدأ من 0-n
2. حلقة for أخرى تتراوح من 0 إلى 100
3. بعض التعليمات البرمجية في الداخل، والتي تم وضع علامة عليها كـ ...

لا ينبغي عليك في أي وقت من الأوقات أن تحاول حساب كل ذلك دفعة واحدة.هذا هو المكان الذي يرتكب فيه معظم المبتدئين نوعًا من الأخطاء الحسابية.احسبها بشكل فردي لكل مستوى ثم اضربها معًا.

حظ سعيد!