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

[Afshin_Zavar]

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

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 را بیابید

[someCoder]

سلام،
1- فرض کن عنصر k امین عنصر رو میخوای. پارتیشن میکنی لیستت رو و عنصر محوری رو بررسی میکنی که کجا قرار میگیره. اگر در خونه k بود که خودشه. اگر قبل از k بود، همین کار رو فقط رو قسمت اول تکرار میکنی و اگر بزرگتر رو قسمت دوم. اینقدر این کار رو میکنی که عنصر محوری همون k بشه.

4- (t(n)=3*t(n/3 و در حالت اگر به k قسمت تقسیم کنی میشه: (t(n)=K*t(n/K
که اگر حلش کنی میشه k-1 ضربدر لگاریتم n در مبنای k-1
(چون امکان فرمول نویسی نیست، فارسی نوشتم)

ضمنا سوالات رو جدا جدا بپرسی فکر کنم بهتر جواب بگیری

[Afshin_Zavar]

ابتدا، از وقتی که گذاشتین و جوابی که بدون جملات اضافی دادین تشکر میکنم.
فرض کن عنصر k امین عنصر رو میخوای. پارتیشن میکنی لیستت رو و عنصر محوری رو بررسی میکنی که کجا قرار میگیره. اگر در خونه k بود که خودشه. اگر قبل از k بود، همین کار رو فقط رو قسمت اول تکرار میکنی و اگر بزرگتر رو قسمت دوم. اینقدر این کار رو میکنی که عنصر محوری همون k بشه.
به نکته جالبی اشاره کردید، که من تا حال در مورد پارتیشن بندی دقت نکرده بودم و فقط حفظ کرده بودم(منظورم؛ عنصر محوری K در خونه K ام) ؛ احیانا اگه الگوریتم(شبه کد) رو دارید ممنون میشم. چون دنبال پیچیدگیش هم هستم.
4- (t(n)=3*t(n/3 و در حالت اگر به k قسمت تقسیم کنی میشه: (t(n)=K*t(n/K
خوب با توجه به فرمول شما، اگه لیست رو به دو قسمت تقسیم کنیم، میشه
[code]
t(n)=2t(n/2)
[/code[
که برابر n میشه (و نه log n)