(۱۶ دى ۱۳۹۶ ۱۲:۵۷ ب.ظ)jumper نوشته شده توسط: [quote='msour44' pid='450130' dateline='1515157446']
خیلیییی ممنون
حالا برای T(n)=T(n/2)T(2n/3)n هزینه ی سطح i میشه (76)i
پس در نهایت هزینه کلی چطور محاسبه میشه؟
T(n)=n(1+(76)+(76)2+...(76)log32n)=n(6((\frac76)log32n−۱))=?
سوال شما درست نمایش داده نمی شود حداقل برای من لطفا تصحیح کنید. در رابطه ی جدیدی که شما نوشتید احتمالا به صورت
T(n)=T(n2)+T(2n3)+n باشه. در این حالت باید دقت کنیم که درخت بازگشتی درخت پر نیست یعنی تمام برگ ها که نقطه ی پایان بازگشتی هستند در یک سطح نیستند مثلا شاخه سمت چپ(n/2) سریعتر به نقطه پایانی می رسد تا شاخه سمت راست درخت (۲n/3) . پس تا شاخه سمت چپ یک هزینه ی حداقلی بدست می اید (همان
Ω) و اگر درخت را تا عمق شاخه سمت راستی پر فرض کنیم هزینه ی حداکثری بدست می اید (همان
O). برای شاخه ی سمت چپی n دائم بر ۲ تقسیم می شود پس سطح (i)را در ساده ترین حالت
log2n میگیرم و در شاخه سمت راست تا سطح
log32n در نظر می گیریم همان که شما رابطه ی ان را نوشتید. به نظر میاد در پیدا کردن مرتبه برای این رابطه نیاز به محا سبات لگاریتمی داریم .حالا باز شما رابطه تصحیح بفرماید یا بهتر این رابطه را به صورت سوال جداگانه مطرح کنید تا توسط دوستان پاسخ داده شود.