تعقيد الخوارزمية وتدوين Big O

دعونا نناقش تعقيد الخوارزميات ، وعلى وجه الخصوص كيف نقيسها في سياق الخوارزميات.

تستغرق الخوارزميات المختلفة ، نظرًا لنفس المشكلة التي يجب حلها ونفس المدخلات ، وقتًا مختلفًا لحل المشكلة.

في بعض الأحيان ، يكون هناك وقت مختلف بشكل كبير ، خاصة وأن عدد العناصر التي يحتاجون إليها لإدارتها ينمو

هذا التعقيد يسمىO كبير، دون أي سبب آخر لاستخدامنا للأحرف الكبيرةoالحرف كاتفاق:O(n)وO(1)وهكذا.

المقاييس الأكثر شيوعًا لـ Big O التي ستراها ، مرتبة حسب الأكثر كفاءة إلى الأقل كفاءة ، هي:

  • O(1)
  • O(log n)
  • O(n)
  • O(n * log n)
  • O(n^2)
  • O(n!)

أينnهو عدد المدخلات. على سبيل المثال ، إذا كنت بحاجة إلى فرز عنصرينnهي 2 ، وإذا كنت تريد فرز 20.000 عنصر ،nهو 20.000.

لكنك لست بحاجة إلى استبدال القيمة فيO()عملية حسابية. هذا رمز يهدف إلى الإشارة إلى المطورين وكل من يبحث في الخوارزميات عن فعاليتها.

خوارزمية معO(1)الكفاءة هي أفضل ما يمكن أن نجده. لا يعتمد وقت التنفيذ على عدد المدخلات ، بل يستغرق دائمًا نفس الوقت للتنفيذ

خوارزمية معO(n)مقاييسخطيامع عدد المدخلات. إذا استغرق الأمر ثانية واحدة مع 10 عناصر ، فسيستغرق الأمر 10 ثوانٍ مع 100 عنصر.

خوارزمية معO(n^2)، إذا كانت 4 عناصر تستغرق 16 ثانية ، فإن 10 عناصر تستغرق 100 ثانية.

سنقوم بتحليل وحساب كفاءة Big O لعدد كبير من الخوارزميات في الدروس التالية.

من المهم أن نلاحظ أن تدوين Big O لا يمنحنا جميع المعلومات التي نحتاجها للحكم على ما إذا كانت خوارزمية ما ستكون أسرع من خوارزمية أخرى ، لا سيما إذا كانت قيمة Big O هي نفسها. في هذه الحالة ، ستحتاج إلى استخدام أدوات أخرى لاختبار الكفاءة.

ولكن عندما تحتوي الخوارزميات على فئات مختلفة (O(n)ضدO(n^2)على سبيل المثال) ، ليس هناك شك.