چرا اگر تعداد عناصر ارایه توانی از ۲ باشد
بدترین حالت و بهترین حالت تعداد مقایسات میشه
[tex]nlog(n) -n 1 , \frac{n}{2} logn[/tex]
شما باید رابطه بازگشتی مرتب سازی ادغامی رو در دو حالت بهترین و بدترین در نظر بگیرید(این دو تا رابطه بازگشتی تو همه کتابای طراحی الگوریتم هستش).طبیعتا وقتی هر دو رابطه بازگشتی رو حل کنید میرسید به این دو تا جواب.
(۱۲ آبان ۱۳۹۰ ۰۸:۳۶ ب.ظ)mfXpert نوشته شده توسط: شما باید رابطه بازگشتی مرتب سازی ادغامی رو در دو حالت بهترین و بدترین در نظر بگیرید(این دو تا رابطه بازگشتی تو همه کتابای طراحی الگوریتم هستش).طبیعتا وقتی هر دو رابطه بازگشتی رو حل کنید میرسید به این دو تا جواب.میشه رابطه بازگشتیشو بنویسید؟
حالت بدترین به صورت زیر هستش:
[tex]T(n)=2T(\frac{n}{2}) n-1[/tex]
و حالت بهترین هم به صورت زیر:
[tex]T(n)=2T(\frac{n}{2}) \frac{n}{2}[/tex]
هر دو رابطه بازگشتی دارای شرط اولیه زیر هستن:
[tex]T(1)=0[/tex]