انجمنصفحه اولجستجوی انجمن

[heni63]

سلام میشه محاسبه پیچیدگی تابع به روش درختی بگید ؟
T(n/3)=3t(n/9)+n/3

[arash691]

(۲۸ فروردین ۱۳۹۶ ۰۸:۵۰ ب.ظ)heni63 نوشته شده توسط:  سلام میشه محاسبه پیچیدگی تابع به روش درختی بگید ؟
T(n/3)=3t(n/9)+n/3

$\frac{n}{3}=m\: \: \: T(m)=3T(\frac{m}{3})+m\:$ برای این رابطه درخت بکشید حل کنید و سراخر تغییر متغیر اعمال شده رو در نظر بگیرید $\theta(mlogm)=\theta(\frac{n}{3}\log(\frac{n}{3}))$

درخت با ریشه m و در سطح بعدی ۳ فرزند هرکدام m/3 که مجموع هزینه ی آن بازهم m هست و در سطح بعدی ۹ فرزند هر کدام m/9 و ... ارتفاع درخت لگاریتم m در مبنای ۳ است