تحليل تعقيد الوقت للحلقات المتداخلة

في هذا الكود، لدينا حلقتان متداخلتان. دعونا نحسب عدد العمليات التي تحدث في كل حلقة، ثم نقوم بتحليل كيفية تأثير حجم المدخل (المتغير n) على العمليات الكلية.

لنقوم بتحليل الحلقة الخارجية أولاً، التي يكون فيها المتغير k يبدأ من n/2 ويقلّ تقسيماً على 2 في كل تكرار حتى يصل إلى 0. هذه الحلقة ستتكرر log(n) مرة، حيث يتم تقسيم n/2 في كل تكرار. لكل تكرار، يتم تنفيذ الحلقة الداخلية.

الآن لنقوم بتحليل الحلقة الداخلية، التي يتم فيها تكرار المتغير m من 0 إلى n-1. لذلك، ستتم تنفيذ الحلقة الداخلية n مرة.

لذا، إجمالي عدد العمليات هو ناتج ضرب عدد مرات تكرار الحلقة الخارجية بعدد مرات تكرار الحلقة الداخلية. وهو ما يمكن تعبير عنه بالتالي:

عدد العمليات = O(log(n) * n)

بما أن العامل الأساسي هو n، فإن وقت التشغيل الأسوأ سيكون O(n log(n)).

لتأكيد ذلك، يمكنك ملاحظة