ما هو تدوين Big-O؟

هل تساءلت يومًا عن سبب استغراق برنامج كتبته وقتًا طويلاً لتشغيله؟ ربما ترغب في معرفة ما إذا كان بإمكانك جعل شفرتك أكثر كفاءة. يمكن أن يؤدي فهم كيفية تشغيل التعليمات البرمجية إلى الارتقاء بالكود الخاص بك إلى المستوى التالي. تدوين Big-O هو أداة مفيدة لحساب مدى كفاءة الكود الخاص بك حقًا.

ما هو تدوين Big-O؟

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

كيفية تنزيل مقاطع فيديو youtube مجانًا

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

كيف تحسب تدوين Big-O

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

الخوارزمية 1:

def sockCounter(numberOfPairs):  
 individualSocks = 0  
 for x in range(numberOfPairs):  
 individualSocks = individualSocks + 2  
 return individualSocks

الخوارزمية 2:

def sockCounter(numberOfPairs):  
 return numberOfPairs * 2

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

ذات صلة: ما هي وظيفة في البرمجة؟

الخوارزمية 1 لها العديد من الخطوات:

يقوم بتعيين قيمة صفر للمتغير الفردي الجوارب.
يعين قيمة واحدة للمتغير i.
يقارن قيمة i بـ numberOfPairs.
يضيف اثنين من الجوارب الفردية.
إنه يعين القيمة المتزايدة للجوارب الفردية لنفسه.
يزداد أنا بواحد.
ثم يعود مرة أخرى خلال الخطوات من 3 إلى 6 لنفس عدد مرات (indiviualSocks - 1).

يمكن التعبير عن عدد الخطوات التي يتعين علينا إكمالها للخوارزمية على النحو التالي:

4n + 2

هناك أربع خطوات علينا إكمالها n مرة. في هذه الحالة ، ستساوي n قيمة numberOfPairs. هناك أيضًا خطوتان تم إكمالهما مرة واحدة.

بالمقارنة ، فإن الخوارزمية 2 لديها خطوة واحدة فقط. يتم ضرب قيمة numberOfPairs في اثنين. نود أن نعبر عن ذلك على النحو التالي:

1

إذا لم يكن الأمر واضحًا بالفعل ، فيمكننا الآن أن نرى بسهولة أن الخوارزمية 2 أكثر فاعلية إلى حد ما.

تحليل Big-O

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

في الأمثلة أعلاه ، سيتم التعبير عن الخوارزمية 2 على أنها واحدة:

O(1)

ولكن سيتم تبسيط الخوارزمية 1 على النحو التالي:

O(n)

تخبرنا هذه اللقطة السريعة عن كيفية ارتباط كفاءة الخوارزمية الواحدة بقيمة n. كلما زاد الرقم زادت الخطوات التي ستحتاج الخوارزمية لإكمالها.

كود خطي

حقوق الصورة: Nick Fledderus / مشروع نون

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

كود تربيعي

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

def searchForValue(targetValue, arraySearched):  
 foundTarget = False  
 for x in arraySearched:  
 for y in x:  
 if(y == targetValue):  
 foundTarget = True  
 return foundTarget

في هذا المثال ، يعتمد عدد الخطوات على عدد المصفوفات في arraySearched وعدد القيم في كل مصفوفة. لذا ، فإن العدد المبسط من الخطوات سيكون n * n أو n².

ماذا تفعل عندما يتم اختراق الفيسبوك

حقوق الصورة: Nick Fledderus / مشروع نون

هذه العلاقة هي علاقة تربيعية ، مما يعني أن عدد الخطوات في خوارزمية لدينا ينمو أضعافًا مضاعفة مع n. في تدوين Big-O ، يمكنك كتابته على النحو التالي:

O(n²)

الكود اللوغاريتمي

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

log 2 (8) = 3

اللوغاريتمات يساوي ثلاثة لأنه إذا كانت قاعدتنا 2 ، فسنحتاج إلى قيمة أس 3 لنصل إلى الرقم 8.

حقوق الصورة: Nick Fledderus / مشروع نون

إذن ، علاقة الدالة اللوغاريتمية هي عكس العلاقة الأسية. مع زيادة n ، يتطلب الأمر عددًا أقل من الخطوات الجديدة لتشغيل الخوارزمية.

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

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

كما ترى ، نظرًا لأن عمليات البحث الثنائية تقضي على نصف القيم المحتملة في كل عملية مرور ، فكلما زادت قيمة n ، فإن التأثير على عدد المرات التي نتحقق فيها من المصفوفة يتأثر بالكاد. للتعبير عن هذا في تدوين Big-O ، نكتب:

O(log(n))

أهمية تدوين Big-O

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

كيفية توصيل جهاز تحكم xbox one الجديد

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

يشارك يشارك سقسقة بريد الالكتروني أكثر 10 أخطاء شائعة في البرمجة والترميز

يمكن أن تؤدي أخطاء الترميز إلى العديد من المشاكل. ستساعدك هذه النصائح على تجنب أخطاء البرمجة والحفاظ على مغزى التعليمات البرمجية الخاصة بك.

اقرأ التالي مواضيع ذات صلة

برمجة
برمجة

نبذة عن الكاتب جينيفر سيتون(21 مقالة منشورة)

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

المزيد من Jennifer Seaton

اشترك في نشرتنا الإخبارية

انضم إلى النشرة الإخبارية لدينا للحصول على نصائح تقنية ومراجعات وكتب إلكترونية مجانية وصفقات حصرية!

انقر هنا للاشتراك