خوارزمية الاختيار

الموسوعة الحرة

في علم الحاسوب ، خوارزمية الاختيار هي خوارزمية لإيجادك{\displaystyle k}أصغر قيمة في مجموعة من القيم القابلة للترتيب، مثل الأرقام. تُسمى القيمة التي يجدهاك{\displaystyle k}إحصائية الترتيب th . يشمل الاختيار ، كحالات خاصة، مشاكل إيجاد العنصر الأدنى والوسيط والأعلى في المجموعة . تتضمن خوارزميات الاختيار خوارزمية الاختيار السريع وخوارزمية وسيط الوسائط . عند تطبيقها على مجموعة منن{\displaystyle n}بالنسبة للقيم، تستغرق هذه الخوارزميات وقتًا خطيًا .يا(ن){\displaystyle O(n)}كما هو موضح باستخدام ترميز Big O. بالنسبة للبيانات المهيكلة مسبقًا، قد تكون الخوارزميات الأسرع ممكنة؛ كحالة قصوى، يستغرق الاختيار في مصفوفة مرتبة مسبقًا وقتًايا(1){\displaystyle O(1)}.

بيان المشكلة

تأخذ خوارزمية مشكلة الاختيار كمدخلات مجموعة من القيم، وعددًاك{\displaystyle k}. يُخرجك{\displaystyle k}أصغر هذه القيم، أو في بعض صيغ المسألة، مجموعة منك{\displaystyle k}أصغر القيم. لكي يكون هذا التعريف دقيقًا، ينبغي أن يكون من الممكن ترتيب القيم من الأصغر إلى الأكبر؛ على سبيل المثال، قد تكون أعدادًا صحيحة ، أو أعدادًا عشرية ، أو أي نوع آخر من الكائنات ذات مفتاح رقمي. مع ذلك، لا يُفترض أنها مُرتبة مسبقًا. غالبًا ما تقتصر خوارزميات الاختيار على نموذج حسابي قائم على المقارنة ، كما هو الحال في خوارزميات فرز المقارنة ، حيث تمتلك الخوارزمية عملية مقارنة تُحدد الترتيب النسبي لأي قيمتين، ولكن لا يُمكنها إجراء أي عمليات حسابية أخرى على هذه القيم. [ 1 ]

لتبسيط المسألة، تفترض بعض الدراسات أن القيم جميعها متميزة عن بعضها البعض، [ 2 ] أو أنه تم استخدام طريقة متسقة لكسر التعادل لترتيب أزواج العناصر المتساوية في القيمة. ويتعلق اختلاف آخر في تعريف المسألة بترقيم القيم المرتبة: حيث تمثل أصغر قيمة يتم الحصول عليها بوضعك=0{\displaystyle k=0}كما هو الحال في ترقيم المصفوفات بدءًا من الصفر ، أم يتم الحصول عليه عن طريق تحديدك=1{\displaystyle k=1}هل يتم استخدام المصطلحات الإنجليزية المعتادة للدلالة على أصغر قيمة، وثاني أصغر قيمة، وما إلى ذلك؟ تتبع هذه المقالة المصطلحات التي استخدمها كورمن وآخرون، والتي بموجبها تكون جميع القيم متميزة ويتم الحصول على القيمة الدنيا منك=1{\displaystyle k=1}[ 2 ]​

وفقًا لهذه الاتفاقيات، فإن القيمة القصوى، ضمن مجموعة منن{\displaystyle n}يتم الحصول على القيم عن طريق تحديدك=ن{\displaystyle k=n}. متىن{\displaystyle n}إذا كان عددًا فرديًا ، يتم الحصول على الوسيط للمجموعة عن طريق وضعك=(ن+1)/2{\displaystyle k=(n+1)/2}. متىن{\displaystyle n}إذا كان العدد زوجيًا، فهناك خياران للوسيط، يتم الحصول عليهما بتقريب هذا الخيار منك{\displaystyle k}لأسفل أو لأعلى، على التوالي: الوسيط الأدنى معك=ن/2{\displaystyle k=n/2}والمتوسط ​​الأعلى معك=ن/2+1{\displaystyle k=n/2+1}[ 2 ]​

الخوارزميات

الفرز والاختيار من بين المجموعات

كخوارزمية أساسية، يتم اختيارك{\displaystyle k}يمكن إيجاد أصغر قيمة في مجموعة من القيم من خلال الخطوتين التاليتين:

  • فرز المجموعة
  • إذا كانت مخرجات خوارزمية الفرز عبارة عن مصفوفة ، فاسترجعهاك{\displaystyle k}العنصر رقم 1 ؛ وإلا، فابحث في التسلسل المصنف للعثور على العنصر رقم 1.ك{\displaystyle k}العنصر رقم 1 .

تستغرق هذه الطريقة وقتاً طويلاً، ويعتمد ذلك بشكل أساسي على خطوة الفرز، والتي تتطلبΘ(نسجل⁡ن){\displaystyle \Theta (n\log n)}الوقت باستخدام فرز المقارنة . [ 2 ] [ 3 ] حتى عند استخدام خوارزميات فرز الأعداد الصحيحة ، فإنها عادةً ما تكون أبطأ من الوقت الخطي الذي يمكن تحقيقه باستخدام خوارزميات اختيار متخصصة. ومع ذلك، فإن بساطة هذا النهج تجعله جذابًا، خاصةً عند توفير روتين فرز عالي الكفاءة كجزء من مكتبة وقت التشغيل، ولكن لا تتوفر خوارزمية اختيار. بالنسبة للمدخلات ذات الحجم المتوسط، يمكن أن يكون الفرز أسرع من خوارزميات الاختيار غير العشوائية، نظرًا لصغر العوامل الثابتة في وقت تشغيله. [ 4 ] تُنتج هذه الطريقة أيضًا نسخة مُرتبة من المجموعة، والتي قد تكون مفيدة لحسابات لاحقة أخرى، وخاصةً للاختيار مع خيارات أخرى .ك{\displaystyle k}[ 3 ]​

بالنسبة لخوارزمية الفرز التي تُنشئ عنصرًا واحدًا في كل مرة، مثل فرز التحديد ، يمكن إجراء المسح بالتزامن مع الفرز، ويمكن إنهاء الفرز بمجرد الانتهاء منك{\displaystyle k}تم العثور على العنصر رقم 1. يمكن اعتبار أحد التصاميم الممكنة لجدول مباريات الترضية في بطولة خروج المغلوب ، حيث تلعب الفرق التي خسرت أمام الفائز النهائي بطولة مصغرة أخرى لتحديد المركز الثاني، مثالاً على هذه الطريقة. [ 5 ] يؤدي تطبيق هذا التحسين على فرز الكومة إلى إنتاج خوارزمية اختيار الكومة، والتي يمكنها اختيارك{\displaystyle k}أصغر قيمة في الزمنيا(ن+كسجل⁡ن){\displaystyle O(n+k\log n)}[ 6 ] هذا سريع عندماك{\displaystyle k}صغير نسبياً إلىن{\displaystyle n}لكنها تتدهور إلىيا(نسجل⁡ن){\displaystyle O(n\log n)}بالنسبة للقيم الأكبر منك{\displaystyle k}مثل الاختيارك=ن/2{\displaystyle k=n/2}تُستخدم لإيجاد الوسيط.

التحول

تعتمد العديد من طرق الاختيار على اختيار عنصر "محوري" خاص من المدخلات، واستخدام المقارنات مع هذا العنصر لتقسيم المتبقين-1{\displaystyle n-1}قيم الإدخال إلى مجموعتين فرعيتين: المجموعةل{\displaystyle L}من العناصر الأقل من العنصر المحوري، والمجموعةR{\displaystyle R}للعناصر الأكبر من العنصر المحوري. يمكن للخوارزمية بعد ذلك تحديد مكانك{\displaystyle k}يتم إيجاد أصغر قيمة بناءً على مقارنةك{\displaystyle k}مع أحجام هذه المجموعات. على وجه الخصوص، إذاك≤|ل|{\displaystyle k\leq |L|}، الك{\displaystyle k}أصغر قيمة موجودة فيل{\displaystyle L}ويمكن إيجادها بشكل متكرر من خلال تطبيق خوارزمية الاختيار نفسها علىل{\displaystyle L}. لوك=|ل|+1{\displaystyle k=|L|+1}ثم الـك{\displaystyle k}أصغر قيمة هي القيمة المحورية، ويمكن إرجاعها فورًا. في الحالة المتبقية،ك{\displaystyle k}أصغر قيمة موجودة فيR{\displaystyle R}وبشكل أكثر تحديدًا ، هو العنصر الموجود في الموضعك-|ل|-1{\displaystyle k-|L|-1}لR{\displaystyle R}يمكن إيجادها بتطبيق خوارزمية اختيار بشكل متكرر، والبحث عن القيمة في هذا الموضع فيR{\displaystyle R}[ 7 ]​

كما هو الحال مع خوارزمية الفرز السريع القائمة على التمحور ، فإن تقسيم المدخلات إلىل{\displaystyle L}وR{\displaystyle R}يمكن القيام بذلك عن طريق إنشاء مجموعات جديدة لهذه المجموعات، أو باستخدام طريقة تقسم قائمة أو مصفوفة بيانات معينة في مكانها. تختلف التفاصيل حسب كيفية تمثيل مجموعة الإدخال. [ 8 ] الوقت اللازم لمقارنة العنصر المحوري بجميع القيم الأخرى هويا(ن){\displaystyle O(n)}[ 7 ] مع ذلك ، تختلف طرق التمحور في كيفية اختيارها للمحور، مما يؤثر على حجم المشكلات الفرعية في كل استدعاء تكراري. وتعتمد كفاءة هذه الطرق بشكل كبير على اختيار المحور. فإذا تم اختيار المحور بشكل سيئ، فقد يكون وقت تشغيل هذه الطريقة بطيئًا للغاية .يا(ن2){\displaystyle O(n^{2})}[ 4 ]​

  • إذا كانت نقطة الارتكاز عند الوسيط تمامًا للمدخلات، فإن كل استدعاء تكراري سيحتوي على نصف عدد القيم على الأكثر من الاستدعاء السابق، وستتجمع الأزمنة الإجمالية في متسلسلة هندسية إلىيا(ن){\displaystyle O(n)}ومع ذلك ، فإن إيجاد الوسيط بحد ذاته يمثل مشكلة اختيار، وذلك على كامل المدخلات الأصلية. ومحاولة إيجاده من خلال استدعاء متكرر لخوارزمية اختيار ستؤدي إلى تكرار لا نهائي، لأن حجم المشكلة لن يتناقص في كل استدعاء. [ 7 ]
  • تختار خوارزمية Quickselect العنصر المحوري عشوائيًا وبشكل متساوٍ من بين القيم المدخلة. ويمكن وصفها بأنها خوارزمية تقليم وبحث ، [ 9 ] وهي نوع من خوارزمية Quicksort ، مع نفس استراتيجية التمحور، ولكن في حين أن Quicksort تُجري استدعاءين متكررين لفرز المجموعتين الفرعيتين.ل{\displaystyle L}وR{\displaystyle R}لا يقوم خيار التحديد السريع إلا بإجراء أحد هذين الاستدعاءين. والوقت المتوقع لذلك هويا(ن){\displaystyle O(n)}[ 2 ] [ 7 ] [ 9 ] لأي ثابتج{\displaystyle C}، احتمال أن يتجاوز عدد مقارناتهاجن{\displaystyle Cn}صغير بشكل فائق الأسي فيج{\displaystyle C}[ 10 ]​
  • تختار خوارزمية فلويد-ريفست ، وهي شكل من أشكال الاختيار السريع، نقطة ارتكاز عن طريق أخذ عينة عشوائية من مجموعة فرعية منر{\displaystyle r}قيم البيانات، لحجم عينة معينر{\displaystyle r}ثم يتم تحديد عنصرين بشكل متكرر أعلى وأسفل الموضع قليلاًرك/ن{\displaystyle rk/n}من العينة التي سيتم استخدامها كمحاور. مع هذا الاختيار، من المرجح أنك{\displaystyle k}يتم وضع البيانات بين محوري الربط، بحيث لا يتبقى بعد عملية الربط سوى عدد قليل من قيم البيانات بين المحورين لإجراء استدعاء متكرر. يمكن لهذه الطريقة تحقيق عدد متوقع من المقارنات وهون+مين(ك،ن-ك)+o(ن){\displaystyle n+\min(k,nk)+o(n)}[ 11 ] في عملهما الأصلي ، ادعى فلويد وريفست أنo(ن){\displaystyle o(n)}يمكن تقليص المدة إلى أدنى حد ممكنيا(ن){\displaystyle O({\sqrt {n}})}باستخدام مخطط أخذ عينات متكرر، ولكن تم التشكيك في صحة تحليلهم . [ 12 ] [ 13 ] في المقابل، أظهر تحليل أكثر دقة أن نسخة من خوارزميتهم تحققيا(نسجل⁡ن){\displaystyle O({\sqrt {n\log n}})}لهذا المصطلح. [ 14 ] على الرغم من أن التحليل المعتاد لكل من خوارزمية الاختيار السريع وخوارزمية فلويد-ريفست يفترض استخدام مولد أرقام عشوائية حقيقي ، فقد ثبت أن نسخة من خوارزمية فلويد-ريفست تستخدم مولد أرقام شبه عشوائية مُهيأ بعدد لوغاريتمي فقط من البتات العشوائية الحقيقية تعمل في وقت خطي باحتمالية عالية. [ 15 ]
تمثيل مرئي لاختيار نقطة الارتكاز لطريقة وسيط الوسائط . تُعرض كل مجموعة من خمسة عناصر كعمود من النقاط في الشكل، مرتبة تصاعديًا من الأعلى إلى الأسفل. إذا رُتبت وسائطها (النقاط الخضراء والبنفسجية في الصف الأوسط) تصاعديًا من اليسار إلى اليمين، واختير وسيط الوسائط كنقطة ارتكاز، فإن3ن/10{\displaystyle 3n/10}ستكون العناصر الموجودة في الربع العلوي الأيسر أقل من العنصر المحوري، و3ن/10{\displaystyle 3n/10}ستكون العناصر الموجودة في الربع السفلي الأيمن أكبر من العنصر المحوري، مما يدل على أنه سيتم التخلص من العديد من العناصر عن طريق التمحور.
  • تقوم طريقة الوسيط للوسائط بتقسيم المدخلات إلى مجموعات من خمسة عناصر، وتستخدم طريقة أخرى غير تكرارية لإيجاد الوسيط لكل مجموعة من هذه المجموعات في وقت ثابت لكل مجموعة. ثم تستدعي نفسها بشكل تكراري لإيجاد الوسيط لهذه المجموعات.ن/5{\displaystyle n/5}الوسائط. استخدام الوسيط الناتج للوسائط كمحور ينتج عنه تقسيم معالأعلى(|ل|،|R|)≤7ن/10{\displaystyle \max(|L|,|R|)\leq 7n/10}وبالتالي ، فإن المشكلة تكمن فين{\displaystyle n}يتم اختزال العناصر إلى مسألتين متكررتين علىن/5{\displaystyle n/5}العناصر (لإيجاد المحور) وعلى الأكثر7ن/10{\displaystyle 7n/10}العناصر (بعد استخدام العنصر المحوري). الحجم الإجمالي لهاتين المسألتين الفرعيتين المتكررتين هو على الأكثر9ن/10{\displaystyle 9n/10}مما يسمح بتحليل إجمالي الوقت كمتسلسلة هندسية تُضاف إلىيا(ن){\displaystyle O(n)}على عكس خوارزمية الاختيار السريع ، فإن هذه الخوارزمية حتمية وليست عشوائية. [ 2 ] [ 4 ] [ 5 ] كانت أول خوارزمية اختيار حتمية ذات زمن خطي معروفة، [ 5 ] ويتم تدريسها عادةً في مقررات الخوارزميات الجامعية كمثال على أسلوب فرق تسد الذي لا ينقسم إلى مسألتين فرعيتين متساويتين. [ 2 ] [ 4 ] [ 9 ] [ 16 ] ومع ذلك، فإن العوامل الثابتة العالية تؤثر على أدائها.يا(ن){\displaystyle O(n)}يؤدي القيد الزمني إلى جعله أبطأ من التحديد السريع عمليًا، [ 3 ] [ 9 ] وأبطأ حتى من الفرز بالنسبة للمدخلات ذات الحجم المتوسط. [ 4 ]
  • يمكن استخدام الخوارزميات الهجينة مثل introselect لتحقيق الأداء العملي لخوارزمية quickselect مع اللجوء إلى متوسطات المتوسطات لضمان أسوأ الحالاتيا(ن){\displaystyle O(n)}الوقت. [ 17 ]

المصانع

خوارزميات الاختيار الحتمية ذات أقل عدد معروف من المقارنات، لقيمك{\displaystyle k}التي تبعد مسافة طويلة عن1{\displaystyle 1}أون{\displaystyle n}تعتمد هذه الأساليب على مفهوم المصانع ، الذي قدمه أرنولد شونهاج ومايك باترسون ونيك بيبنجر عام 1976. [ 18 ] وهي طرق تُنشئ ترتيبات جزئية لأنواع محددة، على مجموعات فرعية صغيرة من قيم الإدخال، باستخدام المقارنات لدمج ترتيبات جزئية أصغر . كمثال بسيط، يمكن لأحد أنواع المصانع أن يأخذ كمدخل سلسلة من الترتيبات الجزئية أحادية العنصر، ويقارن أزواجًا من العناصر من هذه الترتيبات، وينتج كمخرج سلسلة من المجموعات المرتبة كليًا ثنائية العناصر. يمكن أن تكون العناصر المستخدمة كمدخلات لهذا المصنع إما قيم إدخال لم تتم مقارنتها بأي شيء بعد، أو قيم "مهدرة" ناتجة عن مصانع أخرى. يهدف الخوارزمية القائمة على المصانع إلى دمج مصانع مختلفة، حيث تذهب مخرجات بعض المصانع إلى مدخلات مصانع أخرى، من أجل الحصول في النهاية على ترتيب جزئي يكون فيه أحد العناصر (الـك{\displaystyle k}( الأصغر) أكبر من بعضك-1{\displaystyle k-1}عناصر أخرى وأصغر من عنصر آخرن-ك{\displaystyle nk}آخرون. يؤدي التصميم الدقيق لهذه المصانع إلى خوارزمية، عند تطبيقها على إيجاد الوسيط، تستخدم على الأكثر2.942ن{\displaystyle 2.942n}المقارنات. بالنسبة للقيم الأخرى لـك{\displaystyle k}[ 19 ]​​​

الخوارزميات المتوازية

تمت دراسة الخوارزميات المتوازية للاختيار منذ عام 1975، عندما قدم ليزلي فاليانت نموذج شجرة المقارنة المتوازية لتحليل هذه الخوارزميات، وأثبت أن الاختيار في هذا النموذج باستخدام عدد خطي من المقارنات يتطلبΩ(سجل⁡سجل⁡ن){\displaystyle \Omega (\log \log n)}خطوات متوازية، حتى لاختيار الحد الأدنى أو الحد الأقصى. [ 20 ] اكتشف الباحثون لاحقًا خوارزميات متوازية للاختيار فييا(سجل⁡سجل⁡ن){\displaystyle O(\log \log n)}[ 21 ] [ 22 ] في نموذج شجرة المقارنة المتوازية العشوائية ، من الممكن إجراء الاختيار في عدد محدود من الخطوات وعدد خطي من المقارنات. [ 23 ] في نموذج ذاكرة الوصول العشوائي المتوازية الأكثر واقعية للحوسبة ، مع الوصول الحصري للقراءة والكتابة إلى الذاكرة، يمكن إجراء الاختيار في وقتيا(سجل⁡ن){\displaystyle O(\log n)}معيا(ن/سجل⁡ن){\displaystyle O(n/\log n)}المعالجات، وهو الأمثل من حيث الوقت وعدد المعالجات. [ 24 ] مع الوصول المتزامن للذاكرة، يصبح وقت المعالجة المتوازية أسرع قليلاً بشكل عام، [ 25 ] وسجل⁡ن{\displaystyle \log n}يمكن استبدال المصطلح في الإطار الزمني بـسجل⁡ك{\displaystyle \log k}[ 26 ]​

هياكل البيانات شبه الخطية

عندما تكون البيانات مُنظمة مسبقًا في بنية بيانات ، قد يكون من الممكن إجراء عملية الاختيار في وقت أقل من خطي بالنسبة لعدد القيم. كمثال بسيط على ذلك، بالنسبة للبيانات المُصنفة مسبقًا في مصفوفة، فإن اختيارك{\displaystyle k}يمكن الوصول إلى العنصر رقم n من خلال عملية بحث واحدة في المصفوفة، في وقت ثابت. [ 27 ] بالنسبة للقيم المنظمة في مصفوفة ثنائية الأبعاد بحجمم×ن{\displaystyle m\times n}مع وجود صفوف وأعمدة مرتبة، يمكن إجراء التحديد في الوقت المناسبيا(مسجل⁡(2ن/م)){\displaystyle O{\bigl (}m\log(2n/m){\bigr )}}أو أسرع عندماك{\displaystyle k}صغير نسبيًا مقارنةً بأبعاد المصفوفة. [ 27 ] [ 28 ] بالنسبة لمجموعة منم{\displaystyle m}المصفوفات المرتبة أحادية البعد، معكأنا{\displaystyle k_{i}}عدد العناصر الأقل من العنصر المحدد فيأنا{\displaystyle i}المصفوفة رقم 1 ، الوقت هويا(م+∑أنا=1مسجل⁡(كأنا+1)){\textstyle O{\bigl (}m+\sum _{i=1}^{m}\log(k_{i}+1){\bigr )}}[ 28 ]​

يستغرق اختيار البيانات من كومة ثنائية وقتًايا(ك){\displaystyle O(k)}وهذا مستقل عن الحجمن{\displaystyle n}من الكومة، وأسرع منيا(كسجل⁡ن){\displaystyle O(k\log n)}الحد الزمني الذي يمكن الحصول عليه من بحث الأفضل أولاً . [ 28 ] [ 29 ] يمكن تطبيق هذه الطريقة نفسها بشكل أعم على البيانات المنظمة على شكل أي نوع من الأشجار المرتبة ترتيبًا هرميًا (شجرة تخزن فيها كل عقدة قيمة واحدة، حيث تكون قيمة العقدة الأب لكل عقدة غير جذرية أصغر من قيمة عقدتها الابنة). طُبقت هذه الطريقة لإجراء الاختيار في كومة على مشاكل سرد حلول متعددة لمسائل التحسين التوافقي ، مثل إيجاد أقصر k مسار في رسم بياني مُثقَّل، وذلك بتعريف فضاء حالة للحلول على شكل شجرة مرتبة ترتيبًا هرميًا مُعرَّفة ضمنيًا ، ثم تطبيق خوارزمية الاختيار هذه على هذه الشجرة. [ 30 ] في الاتجاه الآخر، استُخدمت خوارزميات الاختيار ذات الوقت الخطي كإجراء فرعي في بنية بيانات قائمة الانتظار ذات الأولوية المرتبطة بالكومة، مما حسَّن وقت استخراجها.ك{\displaystyle k}العنصر رقم 1 منيا(سجل⁡ن){\displaystyle O(\log n)}ليا(سجل*⁡ن+سجل⁡ك){\displaystyle O(\log ^{*}n+\log k)}؛ هناسجل*⁡ن{\displaystyle \log ^{*}n}هو اللوغاريتم المتكرر . [ 31 ]

بالنسبة لمجموعة من قيم البيانات التي تخضع لعمليات إدخال وحذف ديناميكية، تعمل شجرة الإحصاء الترتيبي على تعزيز بنية شجرة البحث الثنائية ذاتية التوازن بكمية ثابتة من المعلومات الإضافية لكل عقدة في الشجرة، مما يسمح بعمليات الإدخال والحذف والاستعلامات التي تطلبك{\displaystyle k}العنصر رقم في المجموعة الحالية سيتم تنفيذه بالكامل فييا(سجل⁡ن){\displaystyle O(\log n)}[ 2 ] يتجاوز نموذج المقارنة الحسابي، إذ يُمكن تحقيق أوقات أسرع لكل عملية للقيم التي تُمثل أعدادًا صحيحة صغيرة، والتي يُسمح بإجراء العمليات الحسابية الثنائية عليها . [ 32 ] لا يُمكن لخوارزمية التدفق أن تُحقق أوقاتًا أسرع لكل عملية مع ذاكرة ذات زمن أقل من خطي في كليهما.ن{\displaystyle n}وك{\displaystyle k}لحل استعلامات الاختيار بدقة للبيانات الديناميكية، يمكن استخدام رسم العد الأدنى لحل استعلامات الاختيار تقريبًا، وذلك بإيجاد قيمة يكون موضعها في ترتيب العناصر (إذا تمت إضافتها إليها) ضمنεن{\displaystyle \varepsilon n}خطواتك{\displaystyle k}، بالنسبة لرسم تخطيطي يقع حجمه ضمن عوامل لوغاريتمية من1/ε{\displaystyle 1/\varepsilon }[ 33 ]​

الحدود الدنيا

اليا(ن){\displaystyle O(n)}يُعدّ وقت تشغيل خوارزميات الاختيار المذكورة أعلاه ضروريًا، لأنّ خوارزمية الاختيار التي يمكنها معالجة المدخلات بترتيب عشوائي يجب أن تستغرق هذا الوقت لفحص جميع مدخلاتها. إذا لم تتم مقارنة أيٍّ من قيم المدخلات، فقد تكون تلك القيمة هي القيمة التي كان ينبغي اختيارها، وبالتالي قد تُنتج الخوارزمية إجابة خاطئة. [ 28 ] إضافةً إلى هذه الحجة البسيطة، أُجريت أبحاثٌ كثيرة حول العدد الدقيق للمقارنات اللازمة للاختيار، سواءً في الحالات العشوائية أو الحتمية.

اختيار الحد الأدنى منن{\displaystyle n}القيم تتطلبن-1{\displaystyle n-1}المقارنات، لأنن-1{\displaystyle n-1}يجب أن تكون القيم التي لم يتم اختيارها قد حُددت جميعها على أنها غير دنيا، وذلك لكونها الأكبر في مقارنة ما، ولا يمكن أن تكون قيمتان منها الأكبر في المقارنة نفسها. وينطبق المنطق نفسه على اختيار القيمة القصوى. [ 14 ]

الحالة الأبسط التالية هي اختيار ثاني أصغر قيمة. بعد عدة محاولات غير صحيحة، نُشر أول حد أدنى دقيق لهذه الحالة عام 1964 على يد عالم الرياضيات السوفيتي سيرجي كيسليتسين . ويمكن إثبات ذلك من خلال ملاحظة أن اختيار ثاني أصغر قيمة يتطلب أيضًا تمييز أصغر قيمة عن باقي القيم، ومن خلال النظر في العددص{\displaystyle p}من المقارنات التي تتضمن أصغر قيمة يمكن أن تُجريها خوارزمية لحل هذه المشكلة. كل منهاص{\displaystyle p}العناصر التي تمت مقارنتها بأصغر قيمة هي مرشحة لتكون ثاني أصغر قيمة، وص-1{\displaystyle p-1}يجب إيجاد قيمة من هذه القيم أكبر من قيمة أخرى في مقارنة ثانية لاستبعادها باعتبارها ثاني أصغر قيمة.ن-1{\displaystyle n-1}أن تكون القيم أكبر في مقارنة واحدة على الأقل، وص-1{\displaystyle p-1}إذا كانت القيم أكبر في مقارنتين على الأقل، فإن إجمالي عدد القيم سيكون على الأقلن+ص-2{\displaystyle n+p-2}المقارنات. حجة خصومة ، حيث يتم اختيار نتيجة كل مقارنة من أجل تحقيق أقصى قدر من الفائدة.ص{\displaystyle p}(رهناً بالتوافق مع ترتيب واحد ممكن على الأقل) بدلاً من القيم العددية للعناصر المعطاة، يُظهر أنه من الممكن فرضص{\displaystyle p}أن يكون على الأقلسجل2⁡ن{\displaystyle \log _{2}n}وبالتالي ، فإن أسوأ عدد للمقارنات اللازمة لاختيار ثاني أصغر قيمة هون+⌈سجل2⁡ن⌉-2{\displaystyle n+\lceil \log _{2}n\rceil -2}وهو نفس العدد الذي يمكن الحصول عليه من خلال تنظيم بطولة إقصائية فردية مع جولة فاصلة بين القيم التي خسرت أمام أصغر قيمة. ومع ذلك، يمكن أن يكون العدد المتوقع للمقارنات في خوارزمية اختيار عشوائية أفضل من هذا الحد؛ على سبيل المثال، يتطلب اختيار ثاني أصغر عنصر من بين ستة عناصر سبع مقارنات في أسوأ الحالات، ولكن يمكن القيام بذلك بواسطة خوارزمية عشوائية بعدد متوقع يبلغ 6.5 مقارنات. [ 14 ]

وبشكل أعم، اختيارك{\displaystyle k}العنصر رقم 1 من بينن{\displaystyle n}يتطلب على الأقلن+مين(ك،ن-ك)-يا(1){\displaystyle n+\min(k,nk)-O(1)}في المتوسط، تتطابق المقارنات مع عدد مقارنات خوارزمية فلويد-ريفست حتىo(ن){\displaystyle o(n)}يُستخدم هذا المصطلح مباشرةً في سياق الخوارزميات الحتمية، حيث يُحسب عدد المقارنات كمتوسط ​​لجميع التباديل الممكنة لقيم المدخلات . [ 1 ] وبحسب مبدأ ياو ، ينطبق هذا أيضًا على العدد المتوقع للمقارنات لخوارزمية عشوائية على أسوأ حالة مدخلات لها. [ 34 ]

بالنسبة للخوارزميات الحتمية، فقد ثبت أن اختيارك{\displaystyle k}يتطلب العنصر th(1+ح(ك/ن))ن+Ω(ن){\displaystyle {\bigl (}1+H(k/n){\bigr )}n+\Omega ({\sqrt {n}})}المقارنات، حيثح(x)=xسجل2⁡1x+(1-x)سجل2⁡11-x{\displaystyle H(x)=x\log _{2}{\frac {1}{x}}+(1-x)\log _{2}{\frac {1}{1-x}}}هي دالة الإنتروبيا الثنائية . [ 35 ] الحالة الخاصة لإيجاد الوسيط لها حد أدنى أكبر قليلاً لعدد المقارنات، على الأقل(2+ε)ن{\displaystyle (2+\varepsilon )n}، لε≈2-80{\displaystyle \varepsilon \approx 2^{-80}}[ 36 ]​

الأعداد الدقيقة للمقارنات

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

يقدم كنوت المثلث التالي من الأرقام الذي يلخص أزواجًا منن{\displaystyle n}وك{\displaystyle k}والتي يكون فيها العدد الدقيق للمقارنات اللازمة لخوارزمية الاختيار الأمثل معروفاً.ن{\displaystyle n}الصف رقم 1 من المثلث (بدءًا منن=1{\displaystyle n=1}(في الصف العلوي) يوضح عدد المقارنات لمدخلات منن{\displaystyle n}القيم، وك{\displaystyle k}يشير الرقم الموجود في كل صف إلى عدد المقارنات اللازمة لاختيارك{\displaystyle k}أصغر قيمة من مدخلات بهذا الحجم. الصفوف متناظرة لأن اختيارك{\displaystyle k}يتطلب اختيار أصغر قيمة نفس عدد المقارنات تمامًا، في أسوأ الحالات، مثل اختيار القيمة الأصغر.ك{\displaystyle k}الأكبر . [ 14 ]

0
1 1  
2 3 2    
3 4 4 3      
4 6 6 6 4        
5 7 8 8 7 5          
6 8 10 10 10 8 6        
7 9 11 12 12 11 9 7         
8  11  12  14  14  14  12  11  8
9  12  14  15  16  16  15  14  12  9

يمكن إيجاد معظم، وليس كل، المدخلات الموجودة في النصف الأيسر من كل صف باستخدام الصيغةن-ك+(ك-1)⌈سجل2⁡(ن+2-ك)⌉.{\displaystyle n-k+(k-1){\bigl \lceil }\log _{2}(n+2-k){\bigr \rceil }.}يصف هذا عدد المقارنات التي تجريها طريقة عبد الله هاديان وميلتون سوبل ، المرتبطة باختيار الكومة، والتي تجد أصغر قيمة باستخدام بطولة إقصاء فردي، ثم تستخدم بشكل متكرر بطولة أصغر بين القيم التي تم استبعادها بواسطة الفائزين النهائيين في البطولة للعثور على القيم المتتالية التالية حتى الوصول إلىك{\displaystyle k}أصغرها . [ 14 ] [ 37 ] وقد ثبت أن بعض المدخلات الأكبر حجمًا هي الأمثل باستخدام البحث الحاسوبي. [ 14 ] [ 38 ]

الدعم اللغوي

قلة قليلة من لغات البرمجة تدعم بشكل مدمج عملية الاختيار العام، مع أن العديد منها يوفر أدوات لإيجاد أصغر أو أكبر عنصر في قائمة. ومن الاستثناءات البارزة المكتبات القياسية للغتي C++ و Rust . توفر مكتبة القوالب القياسية للغة C++ nth_elementدالة مُنمذجة مع ضمان وقت تنفيذ خطي متوقع. [ 3 ] أما مكتبة Rust القياسية، فتُوفر عدة صيغ للدالة select_nth_unstableالعضوية لنوع sliceالبيانات. وتضمن هذه الصيغ جميعها وقت تنفيذ خطي لجميع المدخلات. [ 39 ]

تتضمن مكتبة بايثون القياسية heapq.nsmallestدوالًا heapq.nlargestلإرجاع أصغر أو أكبر العناصر من مجموعة، بترتيب مُرتب. ويحتفظ التنفيذ بكومة ثنائية ، تقتصر على استيعابك{\displaystyle k}العناصر، وتمت تهيئتها إلى الأولك{\displaystyle k}عناصر المجموعة. بعد ذلك، يمكن لكل عنصر لاحق في المجموعة أن يحل محل أكبر أو أصغر عنصر في الكومة إذا كان أصغر أو أكبر من هذا العنصر. استخدام الذاكرة في هذه الخوارزمية أفضل من خوارزمية اختيار الكومة (الأولى تحتفظ فقط بـك{\displaystyle k}يتم تخزين العناصر في الذاكرة في وقت واحد، بينما يتطلب الأخير معالجة مجموعة البيانات بأكملها في الذاكرة. يعتمد وقت التشغيل على ترتيب البيانات. أفضل حالة هييا((ن-ك)+كسجل⁡ك){\displaystyle O((n-k)+k\log k)}بالنسبة للبيانات المصنفة مسبقًا. أسوأ الحالات هييا(نسجل⁡ك){\displaystyle O(n\log k)}بالنسبة للبيانات المرتبة عكسيًا. في المتوسط، من المرجح أن يكون هناك عدد قليل من تحديثات الذاكرة، وتُعالج معظم عناصر الإدخال بمقارنة واحدة فقط. على سبيل المثال، يتطلب استخراج أكبر أو أصغر 100 قيمة من بين 10,000,000 مدخل عشوائي 10,009,401 مقارنة في المتوسط. [ 40 ]

منذ عام 2017، أضافت Matlabmaxk() وظائف mink()تُرجع القيمة القصوى (الدنيا).ك{\displaystyle k}القيم في المتجه بالإضافة إلى مؤشراتها. لا تحدد وثائق Matlab الخوارزمية التي تستخدمها هذه الدوال أو وقت تشغيلها. [ 41 ]

تاريخ

عُرضت خوارزمية الاختيار السريع (Quickselect) دون تحليل من قِبل توني هوار عام 1965، [ 42 ] وخضعت لأول تحليل في تقرير فني عام 1971 من قِبل دونالد كنوث . [ 11 ] أما أول خوارزمية اختيار حتمية خطية معروفة فهي طريقة وسيط الوسائط ، التي نُشرت عام 1973 من قِبل مانويل بلوم ، وروبرت دبليو فلويد ، وفون برات ، ورون ريفست ، وروبرت تارجان . [ 5 ] ويعزو هؤلاء الباحثون صياغة مشكلة الاختيار إلى أعمال تشارلز إل دودجسون (المعروف باسم لويس كارول ) الذي أشار عام 1883 إلى أن التصميم المعتاد لبطولات الإقصاء الفردي في الرياضات لا يضمن فوز اللاعب صاحب المركز الثاني، [ 5 ] [ 43 ] وإلى أعمال هوغو شتاينهاوس حوالي عام 1930، الذي تابع هذا النهج الفكري نفسه، مطالبًا بتصميم بطولة يضمن ذلك، مع الحد الأدنى من المباريات (أي المقارنات). [ 5 ]

انظر أيضاً

مراجع

  1. 1 2 كونتو، والتر؛ مونرو، ج. إيان (1989). "اختيار الحالة المتوسطة" . مجلة ACM . 36 (2): 270-279 . doi : 10.1145 / 62044.62047 . MR 1072421. S2CID 10947879 .  
  2. 1 2 3 4 5 6 7 8 كورمن، توماس هـ .؛ ليسرسون، تشارلز إي .؛ ريفست، رونالد ل .؛ شتاين، كليفورد (2009) [1990]. "الفصل 9: الوسائط والإحصاءات الترتيبية". مقدمة في الخوارزميات ( الطبعة الثالثة). مطبعة معهد ماساتشوستس للتكنولوجيا وماكجرو هيل. الصفحات 213-227 . ISBN   0-262-03384-4.؛ "القسم 14.1: إحصاءات الترتيب الديناميكية"، الصفحات 339-345
  3. 1 2 3 4 سكينا، ستيفن س. (2020). "17.3: الوسيط والاختيار". دليل تصميم الخوارزميات . نصوص في علوم الحاسوب ( الطبعة الثالثة). سبرينغر. ص 514-516 . doi : 10.1007/978-3-030-54256-6 . ISBN   978-3-030-54255-9. MR 4241430 . S2CID 22382667 .  
  4. 1 2 3 4 5 إريكسون، جيف (يونيو 2019). "1.8: الاختيار الخطي". الخوارزميات . ص 35-39 . 
  5. 1 2 3 4 5 6 بلوم، مانويل ؛ فلويد، روبرت و.؛ برات ، فوغان ؛ ريفست، رونالد ل.؛ تارجان ، روبرت إي. (1973). "الحدود الزمنية للاختيار" (ملف PDF) . مجلة علوم الحاسوب والنظم . 7 (4): 448-461 . doi : 10.1016/S0022-0000(73)80033-9 . MR 0329916 . 
  6. ↑ برودال، جيرث ستولتينغ (2013). "دراسة استقصائية حول قوائم الانتظار ذات الأولوية". في: برودنيك، أندريه؛ لوبيز-أورتيز، أليخاندرو؛ رامان، فينكاتيش؛ فيولا، ألفريدو (محررون). هياكل البيانات، والتدفقات، والخوارزميات ذات الكفاءة المكانية - أوراق بحثية تكريمًا لجيه. إيان مونرو بمناسبة عيد ميلاده السادس والستين . سلسلة محاضرات في علوم الحاسوب. المجلد 8066. سبرينغر. الصفحات 150-163 . doi : 10.1007/978-3-642-40273-9_11 . ISBN   978-3-642-40272-2.
  7. 1 2 3 4 كلاينبرغ، جون ؛ تاردوس، إيفا (2006). "13.5 فرق تسد العشوائي: إيجاد الوسيط والفرز السريع". تصميم الخوارزميات . أديسون-ويسلي. ص 727-734 . ISBN  9780321295354.
  8. ↑ على سبيل المثال، يستخدم كورمن وآخرون تقسيم المصفوفة في مكانها، بينما يصف كلاينبيرج وتاردوس المدخلات على أنها مجموعة ويستخدمون طريقة تقسمها إلى مجموعتين جديدتين.
  9. 1 2 3 4 غودريتش، مايكل ت .؛ تاماسيا، روبرتو (2015). "9.2: الاختيار". تصميم الخوارزميات وتطبيقاتها . وايلي. ص 270-275 . ISBN  978-1-118-33591-8.
  10. ↑ ديفروي، لوك (1984). "الحدود الأسية لوقت تشغيل خوارزمية الاختيار" (ملف PDF) . مجلة علوم الحاسوب والنظم . 29 (1): 1-7 . doi : 10.1016/0022-0000(84)90009-6 . MR 0761047 . ديفروي، لوك (2001). "حول أسوأ وقت احتمالي لـ 'العثور'"( PDF) . Algorithmica . 31 (3): 291–303 . doi : 10.1007/ s00453-001-0046-2 . MR 1855252. S2CID 674040 .  
  11. 1 2 فلويد، روبرت و .؛ ريفست، رونالد ل. (مارس 1975). "الحدود الزمنية المتوقعة للاختيار" . اتصالات رابطة آلات الحوسبة . 18 (3): 165-172 . doi : 10.1145/360680.360691 . S2CID 3064709 . انظر أيضًا "الخوارزمية 489: خوارزمية SELECT - لإيجادأنا{\displaystyle i}أصغر​ن{\displaystyle n}العناصر"، ص 173، doi : 10.1145/360680.360694 .
  12. ↑ براون، ثيودور (سبتمبر 1976). "ملاحظة على الخوارزمية 489". معاملات ACM في البرمجيات الرياضية . 2 (3): 301-304 . doi : 10.1145/355694.355704 . S2CID 13985011 . 
  13. ↑ بوستمس، جيه تي؛ رينوي كان، إيه إتش جي ؛ تيمر، جي تي (1983). "طريقة اختيار ديناميكية فعالة" . اتصالات رابطة مكائن ​​الحوسبة . 26 (11): 878-881 . doi : 10.1145/182.358440 . MR 0784120. S2CID 3211474 .  
  14. 1 2 3 4 5 6 كنوت، دونالد إي. (1998). "القسم 5.3.3: اختيار المقارنة الدنيا". فن برمجة الحاسوب، المجلد 3: الفرز والبحث ( الطبعة الثانية). أديسون-ويسلي. الصفحات 207-219 . ISBN   0-201-89685-0.
  15. ↑ كارلوف، هوارد جيه؛ راغافان، برابهاكار (1993). " الخوارزميات العشوائية والأرقام شبه العشوائية" . مجلة ACM . 40 (3): 454-476 . doi : 10.1145/174130.174132 . MR 1370358. S2CID 17956460 .  
  16. ↑ غورويتز، تشايا (1992). "حول تدريس خوارزميات إيجاد الوسيط". معاملات IEEE في التعليم . 35 (3): 230-232 . Bibcode : 1992ITEdu..35..230G . doi : 10.1109/13.144650 .
  17. ↑ موسر، ديفيد ر. (أغسطس 1997). "خوارزميات الفرز والاختيار الاستبطانية". البرمجيات: الممارسة والخبرة . 27 (8). وايلي: 983-993 . doi : 10.1002/(sici)1097-024x(199708)27:8 < 983::aid-spe117 > 3.0.co ; 2-# .
  18. ↑ شونهاج، أ .؛ باترسون، م .؛ بيبنجر، ن. (1976). "إيجاد الوسيط". مجلة علوم الحاسوب والنظم . 13 (2): 184-199 . doi : 10.1016 / S0022-0000(76)80029-3 . MR 0428794. S2CID 29867292 .  
  19. ↑ دور، دوريت ؛ زويك ، أوري (1999). "اختيار الوسيط". مجلة SIAM للحوسبة . 28 (5): 1722-1758 . doi : 10.1137/S0097539795288611 . MR 1694164. S2CID 2633282 .  
  20. ↑ فاليانت، ليزلي ج. (1975). "التوازي في مسائل المقارنة". مجلة SIAM للحوسبة . 4 (3): 348-355 . doi : 10.1137/0204030 . MR 0378467 . 
  21. ^ أجتاي، ميكلوس ؛ كوملوس, يانوس ; ستيجر، WL. سيميريدي، إندري (1989). "الاختيار الموازي الأمثل له تعقيديا(سجل⁡سجل⁡ن){\displaystyle O(\log \log n)}". مجلة علوم الحاسوب والأنظمة . 38 (1): 125– 133. doi : 10.1016/0022-0000(89)90035-4 . MR 0990052 . 
  22. ↑ آزار، يوسي؛ بيبنجر، نيكولاس (1990). "الاختيار المتوازي". الرياضيات التطبيقية المنفصلة . 27 ( 1-2 ): 49-58 . doi : 10.1016/0166-218X(90)90128-Y . MR 1055590 . 
  23. ↑ رايشوك، روديجر (1985). "خوارزميات متوازية احتمالية للفرز والاختيار". مجلة SIAM للحوسبة . 14 (2): 396-409 . doi : 10.1137/0214030 . MR 0784745 . 
  24. ↑ هان، ييجي (2007). "الاختيار الأمثل المتوازي". معاملات ACM في الخوارزميات . 3 (4): A38:1–A38:11. doi : 10.1145 /1290672.1290675 . MR 2364962. S2CID 9645870 .  
  25. ↑ تشودري، شيفا؛ هاجيروب، توربن؛ رامان، راجيف (1993). "الاختيار المتوازي الحتمي التقريبي والدقيق". في: بورزيسكوفسكي، أندريه م.؛ سوكولوفسكي، ستيفان (محرران). الأسس الرياضية لعلوم الحاسوب 1993، الندوة الدولية الثامنة عشرة، MFCS'93، غدانسك، بولندا، 30 أغسطس - 3 سبتمبر 1993، وقائع المؤتمر . سلسلة محاضرات في علوم الحاسوب. المجلد 711. سبرينغر. الصفحات 352-361 . doi : 10.1007/3-540-57182-5_27 . hdl : 11858/00-001M-0000-0014-B748-C . ISBN   978-3-540-57182-7.
  26. ↑ ديتز، بول ف.؛ رامان، راجيف (1999). "اختيار الرتبة الصغيرة بالتوازي، مع تطبيقات على بناء الكومة". مجلة الخوارزميات . 30 (1): 33-51 . doi : 10.1006/jagm.1998.0971 . MR 1661179 . 
  27. 1 2 فريدريكسون، جريج ن.؛ جونسون، دونالد ب. (1984). "الاختيار والترتيب المعمم: المصفوفات المصنفة". مجلة SIAM للحوسبة . 13 (1): 14-30 . doi : 10.1137/0213002 . MR 0731024 . 
  28. 1 2 3 4 كابلان، حاييم؛ كوزما، لازلو؛ زامير، أور؛ زويك، أوري (2019). "الاختيار من الأكوام، والمصفوفات المرتبة صفّياً، وX+Y{\displaystyle X+Y}باستخدام أكوام ناعمة". في فاينمان، جيريمي ت.؛ ميتزنماخر، مايكل (محرران). الندوة الثانية حول البساطة في الخوارزميات، SOSA 2019، 8-9 يناير 2019، سان دييغو، كاليفورنيا، الولايات المتحدة الأمريكية . OASICs. المجلد.  69. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. ص. 5 : 1–5 : 21  .​​​
  29. ↑ فريدريكسون، جريج ن. (1993). "خوارزمية مثلى للاختيار في كومة دنيا" . المعلومات والحوسبة . 104 (2): 197-214 . doi : 10.1006/inco.1993.1030 . MR 1221889 . 
  30. ↑ إبستين، ديفيد (1999). "إيجادك{\displaystyle k}"أقصر المسارات". مجلة SIAM للحوسبة . 28 (2): 652-673 . doi : 10.1137/S0097539795290477 . MR 1634364 . 
  31. ↑ بابينكو، مكسيم؛ كوليسنيتشينكو، إغنات؛ سميرنوف، إيفان (2019). "الكومة المتتالية: نحو استخلاصات مثالية زمنيًا". نظرية أنظمة الحوسبة . 63 (4): 637-646 . doi : 10.1007/s00224-018-9866-1 . MR 3942251. S2CID 253740380 .  
  32. ↑ باتراشكو، ميهاي ؛ ثورب، ميكيل (2014). "مجموعات الأعداد الصحيحة الديناميكية مع الترتيب الأمثل، والاختيار، والبحث عن السلف". المؤتمر السنوي الخامس والخمسون لجمعية مهندسي الكهرباء والإلكترونيات حول أسس علوم الحاسوب، FOCS 2014، فيلادلفيا، بنسلفانيا، الولايات المتحدة الأمريكية، 18-21 أكتوبر 2014. جمعية مهندسي الكهرباء والإلكترونيات. الصفحات 166-175 . arXiv : 1408.3045 . doi : 10.1109/FOCS.2014.26 . ISBN  978-1-4799-6517-5.
  33. ↑ كورمود، غراهام؛ موثوكريشنان، س. (2005). "ملخص مُحسَّن لتدفق البيانات: رسم عد-أدنى وتطبيقاته". مجلة الخوارزميات . 55 (1): 58-75 . doi : 10.1016/j.jalgor.2003.12.001 . MR 2132028 . 
  34. ↑ تشان، تيموثي م. (2010). "حدود دنيا للوقت والمكان للاختيار قائمة على المقارنة". معاملات ACM في الخوارزميات . 6 (2): A26:1–A26:16. doi : 10.1145 /1721837.1721842 . MR 2675693. S2CID 11742607 .  
  35. ↑ بنت، صموئيل و.؛ جون، جون و. (1985). "يتطلب إيجاد الوسيط2ن{\displaystyle 2n}المقارنات". في: سيدجويك، روبرت (محرر). وقائع الندوة السنوية السابعة عشرة لجمعية آلات الحوسبة حول نظرية الحوسبة، 6-8 مايو 1985، بروفيدنس، رود آيلاند، الولايات المتحدة الأمريكية . جمعية آلات الحوسبة. الصفحات 213-216 . doi : 10.1145/22145.22169 . ISBN  0-89791-151-2.
  36. ↑ دور، دوريت ؛ زويك، أوري (2001). "يتطلب اختيار الوسيط(2+ε)شمال{\displaystyle (2+\varepsilon )N}"المقارنات". مجلة SIAM للرياضيات المتقطعة . 14 (3): 312-325 . doi : 10.1137/S0895480199353895 . MR 1857348 . 
  37. ^ هاديان، عبد الله. سوبيل ، ميلتون (مايو 1969). اختيارت{\displaystyle t}أكبر قيمة باستخدام المقارنات الثنائية الخالية من الأخطاء (تقرير). تقارير فنية من كلية الإحصاء. المجلد  121. جامعة مينيسوتا. hdl : 11299/199105 .
  38. ↑ غاسارش، ويليام ؛ كيلي، واين؛ بو، ويليام (يوليو 1996). "إيجادأنا{\displaystyle i}الأكبر منن{\displaystyle n}للصغارأنا،ن{\displaystyle i,n}". ACM SIGACT News . 27 (2): 88–96 . doi : 10.1145/235767.235772 . S2CID 3133332 . 
  39. ↑ "شريحة النوع البدائي" . مكتبة Rust القياسية . تم الاسترجاع في 12-10-2025 .
  40. ↑ "شفرة مصدر حزمة heapq" . مكتبة بايثون . تم الاطلاع عليها بتاريخ 2023-08-06 .انظر أيضًا إلى المقارنة المرتبطة لأداء الخوارزمية على بيانات أفضل الحالات .
  41. ↑ "mink: إيجاد أصغر k عنصر في المصفوفة" . وثائق Matlab R2023a . Mathworks . تم الاطلاع بتاريخ 30-03-2023 .
  42. ↑ هوار، سي إيه آر (يوليو 1961). "الخوارزمية 65: البحث". اتصالات رابطة آلات الحوسبة . 4 (7): 321-322 . doi : 10.1145/366622.366647 .
  43. ↑ دودجسون، تشارلز ل. (1883). بطولات التنس على العشب: الطريقة الصحيحة لتوزيع الجوائز مع إثبات خطأ الطريقة الحالية . لندن: ماكميلان وشركاه.انظر أيضًا: ويلسون، روبن ؛ ومقتفي، أميروش، محرران (2019). "بطولات التنس على العشب" . العالم الرياضي لتشارلز ل. دودجسون (لويس كارول) . مطبعة جامعة أكسفورد. ص 129. ISBN  9780192549013.