المپدیا

دانش‌نامه‌ی المپیاد کامپیوتر ایران

ابزار کاربر

ابزار سایت


آموزش:الگوریتم:مرتبه ی آماری

مرتبه‌ی آماری

تعریف

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

در زبان ++C این کار به کمک تابع nth_element صورت می‌گیرد.


ابزار صفحه