n عدد نامرتب و نامساوی داده شده اند. میخواهیم جمع کوچکترین رادیکال n عددهای این اعداد را پیدا کنیم.
یک الگوزیتم کارا این مسئله را در چه زمانی حل میکند؟
باید رادیکال n امین عدد رو پیدا کنی که این همون الگوریتم کوچکترین k امین عنصر هستش که هزینه اجراش O(n) هست . حالا این رادیکال n امین عددرو که پیدا کردی می شه عنصر محور ،که باید اعداد قبلش رو با خودش جمع کنی و جمع رادیکال n عدد هم از مرتبه O(رادیکال n( می شه .
پس هزینه کل همون O(n) .
ana_12345 درست گفته.
--------------------
از الگوریتم یافتن میانه استفاده می کنیم.در هر مرحله اول یه محور رو پیدا می کنیم و سپس اعداد را به کمک این محور به دو بخش اعداد بیشتر از محور و کمتر از آن تقسیم می کنیم.سپس با مقایسه ی طول این دو بخش با مقدار رادیکال n ،تصمیم گرفته می شود که الگوریتم به چه صورتی در روی یکی از اینها بازگشتی اجرا شود.به روشی مشابه روش الگوریتم انتخاب میانه ی آماری می توان نشان داد که زمان بری الگوریتم o_n می باشد.
پس از یافتن رادیکال n امین عدد، در o_n اعداد کوچکتر از آن را می یابیم و جمع آنها را حساب می کنیم.
---
کلا میشه o_n