الخوارزميات وكيفية تحليل تعقيدها

تشارك الخوارزميات في جميع المهام تقريبًا التي نقوم بها يوميًا. نقوم بتنفيذ العديد منها على "تلقائي" ، حتى بدون إدراك "ما" التي يتم استخدامها أو "كيف" نستخدمها. في تطوير البرمجيات ، ليس الأمر مختلفًا. ولكن ، ما هي الخوارزميات على أي حال؟ ولماذا من المهم تحليل تعقيدها؟

هيا نكتشف! :)

ما هي الخوارزمية؟

مجموعة من الخطوات اللازمة لأداء مهمة.

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

على سبيل المثال ، هل فكرت في الخوارزمية التي تنفذ المهام التالية؟

  • نظف اسنانك
  • استحم
  • يطبخ
  • قد إلى العمل من المنزل

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

  1. اركب سيارتي
  2. قد إلى منزل أحد الأصدقاء لركوبه
  3. قد إلى المكتب حيث أعمل
  4. أوقف سيارتي في مرآب السيارات

هذه هي مجموعة الخطوات (الخوارزمية) التي أحتاج إلى تنفيذها لإكمال هذه المهمة.

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

برامج الكمبيوتر ليست مختلفة للغاية: هناك مجموعة متنوعة من الخوارزميات التي يمكن استخدامها لتنفيذ سلسلة من المهام. في كثير من الأحيان ، لا نهتم لأنفسنا بما هي عليه ، نحن ببساطة نستخدمها (وأنا منهم).

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

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

ما هو تعقيد الخوارزمية؟

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

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

يسمح لنا تحليل تعقيد الوقت بتحديد كيفية تصرف الخوارزمية نظرًا لزيادة عناصر الإدخال الخاصة بها. يمكن أن يكون لدينا فكرة عن الوقت الذي ستستغرقه معالجة 10 أو 100 أو 1000 عنصر.

ولماذا هذا التحليل مهم؟

  • لتحديد الخوارزمية الأكثر فعالية ؛
  • لتكون قادرة على تطوير خوارزميات أكثر كفاءة ؛
  • أن تكون قادرًا على تحليل ما إذا كانت مكتبة الخوارزمية ، أو حتى لغتها الفعلية ، فعالة.

وباختصار ، فإن الكفاءة هي النقطة!

تعقيد الوقت

الوقت الذي يستغرقه اختتام النشاط.

يمكننا البدء في تحليل الوقت باستخدام طريقة حساب عدد مرات الظهور ، والتي تحسب بشكل أساسي عدد مرات تنفيذ تعليمات الجهاز. يتم تعيين وحدة زمنية لكل خطوة (تعليمات) ، بدءًا من 1.

يتم التعبير عن الوقت الذي تستهلكه الخوارزمية من خلال الوظيفة f (n) ، حيث تمثل n حجم البيانات.

يتم التعبير عن نتيجة التحليل على النحو التالي:

([دالة تعبر عن الوقت]) = [مجموع وحدات الوقت]

الآن دعونا نحلل بعض الخوارزميات لفهم كيفية عمل ذلك في الواقع.

تجمع الوظيفة الأولى رقمين صحيحين:

يمكننا أن نرى أنه بالنسبة للمهمة المذكورة ، تقوم الخوارزمية المنفذة بتنفيذ خطوة واحدة فقط: جمع رقمين. نظرًا لأننا نعزو قيمة لكل خطوة ، تكون النتيجة f (n) = 1.

دعونا نلقي نظرة على المثال التالي ، وهو خوارزمية تقسم عددًا صحيحًا على عدد صحيح آخر:

على الرغم من كونها عملية رياضية مشابهة للجمع ، فإن الخوارزمية تحتوي على المزيد من الخطوات لأنها تحتاج إلى التحقق مما إذا كان المقسوم يساوي 0 ؛ إذا كان هذا هو الحال ، فلن يتحقق الانقسام. نظرًا لأن لدينا أربع خطوات في المجموع ، وتم تعيين قيمة 1 لكل منها ، تكون النتيجة f (n) = 4.

تلخص الخوارزمية التالية جميع عناصر قائمة الأعداد الصحيحة:

في هذه الخوارزمية ، تتضمن إحدى الخطوات تعليمات بشأن التكرار ؛ هذا يعني أنه سيتم تنفيذ التعليمات البرمجية الموجودة بداخل عدة مرات. نظرًا لأن عدد عمليات التنفيذ يعتمد على حجم البيانات ، فإننا نعزو قيمة n كوحدة زمنية. تكون النتيجة f (n) = 2n + 3.

تضيف الخوارزمية التالية مجموع قائمة واحدة مع مجموع قائمة ثانية.

نتيجة لذلك لدينا f (n) = 2n² + 2n + 3.

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

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

على سبيل المثال ، ما هو المصطلح السائد لمجموع الخوارزمية الثالثة؟

و (ن) = 2 ن + 3

في هذه الحالة ، المصطلح السائد في 2 * n ، وسأشرح السبب!

في أي حالة يكون فيها n أكبر من 1 (n> 1) ، فإن المنتج (نتيجة الضرب) سيكون بالفعل أكثر من الحد الثاني للمجموع.

اختبر شيئًا: استبدل n بأي عدد صحيح أكبر من 1 ، وقم بإجراء الضرب.

ماذا عن المصطلح السائد لمجموع الخوارزمية الأخيرة؟

و (ن) = 2 ن² + 2 ن + 3

في هذه الحالة ، المصطلح السائد هو 2 * n² ، لأنه عندما n> 1 ، سيكون المنتج دائمًا أكبر من الفصلين الثاني والثالث من المجموع. المضي قدما ، واختباره!

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

هنا يأتي دور ترتيب التعقيد ، المعروف أيضًا باسم Notation-O أو Big-O.

تدوين Big-O

تُستخدم لتصنيف خوارزمية مع مراعاة معدل نمو العمليات مع تزايد عدد العناصر المعالجة.

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

الفئات الأكثر شيوعًا هي:

  • O (1) - ثابت ، لا يزيد عدد العمليات مع زيادة عدد العناصر
  • O (log n) - لوغاريتمي ، عدد العمليات أقل من عدد العناصر
  • O (n) - الخطي ، يزداد عدد العمليات بشكل متناسب مع عدد العناصر
  • O (n²) Quadratic ، سيكون عدد العمليات أكبر من عدد العناصر
  • O (2 ^ n) - الأسي ، يزداد عدد العمليات بسرعة مقارنة بعدد العناصر
  • O (n!) - عامل ، يزداد عدد العمليات بسرعة كبيرة جدًا ، حتى بالنسبة لعدد قليل من العناصر

أدناه ، لدينا رسم بياني يوضح معدل نمو العمليات × كمية العناصر:

تم تصنيف الرسم على النحو التالي:

  • المنطقة الحمراء رهيبة ، تجنبها!
  • المنطقة البرتقالية سيئة ، وتجنبها أيضًا!
  • المنطقة الصفراء عادلة ومعقولة!
  • المنطقة الخضراء الفاتحة جيدة ، باردة!
  • المنطقة الخضراء الداكنة ممتازة ، تهانينا!

الآن ، سنستخدم تدوين Big-O لتصنيف الخوارزميات التي تم ذكرها سابقًا ، ونستخدم دائمًا مصطلحها السائد لإرشادنا.

أدت الخوارزمية الأولى إلى f (n) = 1 ؛ بمعنى أنه ، بغض النظر عن زيادة العناصر ، تقوم الخوارزمية بتنفيذ عملية واحدة فقط. وبالتالي ، يمكننا تصنيف الخوارزمية على أنها Constant - O (1).

أدت الخوارزمية الثانية إلى f (n) = 4 ؛ بمعنى أنه بغض النظر عن زيادة العناصر ، ستقوم الخوارزمية بتنفيذ أربع عمليات. وبالتالي ، يمكننا أيضًا تصنيف هذه الخوارزمية على أنها Constant - O (1).

كانت نتيجة الخوارزمية الثالثة f (n) = 2n + 3 ؛ وهذا يعني أن عدد العمليات سوف ينمو بشكل متناسب مع عدد العناصر ، حيث ينظر إلى كيفية عمل n كمتغير في هذه الوظيفة. وبالتالي ، يمكننا تحديد هذه الخوارزمية على أنها خطية - O (ن).

أسفرت نتيجة الخوارزمية الأخيرة عن f (n) = 2n² + 2n + 3 ، مما يعني أن عدد العمليات سيزيد أكثر من عدد العناصر. في هذه الحالة ، يعمل n أيضًا كمتغير ، ولكن يتم رفعه إلى القوة الثانية (مربع). وبالتالي ، يمكننا تحديد هذه الخوارزمية على أنها Quadratic - O (n²).

يوضح الجدول أدناه نمو عدد العمليات من حيث علاقتها بنمو عدد العناصر.

لاحظ أنه في خوارزمية أسية ، ستؤدي 16 عنصرًا إلى 655536 عملية على الأقل. مزعجة جدا ، أليس كذلك؟

بشكل عام ، عملية التحليل هي نفسها التي كنا نقوم بها: حساب عدد الخطوات وتحديد المصطلح السائد.

يمكننا ملاحظة بعض الاتجاهات:

  • تميل الخوارزميات التي ليس لها حلقة تكرار إلى أن تكون ثابتة - O (1)
  • تميل الخوارزميات التي تحتوي على حلقات تكرار ، طالما لم تكن متداخلة ، إلى أن تكون خطية - O (n)
  • تميل الخوارزميات التي تحتوي على حلقتين متكررتين من التكرار إلى التربيعي - O (n²)
  • عادة ما يكون الوصول المباشر إلى فهرس صفيف O (1) (ثابت)
  • طرق تمديد القائمة ، في المتوسط ​​، هي O (n). على سبيل المثال: أي ، مجموع ، وفلتر.
  • عادةً ما تكون خوارزميات الفرز مثل فرز الفقاعة وفرز الإدخال وفرز التحديد O (n²).

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

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

لقد تركت بعض المراجع أدناه كمواد قراءة إضافية!

المراجع:

Vídeos 1 إلى 1.7

هل تريد جلب الابتكار إلى سوق القروض من خلال التكنولوجيا؟ نحن نبحث دائمًا عن أشخاص جدد للانضمام إلى طاقمنا!

تحقق من فتحاتنا هنا.