(۲۹ مهر ۱۳۹۱ ۰۴:۱۶ ب.ظ)roofia نوشته شده توسط: این معادله بازگشتی رو که مربو میشه به مرتب سازی ادغامی چه طوری باید اثباتش کنیم ؟
t(n)= 2t(n/2)+(n-1
(راهنماییش هم اینه:
n=2^k فرض کنیم.و بعد از یه سری محاسبات به این برسیم:
t(n)=O(nlog
)
کـــــــــــــــــــــــــــمکـــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــ!!!!!!!!!!!!!!!!!!!!!!!!
مرتب سازی ادغامی هر بار مجموعه داده شده رو تقریبا نصف می کنه، تا بجایی برسه که ادامه نصف کردن امکان پذیر نباشه.
پس چون هر بار مجموعه نصف میشه، به دو مجموعه تقسیم بندی میشه. (یعنی n ، به دو مجموعه n/2 تبدیل میشه).
پس تا اینجا ۲T(n/2 مشخص شد. اون n-1 که نوشتین زمان لازم برای مقایسه عناصر بوده که از مرتبه تتای n است.
حالا رابطه بازگشتی که شما نوشتین رو میشه راحت با قضیه اصلی بدست آورد. که جواب برابر تتای nlogn خواهد بود.