الفكرة ببساطة
Big O تصف حدا أعلى لنمو عدد الخطوات مع كبر المدخل. ابدأ بعد الخطوات اللي تتكرر مع n.
حلقتان متتاليتان تعمل كل وحدة n مرة تعطيان 2n خطوة. لو الثانية داخل الأولى وتعمل n مرة لكل دورة خارجية، يصير العدد n × n.
مثال محلول
نعد الأزواج المرتبة من قائمة طولها n، بما فيها كل عنصر مع نفسه.
for x in items:
for y in items:
compare(x, y)لو القائمة فيها 4 عناصر، compare تشتغل 16 مرة. إذا المقارنة ثابتة الكلفة، فالزمن O(n²).
انتبه لهالنقطة
شوف عدد دورات الحلقة الداخلية لكل دورة خارجية. أحيانا الداخلية تعمل عددا ثابتا من المرات.
جرّب بنفسك
لو الحلقة الخارجية تعمل n مرة والداخلية تعمل 3 مرات دائما، وش التعقيد؟
اعرض الإجابة
O(n). السطر الداخلي ينفذ 3n مرة.