من اومدم از حد گرفتن و رسیدن به قضیه اصلی برم نشد. جاگذاری هم چون دو تا تابع هست سخته. با تغییر متغیر هم به ناهمگن خیلی پیچیده میشه. درختشم که نمیشه. سختههه و اصلا این طور مسائل رو ندیدم که با درخت حل کنن چون ضریبش غیر صحیح هست یه تابع.
خلاصه تنها راهی که میمونه قضیه ی بمب اتم هست که توی کتاب پوران توضیح دادن دکتر یوسفی
قضیه ی بمب اتم: رابطه ی بازگشتی [tex]T(n)=\Sigma_{i=1}^ka_iT(\frac{n}{b_i})+f(n)[/tex] که k عدد ثابت، [tex]a_{i\: }>0[/tex] ثابت و [tex]b_{i\: }>0[/tex] برای هر i ثابت هستند مفروض است. مرتبه ی این رابطه ی بازگشتی از فرمول زیر به دست می آید:
[tex]T(n)=\theta(n^p(1+\int_1^n\frac{f(x)}{x^{p+1}}\: dx))[/tex]
که p جواب منحصر به فرد معادله ی [tex]\Sigma_{i=1}^k(\frac{a_i}{b^p_i})=1[/tex] است.
خب توی این جا داریم:
[tex]a_1=2\: \: ,\: \: a_2=\frac{8}{9}[/tex] و
[tex]b_1=2\: \: ,\: \: b_2=\frac{4}{3}[/tex]
واسه پیدا کردن p طبق فرمول میریم، میشه : [tex]\frac{a_1}{b^p_1}+\frac{a_2}{b_2^p}=\frac{\: 2}{2^p}+\frac{(\frac{8}{9})}{(\frac{4}{3})^p}=1[/tex] که باید p رو از این رابطه در بیاریم. رابطه رو ساده تر می کنیم:
[tex]\frac{\: 2}{2^p}+\frac{(\frac{8}{9})}{(\frac{4}{3})^p}=(\frac{1}{2^{p-1}})+(\frac{2^3}{9}\cdot(\frac{3^p}{4^p}))=1[/tex] که باید اینو حلش کنیم.
اما چون حلش سخته عددگذاری میکنیم جای p. به ازای p=2 معادله ی بالا میشه برابر با ۱.
خب حالا طبق فرمولی که توی قضیه گفتیم :
[tex]T(n)=\: \theta(n^2(1+\int_1^n\frac{f(x)}{x^{p+1}}))=\theta(n^2(1+\int\frac{x^2}{\log x\times x^3}dx))[/tex]
واسه گرفتن انتگرال
می دونیم که [tex]f(u)'=u'\times f'(u)[/tex] توی اینجا [tex]u=\log x\: \: ،\: \: f(x)=\log x[/tex] و [tex]f(u)'=(\log(u))'=u'\times\log u=(\log x)'\times(\log(\log x))'=\frac{1}{xlog_2^2}\times\frac{1}{\log x\times\log_2^2}=\frac{1}{x}\times\frac{1}{\log x}[/tex]
در نهایت میشه :
[tex]T(n)=\: \theta(n^2(1+\int_1^n\frac{f(x)}{x^{p+1}}))=\theta(n^2(1+\int\frac{x^2}{\log x\times x^3}dx))=\theta(n^2(1+\log\log n))[/tex]
[tex]T(n)=\theta(n^2\log\log n)[/tex]

(۰۵ مهر ۱۳۹۵ ۱۱:۰۶ ب.ظ)Alirezaj نوشته شده توسط:  با سلام
حل این رابطه بازگشتی رو میخواستم (با درخت بازگشتی)
لطفا راهنمای کنید با تشکر
۲T(n/2)+8/9T(3n/4)+n^2/log n

سلام.با قضیه Akra-Bazzi (فک کنم بمب اتم هم بهش میگن) میشه این سوال رو حل کرد.(در پاسخ بالا هم در مورد این قضیه توضیح دادن)

اگر شکل کلی یک رابطه بازگشتی بصورت زیر باشه:

[tex]T(n)=\: \sum_{i=1}^ka_i\: T(\frac{n}{b_i})\: +f(n)[/tex]

k: یک عدد ثابت
[tex]a_i[/tex] و [tex]b_i[/tex] اعداد ثابت بزرگتر از صفر
f(n) از بالا و پایین به توابع چند جمله ای محدود میشه. [tex]n^c\: \le\: f(n)\: \: \le\: n^d\: \: ,\: c\succ0[/tex]

حال طبق قضیه Akra-Bazi(بمب اتم) در مورد مرتبه زمانی T(n) داریم:

که p رو میشه از رابطه زیر بدست آورد:

---------------------------------------------------------

حل این سوال:
ابتدا p رو محاسبه می‌کنیم:

سپس مرتبه زمانی T(n) رو محاسبه می‌کنیم:
پس جواب مسئله [tex]\: \theta(n^2\log\log n\: )[/tex] میشه.

--------------------------------------------

توضیحات:
جهت حل انتگرال [tex]\: \int\frac{1}{x\: \ln x}\: dx[/tex] میتونیم از تغییر متغیر استفاده کنیم.
[tex]u=\ln x[/tex]
[tex]du\: =\frac{\: 1}{x}\: dx[/tex]

پس با تغییر متغیر،انتگرال ما به انتگرال [tex]\int\frac{1}{u}du[/tex] تبدیل میشه که جوابش [tex]\ln\: u[/tex] میشه.
و چونکه u رو برابر [tex]\ln\: x[/tex] قرار داده بودیم،پس جواب نهایی انتگرال برابر [tex]\ln\: (\ln\: x)[/tex] میشه.