الگوریتم شناسایی میانه

یافتن میانه یا $\frac{n}{2}$ امین عنصر از نظر کوچکی در یک آرایه حالت خاصی از الگوریتم شناسایی عنصر kام می‌باشد. پیدا کردن میانه با زمان بهینه در الگوریتم مرتب‌سازی سریع می‌تواند مرتبه زمانی الگوریتم را در بدترین حالت به $O(n\log n)$ برساند. با توجه به این که الگوریتم شناسایی عنصر kام از $O(n)$ می‌باشد و این بهترین مرتبه زمانی ممکن است (حداقل یک بار باید آرایه خوانده بشود) بنابراین بهترین الگوریتم شناسایی میانه نیز از همین مرتبه زمانی است. الگوریتم‌های دیگری مانند میانه‌ی میانه‌ها وجود دارند که تنها تضمین می‌کنند جواب مسئله در بازه‌ی خاصی از آرایه قرار دارد، مثلاً بین مرتبه‌ی آماری $\frac{3n}{10}$ و $\frac{7n}{10}$ قرار دارد. این الگوریتم‌ها تصادفی نیستند و با توجه به این که استفاده از عنصر $\frac{n}{k}$ام به جای عنصر $\frac{n}{2}$ام تنها مبنای لگاریتم در تابع زمان را تغییر می‌دهد، اردر الگوریتم ثابت می‌ماند و از آن‌ها نیز می‌توان برای این کار استفاده کرد. این کار در عمل صورت نمی‌گیرد، امّا در تئوری استفاده نکردن از بیت‌های تصادفی و قطعیت کامل الگوریتم ارزشمند است.

مراجع