(۱۶ آذر ۱۳۹۲ ۱۰:۰۱ ب.ظ)tarane1992 نوشته شده توسط:  سلام

دوستان عزیز این سوالو برام توضیح بدین.

جواب گزینه ۱ هست.

سوال من اینه تعداد مقایسه در mergsort خوب p+m_1 هست حالا اگه من n رو مثلا ۸ بگیرم بخوام تعداد مقایسه ها رو بدونم چنده هر بار که آرایه رو تقسیم میکنم باید فرمول بالا رو توش به کار ببرم و نهایت همه رو در هر سطح با هم جمع کنم کلا میشه جواب؟مشکل من اینه نمیدونم چطوری باید از فرمول استفاده کنم ؟

بهم بگید من چه چیزی رو اشتباه میکنم راه حل اصلی چطوریه؟



مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.

سلام

فرض میکنیم n=4. پس در مرحله اول به دو دسته ۲ عنصری تقسیم میشود قبل از اینکه به پایین رویم همینجا میتوانیم تعداد مقایسه ها را در بدترین حالت برای مرحله اول بدانیم که میشود ۳ = ۱-۲+۲/
در مرحله دوم هر دسته ۲ تایی به دو دسته یک عنصری تقسیم میشود که برای هر یک میشود ۱=۱-۱+۱ که دو دسته هست و در مجموع میشود ۲ مقایسه.
درکل مجموع مرحله اول و دوم میشود ۵=۲+۳ که برابرست با تعداد مقایسات در بدترین حالت این الگوریتم با ۴=n.
در میان گزینه ها برای ۴=n میتوان بدون به دست اوردن فرمول کلی جواب را پیدا کرد.

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

موفق باشید.