سوال ۷۶ کنکور ارشد علوم کامپیوتر ۱۴۰۴
اهمیت
۰/۵
فرض کنید آرایه‌ای از n عنصر داده شده است و می‌خواهیم میانه (Median) آن را با استفاده از روش تقسیم و حل (Divide and Conquer) پیدا کنیم. کدام‌یک از گزینه‌های زیر درباره الگوریتمی که این مسئله را به‌درستی و با کمترین زمان حل، پاسخ را محاسبه می‌کند، صحیح است؟
پاسخ صحیح: گزینهٔ C — با استفاده از افرازِ مبتنی بر انتخاب (QuickSelect / تقسیم و حل) میانه در زمان پیدا می‌شود و می‌تواند بدون مرتب‌سازی کامل آرایه، میانه را پیدا کند.
پاسخ تشریحی
The median is the -th smallest element, i.e. a special case of the selection problem (finding the -th order statistic). …
ادامهٔ پاسخ تشریحی ویژهٔ مشترکان است.
مشاهدهٔ پاسخ کامل#median#selection#quickselect#median-of-medians#divide-and-conquer#linear-time