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

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

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

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

تعقيد الوقت

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

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

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

1. البحث الخطي.

2. بحث ثنائي.

لنفترض أن المصفوفة تحتوي على عشرة عناصر ، وعلينا إيجاد العدد عشرة في المصفوفة.

const array = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]; const search_digit = 10;

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

الآن دعونا نحسب عدد العمليات التي يقوم بها. الجواب هنا هو 10 (لأنه يقارن كل عنصر من عناصر المصفوفة). لذلك ، يستخدم البحث الخطي عشر عمليات للعثور على عنصر معين (هذه هي أقصى عدد من العمليات لهذه المصفوفة ؛ في حالة البحث الخطي ، يُعرف هذا أيضًا بأسوأ حالة للخوارزمية).

بشكل عام ، سيأخذ البحث الخطي عدد n من العمليات في أسوأ حالاتها (حيث n هو حجم المصفوفة).

دعونا نفحص خوارزمية البحث الثنائي لهذه الحالة.

يمكن فهم البحث الثنائي بسهولة من خلال هذا المثال:

المصدر: Learneroo

إذا حاولنا تطبيق هذا المنطق على مشكلتنا ، فسنقوم أولاً بمقارنة search_digit بالعنصر الأوسط من المصفوفة ، أي 5. الآن نظرًا لأن الرقم 5 أقل من 10 ، فسنبدأ في البحث عن search_digit في عناصر المصفوفة أكبر من 5 ، بنفس الطريقة حتى نحصل على العنصر المطلوب 10.

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

عدد العمليات = سجل (10) = 4 (تقريبًا)

للقاعدة 2

يمكننا تعميم هذه النتيجة للبحث الثنائي على النحو التالي:

بالنسبة لصفيف من الحجم n ، فإن عدد العمليات التي يقوم بها البحث الثنائي هو: log (n)

تدوين Big O

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

المصدر: Techtud

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

عندما نحلل خوارزمية ، نستخدم تدوينًا لتمثيل تعقيدها الزمني وهذا الترميز هو تدوين Big O.

على سبيل المثال: يمكن تمثيل التعقيد الزمني للبحث الخطي على أنه O (n) و O (log n) للبحث الثنائي (حيث يمثل n و log (n) عدد العمليات).

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

  1. بحث ثنائي: O (تسجيل ن)
  2. البحث الخطي: O (n)
  3. فرز سريع: O (n * log n)
  4. فرز التحديد: O (n * n)
  5. مندوب مبيعات السفر: O (n!)

استنتاج

إنني أقدر حقًا جهودك إذا كنت لا تزال تقرأ هذا المقال. الآن ، يجب أن تفكر - لماذا يعد تعقيد الوقت مهمًا جدًا لفهمه؟

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

على سبيل المثال ، إذا كان لدينا 4 مليارات عنصر للبحث عنها ، ففي أسوأ الحالات ، سيستغرق البحث الخطي 4 مليارات عملية لإكمال مهمته. سيكمل البحث الثنائي هذه المهمة في 32 عملية فقط. هذا فرق كبير. لنفترض الآن أنه إذا استغرقت عملية واحدة 1 مللي ثانية حتى تكتمل ، فسيستغرق البحث الثنائي 32 مللي ثانية فقط بينما يستغرق البحث الخطي 4 مليار مللي ثانية (أي 46 يومًا تقريبًا). هذا فرق كبير.

هذا هو سبب أهمية دراسة تعقيد الوقت عندما يتعلق الأمر بكمية كبيرة من البيانات.

مصادر

خوارزميات Grokking- بواسطة Aditya Y Bhargava

مقدمة إلى تدوين Big O وتعقيد الوقت - بواسطة CS Dojo