تالار گفتمان مانشت

در الگوریتم پیدا کردن K امین کوچکترین عنصر از میان N عنصر ،ابتدا همه عناصر را به دسته های 5تای تقسیم،میانه هر دسته را بدست آورده و سپس میانه ها را به صورت بازگشتی پیدا میکنیم،این عنصر را به عنوان محور انتخاب و عمل Partition را روی آرایه عناصر انجام می دهیم.پس از آن همین الگوریتم را بصورت بازگشتی روی یکی از بخش ها اجرا میکنیم تا عنصر مورد نظر پیدا شود .زمان اجرای الگوریتم کدام است؟این رابطه بازگشتی چطور بدست اومده؟
جواب:
[tex]t(n)=t(n/5) t(7n/10 6) o(n)[/tex]

(06 مهر 1391 04:37 ب.ظ)parasto نوشته شده توسط: [ -> ]در الگوریتم پیدا کردن K امین کوچکترین عنصر از میان N عنصر ،ابتدا همه عناصر را به دسته های ۵تای تقسیم،میانه هر دسته را بدست آورده و سپس میانه ها را به صورت بازگشتی پیدا میکنیم،این عنصر را به عنوان محور انتخاب و عمل Partition را روی آرایه عناصر انجام می دهیم.پس از آن همین الگوریتم را بصورت بازگشتی روی یکی از بخش ها اجرا میکنیم تا عنصر مورد نظر پیدا شود .زمان اجرای الگوریتم کدام است؟این رابطه بازگشتی چطور بدست اومده؟
جواب:
[tex]t(n)=t(n/5) t(7n/10 6) o(n)[/tex]

این روش به «میانه میانه ها» معروف هست.
مرتبه اجرایی این روش خطی هست بصورت [tex]\Theta (n)[/tex]

[tex]t(7n/10 6)[/tex] در واقع نشون میده که موقع افراز کردن، هر زیر لیست حداکثر این تعداد عضو داره و به همین خاطر به این شکل در رایطه قرار داره.

[tex]t(n)=t(n/5) t(7n/10 6) o(n)[/tex]
[/quote]


میشه این قسمت رو که هر کدوم از لیستا به [tex]t(7n/10 6)[/tex] افراز میشن رو توضیح بدین؟

عناصر آرایه به دو گروه تقسیم میشن. اونایی که بزرگتر از میانه میانه ها هستند و اونایی که کوچکتر از میانه میانه ها هستند! در مرحله بعدی باید در دسته ای که بزرگتر هست دنبال عنصر مورد نظر بگردید (چون دارید مرتبه زمانی اجرا رو پیدا میکنید)

[tex]3(\frac{1}{2}(\frac{n}{5}) - 2) = \frac{3n}{10} - 6[/tex] = تعداد عناصر بزرگتر از میانه میانه ها
[tex]n - (\frac{3n}{10} - 6) = \frac{7n}{10} 6[/tex] = پس تعداد عناصر کوچکتر از میانه میانه ها
چون [tex]\frac{3n}{10} - 6 < \frac{7n}{10} 6[/tex] پس در دسته دوم باید دنبال میانه میانه ها بگردید.
این فرمولایی که نوشتم تعداد دقیق نیست سقف و کف هستند.

پ.ن: فکر نمیکنم اصلا لازم باشه خودتون رو درگیر این رابطه کنید اما باز اگر سوالی از جزئیات هست در خدمتم

اما این که نشد اثبات !
ما که متوجه نشدیم رابطه ی بازگشتی چه طوری بدست اومد. یا کامل توضیح بدید یا یه کتاب معرفی کنید و آدرس بدید خودمون بریم کامل مطالعه کنیم.
مثلا اگه CLRS هست بگید فلان صفحه فلان بخش و .... ما بریم کامل مطالعه کنیم.

(10 آبان 1391 04:07 ب.ظ)csharpisatechnology نوشته شده توسط: [ -> ]یا کامل توضیح بدید یا یه کتاب معرفی کنید و آدرس بدید خودمون بریم کامل مطالعه کنیم.
مثلا اگه CLRS هست بگید فلان صفحه فلان بخش و .... ما بریم کامل مطالعه کنیم.

ویرایش سوم، فصل نهم، بخش سوم