خوارزمية البحث Jump Search Algorithm

خوارزمية البحث Jump Search Algorithm
خوارزمية البحث Jump Search Algorithm


المطلوب 

البحث والحصول على عنصر فى مصفوف مرتبة فلنفرض مثلًا اننا نملك مصفوفة تحتوي العناصر
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610]
وعدد عناصر هذه المصفوفة هو 16 عنصر
لنفرض اننا نريد ايجاد العدد 55
 بتخطى بعض العناصر ولنفرض انه يتخطى 4 عناصر فى كل مرة Jump Algorithm سيقوم
كالتالى
الخطوة الاولى : سيقفز من العنصر 0 الى العنصر 4
الخطوة الثانية : سيقفز من العنصر 4 الى العنصر 8
الخطوة الثالثة : سيقفز من العنصر 8 الى العنصر 12
الخطوة الثالثة : سيقفز من العنصر 12 الى العنصر 16
وعندما يجد ان العنصر فى الموقع 16 اكبر من 55 بالتالى يقوم بالرجوع  الى العنصر رقم 9
الخطوة الرابعة : يقوم بعمل بحث خطى فى العناصر من 9 حتى يجد العنصر 55
jump search fig 1
زمن التنفيذ
فى اسوء الحالات سنحتاج الى عدد مرات = عدد العناصر الكلى(n) / عدد العناصر التى نتخطاها فى المرة الواحدة (m)
بالاضافة الى تنفيذ m – 1 مقارنة اضافية فى البحث الخطى لايجاد العنصر
بالتالى عدد المرات الكلية فى اسوء الحالات هى n/m + m-1 وهذه القيمة تكون اصغير مايكن عندما تقريبًا
m = √n
الكود باستخدام python

مقالات ذات صلة

تحليل وتصميم الخوارزميات PDF تحميل مجانى

نوع الملف : PDF . وصف الملف : يشرح هذا الكتاب الخوارزميات البرمجية التى تستخدم فى فهم وتصميم وتحليل البرامج ,...

Edit Distance Algorithm

Edit Distance -:Definition         The minimum of operations required to convert one string into other such...

خوارزميات المقارنة Pattern Matching Algorithm

موضوع مطابقة النصوص أو البحث في النصوص من المواضيع المهمه في مجال الخوارزميات ، حيث الهدف هو البحث عن...

خوارزمية Interpolation Search

المعطى مصفوف مرتبة من العناصر والمطلوب ايجاد عنصرمعين وليكون x فى المصفوفة  arr   باستخدام Interpolation Search خوارزمية وهى نسخة...

كتب بواسطة عمرو العربى

مؤسس مطور

التعليقات

اترك تعليقك

لن يتم نشر عنوان بريدك الإلكتروني. الحقول الإلزامية مشار إليها بـ *

*