خوارزمية الاختيار
المحتويات
في البداية، خَوَارِزمِيَّةُ الاِختِيَارِ هي خوارزمية لإيجاد مكان عدد بالترتيب حسب التصنيف، وتعد هذه الخوارزمية من أشهر الخوارزميات لأنه يمكن تطبيقها بزمن خطي ولاستخداماتها المتعددة في علوم الحاسوب والطريقة التي تتم بها عن طريق الاستدعاء الذاتي أو recursion
{
- min=A[j]؛
- }
- }
- return min;
مقدمة
وعلى صعيد آخر، خوارزمية الاختيار هي طريقة بحث فعّـالة حيث تُعطَى الخوارزمية عدد i, والهدف هو إيجاد العدد ال-i في القائمة بعد التصنيف -SORTING- هناك عدة طرق لإيجاد هذا الهدف وقد تم التوصل إلى خوارزمية فعالة بزمن خطي - linear time algorithm-
اسم هذه الخوارزمية سيكون: اختيار
إضافةً إلى ذلك، - استدعي اختيار بشكل ذاتي لايجاد العدد ال-i في القائمة السفلى إذا: i≤k أو العدد ال- i-k الأصغر إذا i>k
من جهة ثانية، - قسم ال-n أعداد في القائمة ل- حيث كل قائمة تحوي 5 أعداد وقائمة أخيرة تحوي البواقي وهي بكبر:n mod 5
وفي هذا الصدد، - قسم القائمة حول x بواسطة partition ولنقل أن الأعداد في القائمة السفلى عددها k والقائمة العليا هي n-k
ومن جهة أخرى، - جِد القيمة الوسطى للقوائم (تستطيع ان تصنف ثم تجد لكل قائمة القيمة الوسطى)
إذا n>1 حينها:
إذا n=1 نرجع القيمة الوحيدة الموجودة وهو بمثابة العدد ال -i
وفي هذا السياق، - استدعي اختيار لإيجاد القيمة الوسطى،x, ل الاعداد التي وجدتها في 2
تحليل زمن الخوارزمية
معادلة الاستدعاء الذاتي:
وحلها كالتالي:
حالات خاصة
int FindMin(int[] A)
إضافةً إلى ذلك، عندما يكون i=1 عندها على الخوارزمية إيجاد العدد الأول من حيث الترتيب أي اصغر قيمة في القائمة وهذه المهمة بسيطة جدا وإيجاد هذه القيمة يتم عن طريق بحث خطي مع متغيِّر إضافيّ وها هي طريقة لفعل هذا:
{
if(A[j]<A[0])
}
وفي هذا السياق، هذه الطريقة صحيحة ولكن الوقت الذي تحتاجه هو: ((O(nlog(n ونريد أن نصل لخوارزمية فعالة بوقت خطي بالنسبة للمدخل!
اختيار بالتصنيف
- int select(int[] A,int i)
- {
- return (A.sort)[i]
إضافةً إلى ذلك، نبدأ أولا بالطريقة السهلة وهي تتم عن طريق تحويل الاختيار إلى تصنيف ثم التوجه للعدد المطلوب أي:
}
في هذا الإطار، وحالة أخرى هي i=n وعندها يجب إيجاد القيمة الكبرى وبطريقة مشابهة لإيجاد القيمة الصغرى.
{
for(int j=1;j<=A.length;j++)
int min=A[0]؛
الخوارزمية الخطية
من جهة ثانية، هذه الخوارزمية تستعمل طريقة الاستدعاء الذاتي (العودية) وهي كالتالي:
📝 هل في هذه المقالة خطأ؟
إذا وجدت معلومة تحتاج تصحيحاً أو إضافة، أو أردت حذف المقالة، أرسل لنا طلباً وسنراجعه.
ما رأيك في هذه المقالة؟