التعقيد الزمني للأزواج في حلقة الصفيف المزدوجة

Question

واعلم أن ما يلي: يا (ن ^ 2),

int count = 0;
for(int i = 0; i<array.length(); i++) {
   for(int j = i+1; j<array.length(); j++) {
       if(array[i] == array[j]) {
           count = count + 1;
       }
   }
}

ولكن، ينبغي أن يكون هناك شيء من هذا القبيل count = count + 1; أن تؤخذ بعين الاعتبار؟للتنبؤ أو تكوين معادلة زمنية معقدة، أو استخدام تدوين المجموع،

n + n-1 + n-2 + n-3 + (…) + 1

Answer 1

إنها مهمة معروفة "التحقق من التكرارات" ويمكنك العثور عليها على سبيل المثال في Tim Roughgarden - الخوارزميات المضيئة _ الجزء 1 _ الأساسيات - (2017) 42 صفحة.اسمحوا لي أن أقول، كما هو الحال هنا في الكتاب مع أخذ الفهرس الأخير "i" كـ $ن=$"array.length()" ليس لها أي معنى، لأن الفهرس "j" ينفد خارج الحدود.ولكن هذا لا يؤثر على العد لدينا.

كما هو الحال دائمًا، فإن الشيء الرئيسي هو اختيار عملية العد - هنا "count = count + 1".من الواضح أن أفضل حالة، أي.أقل قدر من العمليات، هو $0$.والحالة الأسوأ، أي.الحد الأقصى من العمليات هو المبلغ (أقوم بتصحيحه وفقًا لذلك مع رفع المؤشر "i". $ن-1$) جلبت من قبلك $T(n)=1+2+\cdots+(n-1)=\frac{n(n-1)}{2}$ (نحن نعتبر القضية $n\geqslant 2$).

الآن بسبب $\frac{n(n-1)}{2} \leqslant \frac{n\cdot 2n}{2}=n^2$, ، فمن السهل أن نستنتج أن هذه الحالة أسوأ $T(n) \في O(n^2)$.

Answer 2

يعتمد التعقيد الزمني للخوارزمية على نموذج الحساب.عادة ما يتم تحليل الخوارزميات في جهاز ذاكرة الوصول العشوائي (RAM)، حيث تكلف العمليات الأساسية على الكلمات الآلية (مثل التعيين والحساب والمقارنة) $O(1)$.الكلمة الآلية لها طول $O(\log n)$, ، أين $ن$ هو حجم الإدخال.

في حالتك، يكون حجم الإدخال على الأقل $ن$ (يتم تعريفه على أنه طول array)، و حينئذ count تناسبها في كلمة آلة واحدة.كل من العمليات الأساسية في تكلفة الخوارزمية $O(1)$, ، وبالتالي فإن التعقيد الزمني الإجمالي هو $ \ ثيتا (ن ^ 2) $, نظرًا لأن الخوارزمية تنفذ العديد من العمليات الأساسية.