خوارزمية Interpolation Search

خوارزمية البحث 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
زمن التنفيذ
فى اسوء الحالات سنحتاج الى عدد مرات = عدد العناصر الكلى(n) / عدد العناصر التى نتخطاها فى المرة الواحدة (m)
بالاضافة الى تنفيذ m – 1 مقارنة اضافية فى البحث الخطى لايجاد العنصر
بالتالى عدد المرات الكلية فى اسوء الحالات هى n/m + m-1 وهذه القيمة تكون اصغير مايكن عندما تقريبًا
m = √n
الكود باستخدام python

اشترك فى القائمة البريدية

عن الكاتب

شارك على وسائل التواصل

اترك تعليقاً

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

سبعة عشر − 10 =