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

فهم ”الغوريتامز للبحث“

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

حساب تعقيد الوقت

وتشمل هذه العملية إقامة علاقة متكررة تصف مجموع الوقت استنادا إلى حجم مجموعة البيانات، ففي البحث الثنائي مثلا، تخفض كل مكالمة استجمامية مجموعة البيانات إلى النصف، مما يؤدي إلى تكرار العلاقة بين T(n) = T(n/2) + c، حيث يكون (ج) هو الوقت الدائم للمقارنة.

إن حل العلاقة المتكررة باستخدام أساليب مثل نظرية الماجستير أو تحليل شجرات التكرار يوفر التعقيد العام للوقت، وبالنسبة للبحث الثنائي، يؤدي ذلك إلى تعقيد الوقت الناجع للوقود.

تحليل البيانات

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

  • حجم البيانات: عدد العناصر
  • التجزئة المتكررة: خفض عدد البيانات إلى النصف كل خطوة
  • العلاقة المتكررة: T(n) = T(n/2) + c
  • الحل: تعقيد الوقت
  • مثال: يتطلب 000 1 عنصر حوالي 10 مقارنات