تالار گفتمان مانشت

دوستان عزیز سلام
به نظر شما گزینه صحیح کدومه؟!

من به نظرم 4 درسته!اما پاسخ تست گزینه 3 هستش!
نظرتون چیه ؟!
پیشاپیش ممنون

(28 آذر 1391 12:48 ب.ظ)8Operation نوشته شده توسط: [ -> ]دوستان عزیز سلام
به نظر شما گزینه صحیح کدومه؟!

من به نظرم ۴ درسته!اما پاسخ تست گزینه ۳ هستش!
نظرتون چیه ؟!
پیشاپیش ممنون

سلام
هم جواب شما صحیح است و هم جواب طراح ولی توجه کنید که گفته بر اساس این رابطه بازگشتی. (این رابطه بازگشتی رو داده که به طرف بفهمونه که الگوریتم من از نوع تقسیم و غلبه بوده ! یعنی نرو سراغ الگوریتم های درجی و انتخابی )
البته بگم که این تست نرمالی نیست واحتملآ تست آزاد هست.

دوستان عزیز خیلی ممنون از راهنماییتون.......
اینم جوابیه که طراح داده:

(28 آذر 1391 02:16 ب.ظ)esi نوشته شده توسط: [ -> ]چون بدترین حالت رو گفته گزینه 4 درسته، اما در کل کارایی الگوریتم سریع همیشه nlogn در نظر گرفته میشه اما مسلما بدترین حالتش n^2 هستش.
در کل آره، حق با شماست، گزینه 4 درسته.

گزینه ۴ درست نیست. به همون دلیلی که در پست ۲ گفته شده

(28 آذر 1391 06:27 ب.ظ)mfXpert نوشته شده توسط: [ -> ]گزینه ۴ درست نیست. به همون دلیلی که در پست ۲ گفته شده

بله میشه در نهایت اینگونه جمع بندی کرد.....

رابطه بازگشتی برای دو الگوریتم selection(در همه حالات) , insertion(در بدترین حالت) :

[tex]T(n)= T(n-1) \theta (n)[/tex]

در الگوریتم quick sort در بدترین حالت در صورتی که مرتب شده باشند و pvot عنصر ابتدای ارایه انتخاب شده باشد:
[tex]T(n)= T(\frac{n}{2}) O (n)[/tex]

در نتیجه گزینه 3 درسته.

در بدترین حالت اگه لولا عنصر ابتدایی یا تنهایی بشه در نتیجه n-1 عنصر باقی خواهد ماند و رابطه بازگشتی مشابه همون رابطه T(n)=T(n-1)+O(n)a خواهد شد !!!!!!!!!!!!
خوب این چه ربطی به رابطه ایکه تویه صورت سوال گفته داره، اون برای حالتی که دقیقا آرایه نصب بشه، یعنی بهترین حالت ممکنه، حالت متوسط هم به صورت nlnn هستش که تو اکثر کتابا دقیقشو نوشته(با محاسبه احتمال قرار گیری لولا در جاهای مختلف) و همون O(nlogn)a میشه.

ممنون
حق با شماست
بعد از ارسال یه کم فکر کردم دیدم اشتباه زدم
دیگه فرصت نشد بیام اصلاحش کنم.
بعضی اوقات دچار هنگیدگی خفن ضایع میشم