چند سوال الگوریتم از بین تستهای ارشد.

[Developer Programmer]

در زیر چند تا اشکال رو که در حین مطالعه درس طراحی الگوریتم ها و بررسی تستهای کنکور بهشون برخوردم. مطرح میکنم. (متاسفانه نتونستم در منابعی که داشتم جوابهاشون رو پیدا کنم.)
از دوستان خواهش میکنم تا هرجایی که میتونن کمکم کنن و از ارسال پستهای بی ربط و اضافی خودداری کنن.

1) با استفاده از ایده Partition در Quick Sort ؛ K امین کوچکترین عنصر، بین n عنصر نامرتب را بیابید

2)پیچیدگی زمانی K امین کوچکترین عدد و میانه n عنصر نامرتب چقدر است ؟

3 ) یک الگوریتم تقسیم و حل پیچیده، برای حل مساله ای به اندازه n ، آنرا به C زیرمساله به اندازه n/3 تقسیم میکند و راه حل زیرمسائل را در زمان O(n^2)( ترکیب میکند، اگر پیچیدگی زمانی این الگوریتم در بدترین حالت O(n^3) باشد، مقدار C را پیدا کنید.

4) جستجوی باینری را طوری دستکاری کنید که نمونه را به 3 قسمت مساوی تقسیم کند. پیچیدگی زمانی چند است ؟

5) مساله فوق را برای الگوریتم MergerSort پیاده کنید.

6) فرض کنید در تقسیم و حل، نمونه به 10 زیر نمونه به اندازه n/3 تقسیم میشود و مراحل تقسیم و ترکیب، از n^2 می باشد؛ معادله T(n را بیابید