الگوریتم خطی برای پیدا کردن میانه یا median در یک آرایه - هفت خط کد انجمن پرسش و پاسخ برنامه نویسی

وبـــلاگ هــفت خــط کــد


آموزش های برنامه نویسی
۱۵۷ نفر آنلاین
۰ عضو و ۱۵۷ مهمان در سایت حاضرند

الگوریتم خطی برای پیدا کردن میانه یا median در یک آرایه

+1 امتیاز
467 بازدید
سلام .

یکی از راه های پیدا کردن  میانه این هست که آرایه ورودی را مرتب کنیم و عنصر وسط را برگردانیم .

آیا  راهی سریع تر از این روش و  با (O(n وجود داره ؟
سوال شده دی 16, 1393  بوسیله ی PSPCoder (امتیاز 1,417)   2 13 47

2 پاسخ

+2 امتیاز
 
بهترین پاسخ

این کد با (O(n هست که داخل ویژوال استودیو و پیاده سازی std::nth_element وجودداره  و میشه ازش برای پیدا کردن میانه استفاده کرد .

template<class _RanIt,
	class _Pr> inline
	void _Nth_element(_RanIt _First, _RanIt _Nth, _RanIt _Last, _Pr _Pred)
	{	// order Nth element, using _Pred
	for (; _ISORT_MAX < _Last - _First; )
		{	// divide and conquer, ordering partition containing Nth
		pair<_RanIt, _RanIt> _Mid =
			_Unguarded_partition(_First, _Last, _Pred);

		if (_Mid.second <= _Nth)
			_First = _Mid.second;
		else if (_Mid.first <= _Nth)
			return;	// Nth inside fat pivot, done
		else
			_Last = _Mid.first;
		}

	_Insertion_sort(_First, _Last, _Pred);	// sort any remainder
	}

نحوه کار:

ورودی :

  •    اشاره گر به شروع آرایه _First
  •    اشاره گر به عنصر n ام _Nth
  •    اشاره گر به پایان آرایه _Last

خروجی :

  •    عنصری از آرایه که از n عنصر بزرگ تر هست .

 

الگوریتم :

  1. یک عنصر راندوم از بازه _First تا _Last انتخاب می کنیم .
  2. عملیات پارتیشن رو بر روی این عنصر انجام میدیم (یعنی همه ی عناصر کوچک تر رو قبل از این عنصر قرار میدیم ( داخل این تاپیک هم کدش رو گذاشته بودم ))
  3. محل جدید این عنصر رو _Mid میزاریم حالا 3 حالت ممکنه  پیش میاد :
  •     اگر محل _Mid از _Nth کمتر بود مرحله 1 رو دوباره از بازه _First تا _Mid تکرار می کنیم .
  •     اگر محل _Mid از _Nth بیشتر بود مرحله 1 رو اینبار از بازه _Mid تا  _Last تکرار می کنیم .
  •     اگر _Mid با _Nth برابر بود یعنی میانه پیدا شده .
 
البته داخل  پیاده ساز ی بالا  برای سرعت بیشتر در صورتی که سایز آرایه کوچیک باشه (کمتر از 32 ) از insertation sort استفاده می کنه و عنصر n ام رو بعد از sort کردن بر می گردونه .(چون insertation sort بدلیل cache friendly بودن و cache prefetching برای  سایز های کوچیک فوق العاده سریع هست )
 
 
این الگوریتم در حالت میانگین با (O(n میانه رو پیدا می کنه .
پاسخ داده شده دی 17, 1393 بوسیله ی BlueBlade (امتیاز 15,742)   13 17 85
+2 امتیاز

مرتب کردن آرایه زمان nlogn رو داره پس این راهش نیست هر چند اینجا  یه چیزایی بحث شده

یکی از راه های کلاسیک اینه که شما بیاین آرایه رو به دسنه n/5 تقسیم کنی ، بعد هر دسته رو با زمان 1 مرتب کنی و میانه هر دسته رو بدست بیاری بعد به صورت بازگشتی میانه میانه ها رو از اون n/5 بدست بیاری.بعد میانه ی میانه ها رو به الگوریتم pivot در quicksort بده.در کل هزینه ی زیر رو داریم :

T(n)=n/5+t(n/5)+n+T(7n/10+6)

در بهترین حالت نصف دسته ها میانه ای کمتر ازمیانه میانه ها داره و هر دسته حداقل 3عنصر کوجکتر از میانه میانه ها داره پس 3n/10-6 پس این رو از n کم می کنیم تا بدترین هزینه بدست بیاد

این الگوریتم یک الگوریتم مشهور برای بدست آوردن k امین عدد در یک آرایه است که میانه تقریبا عنصر n/2 آرایه است

برای مطالعه دقیق تر از اینجا استفاده کنید

پاسخ داده شده دی 16, 1393 بوسیله ی Pakniat (امتیاز 382)   2 5 27
...