سلام میشه محاسبه پیچیدگی تابع به روش درختی بگید ؟
T(n/3)=3t(n/9)+n/3
(۲۸ فروردین ۱۳۹۶ ۰۸:۵۰ ب.ظ)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 و در سطح بعدی ۳ فرزند هرکدام m/3 که مجموع هزینه ی آن بازهم m هست و در سطح بعدی ۹ فرزند هر کدام m/9 و ... ارتفاع درخت لگاریتم m در مبنای ۳ است