ما هو-O كبير من حلقة متداخلة، حيث يتم تحديد عدد التكرارات في حلقة داخلية من التكرار الحالي للحلقة الخارجية؟

Question

ما هو الوقت المناسب تعقيد كبير-O من الحلقات المتداخلة التالية:

for(int i = 0; i < N; i++) 
{
    for(int j = i + 1; j < N; j++)
    {
        System.out.println("i = " + i + " j = " + j);
    }

}

وسيكون من O (N ^ 2) لا يزال؟

Answer 1

نعم، انها لا تزال O (ن ^ 2)، فقد عاملا ثابتا أصغر، ولكن هذا لا يؤثر O التدوين.

Answer 2

نعم. أذكر تعريف BIG-O: <م> O (و (ن)) بالتعريف يقول إن وقت التشغيل <م> T (ن) ≤ <م> KF (ن) لبعض ثابت <م> ك . في هذه الحالة، فإن عددا من الخطوات يكون <م> (ن 1) + (ن 2) + ... + 0 ، التي تعيد ترتيب لمجموع 0 إلى n-1؛ هذا هو

T (ن) = (ن 1) ((ن 1) +1) / 2 .

وإعادة ترتيب ذلك، ويمكنك أن ترى أن <م> T (ن) سوف يكون دائما ≤ 1/2 (n²)؛ في تعريف، وبالتالي <م> T (ن) = O (n²) .

Answer 3

وانها N مربع إذا كنت تجاهل System.out.println. إذا كنت تفترض أن الوقت من قبل أن يؤخذ سيتم خطية في انتاجها (التي قد جيدا لن يكون، بطبيعة الحال)، وأظن أن ينتهي بك الأمر مع O ((N ^ 2) * تسجيل N).

وأنا أذكر هذا لا يكون من الصعب إرضاءه، ولكن فقط أن أشير إلى أن لا تحتاج فقط لاتخاذ الحلقات واضحة في الاعتبار عند العمل بها تعقيد - كنت بحاجة الى ان ننظر في تعقيد ما تسمونه فضلا

Answer 4

نعم، سيكون N المربعة. العدد الفعلي من الخطوات ان مبلغ 1 إلى N، وهو 0.5 * (N - 1) ^ 2، إذا لم أكن مخطئا. يا كبير يأخذ في الاعتبار فقط أعلى exponant وليس الثوابت، وبالتالي، فإن هذا لا يزال N المربعة.

Answer 5

إذا كان لديك N = 10، هل التكرار على النحو التالي: 10 + 9 + 8 + 7 + 6 + 5 + 4 + 3 + 2 + 1. (هذا هو: عشرة تكرارات بالاضافة الى تسعة التكرار بالإضافة إلى ثمانية تكرارات ... الخ).

والآن، عليك أن تجد في إضافة عدد المرات التي يمكنك الحصول على N (10 في المثال):

1: (10)، 2: (9 + 1)، 3: (8 + 2)، 4: (7 + 3)، 5: (6 + 4). الذي هو 5 مرات ... وتقع 5 تكرارات.

والآن أنت تعرف أن لديك خمسة عشرات + 5:

و10 (5) + 5

في شروط و (ن) (أو N)، يمكننا أن نرى بسهولة أن هذا من شأنه أن يكون:

و (ن) = ن (ن / 2) + ن / 2 = (ن ^ 2) / 2 + ن / 2 = (ن ^ 2 + ن) / 2 ... وهذا هو بالضبط تعقيد هذه حلقة متداخلة.

ولكن، بالنظر إلى السلوك مقارب الكبير O، يمكننا أن نتخلص من القيم أقل أهمية من و (ن)، والتي هي ن واحد والقاسم.

والنتيجة: O (ن ^ 2)

Answer 6

وAFAIL، التي بدأت من الحلقة الداخلية من خلال الخارجي منها هو وسيلة كافية لحساب حلقة تعقيد متداخلة.