سلام
این الگوریتم از دو قسمت تشکیل شده:
الف)غیر بازگشتی:
۱) پیدا کردن میانه‌: از مرتبه‌ی n
۲) تشکیل سه مجموعه (اعضای کوچکتر از میانه)L و (اعضای مساوی با میانه) E و(اعضای بزرگتر از میانه) B: از مرتبه‌ی n
ب)بازگشتی:
۳) پر کردن کوله پشتی:
چون ما دنبال بیشترین‌ها هستیم میریم سراغ B‌ :
۱) اگه مجموع اعضای B مساوی با w باشه‌، مسئله حله !
۲)اگه مجموع اعضای B بزرگتر ازw باشه‌، الگوریتم روی B تکرار میشه تا جایی که مجموع کوچکتر مساوی w بشه ؛ اگه مساوی شد میریم ۱ ؛ اگه کوجکتر شد میریم ۳ .
۳) اگه مجموع اعضای B کوچکتر ازw باشه ‌، کل B انتخاب میشه و کسری کوله از E و در صورت نیاز از L تامین میشه (با تکرار الگوریتم و مراحل ۱و۲و۳ روی E و در صورت نیاز L).
همون طور که دیدین در هر کدوم از این سه حالت الگوریتم روی n/2 اعضا تکرار میشه
بنابراین زمان بازگشتی برابر با‌: T(n)=T(n/2)+n
ودر نتیجه طبق master الگوریتم از مرتبه‌ی n هست.

---

(۲۰ آبان ۱۳۸۹ ۰۵:۲۹ ب.ظ)admin نوشته شده توسط:  جالب شد قضیه، یعنی الگوریتمی از پیچیدگی n وجود داره برای این مسئله؟؟

من هر طور فکر می کنم می بینم که این الگوریتم نیاز به یه مرتب سازی داره( به هر شیوه ای) و مرتب سازی رو با nlogn می شه انجام داد.
چون کوله پشتی کسری هست نمی شه از روش های hash استفاده کرد. جالب میشه دوستان این الگوریتم رو قرار بدن.( البته به صورت pdf و یا doc بهتره تا بشه خوندش)

حب مسئله اینه که این الگوریتم اعضا رو مرتب نمیکنه بلکه هر بار یه مجموعه نامرتب از اعضای از میانه بیشتر تشکیل میده‌، جمعشون میکنه و اگه دید از w بزرگتر یا کوچکترن اصلاحشون میکنه تا به هدف برسه.

---

(۱۹ آبان ۱۳۸۹ ۱۱:۵۲ ق.ظ)۵۴m4n3h نوشته شده توسط:  توی هر مرحله عنصر وسط رو در مرتبه‌ی n پیدا میکنه و هر بار هم کل مجموعه رو ۲ یا ۳ قسمت میکنه انگار که n رو بر ۲ یا ۳ تقسیم کنه، پس میشه گفت به طور متوسط در logn مرحله به جواب میرسه با این استدلالی که من کردم مرتبه‌ی الگوریتم میشه n logn !

هر بار الگوریتم تنها روی نصف مجموعه تکرار میشه نه روی کل مجموعه به همین خاطر، T(n/2 داریم نه ۲T(n/2 .