یافتن K امین کوچکترین عدد

[Developer Programmer]

همونطوری که میدونید توی همه کتابا این مسئله رو با الگوریتم Quick Sort حل میکنن.

سواله من اینه که اگه اعداد رو روی Min Heap بریزیم و K بار عمل حذف انجام بدیم، K مین کوچکترین عدد بدست میآد یا نه؟ یچیدگیش چند میتونه باشه؟ ( k log n+ nlogn ) ؟؟ از ( n^2) بدتره؟!

[manager]

HTML clipboardهمونظور که خودتون گفتید Kمین عنصر کوچکتر رو می شه با زمان مصرفی (O(nlogn یافت ولی با استفاده از تابع Partition الگوریتم مرتب سازی Quick Sort می شه این زمان رو (با اصلاح الگوریتم) به (θ(n کاهش داد. چون برای پیدا کردن کوچکترین kمین کلید شما نیازی ندارید تمام عناصر رو سر جاهای خودشون بشونید تا ببینید جای موقعیت kام چه عددی نشسته و فقط کافیه بتونید عنصری رو که قرار در جای موقعیت kام بشینه پیدا کنید. الگوریتم و زمان مصرفی دقیق این کار تو کتاب طراحی الگوریتم ارشد گسترش علوم پایه مقسمی اومده البته گشتم دنبال اینکه ببینم از کدوم کتاب "کپی" کرده ولی پیدا نکردم.

[pesar irooni]

با استفاده از درخت آمار ترتیبی که یک درخت قرمز سیاه بهبود یافته است این کار رو میتونیم تو log n انجام بدیم.