شرح تدوين Big O بالأمثلة

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

ما هو تدوين Big O وكيف يعمل؟

ببساطة ، يخبرك تدوين Big O بعدد العمليات التي ستقوم بها الخوارزمية. تحصل على اسمها من الحرف "Big O" أمام العدد المقدر للعمليات.

ما لا يخبرك به تدوين Big O هو سرعة الخوارزمية في ثوانٍ. هناك العديد من العوامل التي تؤثر على الوقت الذي تستغرقه الخوارزمية في العمل. بدلاً من ذلك ، ستستخدم تدوين Big O لمقارنة الخوارزميات المختلفة بعدد العمليات التي تقوم بها.

يحدد Big O وقت تشغيل أسوأ حالة

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

أنت تعلم أن البحث البسيط يستغرق O (n) مرات للتشغيل. هذا يعني أنه في أسوأ الأحوال ، سيتعين عليك البحث في كل سجل (يمثله n) للعثور على سجل Jane.

ولكن عند تشغيل البحث البسيط ، تجد أن سجلات Jane هي الإدخال الأول في قاعدة البيانات. ليس عليك إلقاء نظرة على كل إدخال - لقد وجدته في المحاولة الأولى.

هل استغرقت هذه الخوارزمية وقت O (n)؟ أو هل استغرق الأمر وقتًا (1) لأنك عثرت على سجلات جين في المحاولة الأولى؟

في هذه الحالة ، 0 (1) هو أفضل سيناريو - لقد كنت محظوظًا لأن سجلات جين كانت في القمة. لكن تدوين Big O يركز على السيناريو الأسوأ ، وهو 0 (n) للبحث البسيط. إنه لطمأنة أن البحث البسيط لن يكون أبدًا أبطأ من وقت O (n).

تنمو أوقات تشغيل الخوارزمية بمعدلات مختلفة

افترض أن الأمر يستغرق 1 مللي ثانية للتحقق من كل عنصر في قاعدة بيانات المنطقة التعليمية.

من خلال البحث البسيط ، إذا كان عليك التحقق من 10 إدخالات ، فسوف يستغرق الأمر 10 مللي ثانية للتشغيل. ولكن باستخدام خوارزمية البحث الثنائي ، ما عليك سوى التحقق من 3 عناصر ، والتي تستغرق 3 مللي ثانية للتشغيل.

في معظم الحالات ، ستتكون القائمة أو قاعدة البيانات التي تحتاج إلى البحث فيها من مئات أو آلاف العناصر.

إذا كان هناك مليار عنصر ، فسيستغرق استخدام البحث البسيط ما يصل إلى مليار مللي ثانية ، أو 11 يومًا. من ناحية أخرى ، سيستغرق استخدام البحث الثنائي 32 مللي ثانية فقط في سيناريو أسوأ الحالات:

من الواضح أن أوقات التشغيل للبحث البسيط والبحث الثنائي لا تنمو بنفس المعدل تقريبًا. مع زيادة حجم قائمة الإدخالات ، يستغرق البحث الثنائي وقتًا أطول قليلاً للتشغيل. يزداد وقت تشغيل البحث البسيط أضعافًا مضاعفة مع زيادة قائمة الإدخالات.

هذا هو سبب أهمية معرفة كيفية زيادة وقت التشغيل بالنسبة إلى حجم القائمة. وهذا هو بالضبط المكان الذي يكون فيه تدوين Big O مفيدًا جدًا.

يظهر تدوين Big O عدد العمليات

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

فيما يلي بعض الخوارزميات الشائعة وأوقات تشغيلها في تدوين Big O:

تدوين Big O خوارزمية المثال
O (تسجيل ن) بحث ثنائي
على) بحث بسيط
O (ن * تسجيل ن) كويكسورت
على 2) اختيار نوع
على!) مندوب مبيعات السفر

الآن أنت تعرف ما يكفي لتكون خطيرًا مع تدوين Big O. انطلق إلى هناك وابدأ في مقارنة الخوارزميات.