الخوارزميات وتحليل تعقيد الوقت في Loops

تحليل تعقيد الوقت للخوارزميات هو تحديد كمية الموارد (مثل الوقت والتخزين) اللازم لتنفيذها، وتحليل وقت التشغيل هو تصنيف نظري يقدّر ويتوقع الزيادة في وقت التشغيل للخوارزمية مع زيادة حجم الإدخال (يشار إليه عادةً بـ “n”)، وتعد كفاءة وقت التشغيل موضوعًا ذا أهمية كبيرة في علوم الكمبيوتر، حيث يمكن أن يستغرق البرنامج ثوانٍ أو ساعات أو حتى سنوات لإنهاء التنفيذ، اعتمادًا على الخوارزمية التي ينفذها.

تحليل التعقيد وقت لـ Loops:

دعنا نقوم بمناقشة تحليل البرامج التكرارية بأمثلة بسيطة:

1- O(1):

يعتبر التعقيد الزمني لدالة (أو مجموعة من العبارات) على أنه “O(1)” إذا لم تكن تحتوي على “loop” واستدعاء ذاتي وإستدعاء لأي دالة أخرى تعقيدها الزمني غير ثابت، على سبيل المثال، دالة “()swap” لها تعقيد زمني “O(1)”، يعتبر أيضاً “loop” أو الاستدعاء الذاتي الذي يتم تشغيله بعدد ثابت من المرات أيضًا “O(1)”؛ لأن اللوب سيعمل دائماً بعدد ثابت من المرات، على سبيل المثال، الـ “loop” التالي هو “O(1)”:

2- O(n):

يعتبر التعقيد الزمني للحلقة هو “O(n)”، إذا تم زيادة أو إنقاص متغيرات “loop” بمقدار ثابت (في كل مرة سيزيد أو ينقص المتغير “i” بمقدار ثابت)، على سبيل المثال، الدالة التالية لها تعقيد زمني “O(n)”:

3-  O(n^c):

التعقيد الزمني للحلقات المتداخلة (nested loops) يساوي عدد المرات التي يتم فيها تنفيذ العبارة الأعمق، وتعد خوارزمية الترتيب بالإدراج مثال على تعقيد الوقت “O(n²)”،على سبيل المثال، تحتوي الـ “loops” التالية على تعقيد زمني “O(n²)”، ففي كل مرة سيزيد اللوب الخارجي بمقدار “c” فإن اللوب الداخلي سيمشي من (1 إلى n):

4- O(Logn):

يعتبر التعقيد الزمني للحلقة هو “O(Logn)” إذا كانت متغيرات الـ “loop”مقسمة أو مضروبة بمقدار ثابت، على سبيل المثال، تحتوي خوارزمية البحث الثنائي على تعقيد زمني “O(Logn)”، دعونا نرى رياضيا كيف هو “O(log n)”، السلسلة التي نحصل عليها في الحلقة الأولى هي (c¹، c²، c³،… c^k)، وإذا وضعنا (k = Log_cn)، فسنحصل على (c^Log_cn) وهو (n).

 

5- O(LogLogn):

يعتبر التعقيد الزمني للحلقة هو “O(LogLogn)” إذا تم تقليل أو زيادة متغيرات الحلقة أضعافًا مضاعفة بمقدار ثابت، كما في المثال التالي:

كيفية الجمع بين التعقيدات الزمنية للـ loops المتتالية؟

عندما تكون هناك مجموعة من الـ “loops” المتتالية، فإننا نقوم بحساب تعقيد الوقت كمجموع التعقيدات الزمنية للـ “loops” كلٌ على حدى.