Big O Notation - شرح ببساطة مع الرسوم التوضيحية والفيديو

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

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

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

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

يجب أن تكون الخوارزمية المختارة سريعة وصحيحة. من ناحية ، البحث الثنائي أسرع. وغالبًا ما يكون لدى يهوذا حوالي 3 ثوانٍ فقط قبل أن يشعر صديقه بالملل بحثًا عن لعبة. من ناحية أخرى ، من الأسهل كتابة خوارزمية بحث بسيطة ، وهناك فرصة أقل لحدوث أخطاء. بالتأكيد سيكون محرجًا إذا وجد صديقه أخطاء في شفرته! لتوخي مزيد من الحذر ، قرر يهوذا ضبط الوقت لكلتا الخوارزميتين بقائمة من 100 لعبة.

لنفترض أن الأمر يستغرق 1 مللي ثانية للتحقق من لعبة واحدة. من خلال البحث البسيط ، يتعين على يهوذا فحص 100 لعبة ، وبالتالي يستغرق البحث 100 مللي ثانية للتشغيل. من ناحية أخرى ، يتعين عليه فقط التحقق من 7 ألعاب باستخدام بحث ثنائي (السجل 2100 هو 7 تقريبًا ، لا تقلق إذا كانت هذه الرياضيات مربكة لأنها ليست النقطة الرئيسية في هذه المقالة) ، لذلك يستغرق البحث 7 مللي ثانية يهرب. لكن في الحقيقة ، ستحتوي القائمة على مليار لعبة. إذا كان الأمر كذلك ، فكم من الوقت سيستغرق البحث البسيط؟ كم من الوقت سيستغرق البحث الثنائي؟

وقت التشغيل للبحث البسيط مقابل البحث الثنائي ، مع قائمة من 100 عنصر

تقوم Judah بإجراء بحث ثنائي باستخدام مليار لعبة ، وتستغرق 30 مللي ثانية (log2 1،000،000،000 يساوي 30 تقريبًا). "32 مللي ثانية!" يعتقد. "البحث الثنائي أسرع بنحو 15 مرة من البحث البسيط ، لأن البحث البسيط استغرق 100 مللي ثانية مع 100 عنصر ، والبحث الثنائي استغرق 7 مللي ثانية. لذا فإن البحث البسيط سيستغرق 30 × 15 = 450 مللي ثانية ، أليس كذلك؟ أقل بكثير من 30 ثانية التي يستغرقها صديقي ليشعر بالملل ". قرر يهوذا أن يذهب مع بحث بسيط. هل هذا هو الاختيار الصحيح؟

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

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

لذا كان يهوذا مخطئًا بشأن كون البحث الثنائي دائمًا أسرع 15 مرة من البحث البسيط. إذا كان هناك مليار لعبة ، فستكون أسرع بمقدار 33 مليون مرة.

من المهم جدًا معرفة كيفية زيادة وقت التشغيل مع زيادة حجم القائمة. وهنا يأتي دور تدوين Big O.

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

اين الثواني؟ لا يوجد شيء - لا يخبرك Big O بالسرعة في ثوانٍ. يتيح لك تدوين Big O مقارنة عدد العمليات. يخبرك بمدى سرعة نمو الخوارزمية.

لنقم بمثال آخر. احتياجات البحث الثنائية السجل ن عمليات للتحقق من قائمة حجم ن . ما هو وقت التشغيل في تدوين Big O؟ انها O (سجل ن ). بشكل عام ، يتم كتابة تدوين Big O على النحو التالي.

يخبرك هذا بعدد العمليات التي ستقوم بها الخوارزمية. يطلق عليه تدوين Big O لأنك وضعت "كبير O" أمام عدد العمليات.

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

افترض أنك تستخدم بحثًا بسيطًا للبحث عن مستخدم في قاعدة بيانات المستخدم الخاصة بك. أنت تعرف أن بحث بسيط يأخذ O ( ن ) وقت إلى المدى، وهو ما يعني في أسوأ الحالات، سوف تقوم الخوارزمية يجب أن ننظر من خلال كل مستخدم في قاعدة البيانات. في هذه الحالة ، أنت تبحث عن مستخدم باسم "aardvark213". هذا هو المستخدم الأول في القائمة. لذلك لم يكن على الخوارزمية الخاصة بك النظر في كل إدخال - لقد وجدته في المحاولة الأولى. هل استغرقت الخوارزمية وقت O ( n )؟ أم أنها استغرقت وقت O (1) لأنها وجدت الشخص في المحاولة الأولى؟

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

بعض أوقات تشغيل Big O الشائعة

فيما يلي خمس أوقات تشغيل Big O ستواجهها كثيرًا ، مصنفة من الأسرع إلى الأبطأ:

  • O (log n ) ، المعروف أيضًا باسم وقت السجل. مثال: بحث ثنائي.
  • O ( n ) ، المعروف أيضًا باسم الوقت الخطي . مثال: بحث بسيط.
  • س ( ن * سجل ن ). مثال: خوارزمية فرز سريعة ، مثل الترتيب السريع.
  • يا ( ن 2). مثال: خوارزمية فرز بطيئة ، مثل فرز الاختيار.
  • يا ( ن !). مثال: خوارزمية بطيئة حقًا ، مثل مندوب المبيعات المتنقل.

تصور أوقات تشغيل Big O المختلفة

لنفترض أنك ترسم شبكة من 16 مربعًا ، ويمكنك الاختيار من بين 5 خوارزميات مختلفة للقيام بذلك. إذا كنت تستخدم الخوارزمية الأولى ، فسوف يستغرق الأمر O (log n ) وقتًا لرسم الشبكة. يمكنك إجراء 10 عمليات في الثانية. مع وقت O (log n ) ، سوف يستغرق الأمر 4 عمليات لرسم شبكة من 16 مربعًا (log 16 base 2 هو 4). لذلك سوف يستغرق الأمر 0.4 ثانية لرسم الشبكة. ماذا لو كان عليك رسم 1،024 صندوقًا؟ سوف يستغرق الأمر 1،024 = 10 عمليات ، أو ثانية واحدة لرسم شبكة من 1،024 صندوقًا. هذه الأرقام تستخدم الخوارزمية الأولى.

الخوارزمية الثانية أبطأ: تستغرق وقت O ( n ). سيستغرق سحب 16 صندوقًا 16 عملية ، وسيستغرق سحب 1،024 صندوقًا 1،024 عملية. كم من الوقت هذا بالثواني؟

إليك المدة التي سيستغرقها رسم شبكة لبقية الخوارزميات ، من الأسرع إلى الأبطأ:

هناك أوقات تشغيل أخرى أيضًا ، ولكن هذه هي الخمس مرات الأكثر شيوعًا.

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

استنتاج

فيما يلي النقاط الرئيسية:

  • لا تُقاس سرعة الخوارزمية بالثواني ، بل تقاس بنمو عدد العمليات.
  • بدلاً من ذلك ، نتحدث عن مدى سرعة زيادة وقت تشغيل الخوارزمية مع زيادة حجم الإدخال.
  • يتم التعبير عن وقت تشغيل الخوارزميات في تدوين Big O.
  • O (log n ) أسرع من O ( n ) ، لكنها تزداد سرعة مع نمو قائمة العناصر التي تبحث عنها.

وها هو الفيديو الذي يغطي الكثير مما في هذه المقالة وأكثر.

آمل أن يكون هذا المقال قد قدم لك مزيدًا من الوضوح حول تدوين Big O. تستند هذه المقالة إلى درس في دورة الفيديو الخاصة بي من Manning Publications يسمى Algorithms in Motion. تعتمد الدورة على كتاب Grokking Algorithms الرائع من تأليف Adit Bhargava. إنه الشخص الذي رسم كل الرسوم التوضيحية الممتعة في هذه المقالة.

إذا كنت تتعلم بشكل أفضل من خلال الكتب ، احصل على الكتاب! إذا كنت تتعلم بشكل أفضل من خلال مقاطع الفيديو ، ففكر في شراء الدورة التدريبية الخاصة بي. يمكنك الحصول على خصم 39٪ على المقرر الدراسي الخاص بي باستخدام الرمز " 39carnes ".