28 فروردین 1396, 08:50 ب.ظ
28 فروردین 1396, 11:55 ب.ظ
(28 فروردین 1396 08:50 ب.ظ)heni63 نوشته شده توسط: [ -> ]سلام میشه محاسبه پیچیدگی تابع به روش درختی بگید ؟
T(n/3)=3t(n/9)+n/3
[tex]\frac{n}{3}=m\: \: \: T(m)=3T(\frac{m}{3})+m\: [/tex] برای این رابطه درخت بکشید حل کنید و سراخر تغییر متغیر اعمال شده رو در نظر بگیرید [tex]\theta(mlogm)=\theta(\frac{n}{3}\log(\frac{n}{3}))[/tex]
درخت با ریشه m و در سطح بعدی 3 فرزند هرکدام m/3 که مجموع هزینه ی آن بازهم m هست و در سطح بعدی 9 فرزند هر کدام m/9 و ... ارتفاع درخت لگاریتم m در مبنای 3 است