تعقيد خوارزمية الحوسبة - الارتباك

Question

لدي مقتطف الكود التالي:

sum = 0;
for (i = 0; i < n; i++)
    for (j = 0; j < i; j++)
        sum++;

سيكون التعقيد O(n^2), ، ولكن إذا كنت أرغب في البحث أكثر قليلاً عن تعقيد الحلقة الداخلية فهل سيكون كذلك (n (n-1))/2 أو (n-1)!?

Answer 1

نعم، o (n ^ 2)، ولكن في الواقع 0 + 1 + ... + N-1 = n (n-1) / 2 = o (n ^ 2)، بالتأكيد ليس (n-1)!

Answer 2

time = n*(n-1)/2
     = (n*n - n)/2

نظرا لأن التدوين Big-o هو الحد العلوي، فإن مصطلح النظام الأقل (-N) والعامل الثابت (1/2) كلاهما يتم إزالته (لأنهم ليسوا مهمين لتمثيل الحد الأعلى في الوقت المحدد) لإحداث كبير o تدوين O(n*n) المعروف باسم O(n^2).

Answer 3

هل يمكن أن يكون لديك خوارزمية تعمل في الوقت المناسب

22222222222222 + 4444444444444*n + 9999999999999999999999999*n^2 steps

وستظل س (ن ^ 2).

إنها مشكلة مفتوحة للعثور على وصف أفضل لمرحلة تشغيل الخوارزمية من O.

Answer 4

الثوابت غير ذات صلة بقدر ما يتعلق بتدويز كبير.

Answer 5

ما تحسب (n(n-1)/2) هو العدد الدقيق للتكرارات للحصول على الكود. عندما سئل عن تعقيد الوقت من حيث ذلك إذا كانت كبيرة س، فإنك تعطي تقديرا كبيرا بما يكفي للتعبير عن الوقت المستغرق.

وبعبارة أخرى، تحتاج إلى العثور عليها THE SMALLEST power من n بحيث بالنسبة للبعض k (k>0), k * n^power سيكون أكبر من العدد الدقيق للتكرارات. في حالتك، k يحدث أن تكون 1 و power يحدث أن تكون 2. وبعد ثم O(n^power) هو تعقيد وقتك.

Answer 6

أولاً، (n-1)! وسائل (n-1)(n-2)...(2)(1).من الواضح أن هذا ليس ما تريده هنا.

إذا قمت بحساب العدد الفعلي للتكرارات 0 + 1 + 2 + ... + (n-2) + (n-1).لاحظ أن هناك n الحدود في المجموع، وأنه يمكننا إقرانها بطريقة تجعل متوسط ​​قيمة كل زوج هو (n-1)/2.(قم بإقران الأعلى والأدنى، وثاني أعلى وثاني أدنى، وما إلى ذلك) إذا n أمر غريب، سيكون لديك واحدة متبقية لا يمكن إقرانها، ولكن قيمتها أيضًا ملائمة (n-1)/2.هكذا لديك n حيث ومتوسط ​​جميع المصطلحات هو (n-1)/2, ، وبالتالي فإن المبلغ الإجمالي هو n(n-1)/2.

الآن، بالنسبة لتدوين O الكبير، لا يهم بالضبط عدد التكرارات لدينا -- نريد فقط معرفة الحد الأقصى متى n كبيرة جدا.لاحظ أنه يمكن كتابة عدد التكرارات لدينا كـ (1/2)n^2 - (1/2)n.لكبيرة جداً n, ، ال n^2 المصطلح هو الطريق، وسيلة أكبر من n المصطلح، لذلك نحن إسقاط n شرط.هذا يتركنا فقط (1/2)n^2, ، ولكن هناك قاعدة أخرى للتدوين الكبير O وهي أننا لا نهتم بالعامل الثابت، لذلك نكتب فقط أنه O(n^2).