سلام
خوب دوست عزیزم بیا یکم این رابطه رو دست کاری کنیم ببینیم میتونیم به جواب برسیم ؟ اولین کارمون اینه که تغییر متغییر بدیم مثلآ بیا بجای [tex]n[/tex] بزاریم : [tex]3^k[/tex] پس رابطه ما اینجوری میشه :
[tex]T(3^k)=3T(3^{k-1}) \frac{3^k}{log(3^K))}[/tex]
در ضمن میدونیم که پایه لگاریتم تاثیری در مرتبه نداره پس من پایه رو ۳ در نظر میگیرم و این رابطه رو بازم ساده تر میکنم :
[tex]T(3^k)=3T(3^{k-1}) \frac{3^k}{k}[/tex]
خوب حالا بیا تغییر تابع بدهیم : یعنی بجای تابع [tex]T(3^k)[/tex] بزاریم : [tex]g(k)[/tex] در این صورت رابطه ما میشه :
[tex]g(k)=3g(k-1) \frac{3^k}{k}[/tex]
فکر کنم تا اینجا آسون بود. مگه نه ؟ خوب حالا بیا این رابطه رو با جایگذاری حل کنیم :
میدانیم که : [tex]g(2)=3g(1) \frac{3^2}{2}[/tex]
همچنین میدانیم : [tex]g(3)=3g(2) \frac{3^3}{3}[/tex]
و همنیطور : [tex]g(4)=3g(3) \frac{3^4}{4}[/tex] و در نهایت میدانیم که : [tex]g(5)=3g(4) \frac{3^5}{5}[/tex]
تا اینجا هم که تابلو بود. حالا بیا برای بدست آوردن مدل رابطه مثلآ [tex]g(5)[/tex] رو حساب کنیم :
[tex]g(5)=3[3[3[3g(1) \frac{3^2}{2}] \frac{3^3}{3}] \frac{3^4}{4}] \frac{3^5}{5}=3^4 \frac{3^5}{2} \frac{3^5}{3} \frac{3^5}{4} \frac{3^5}{5}[/tex]
از این حدس میزنم که رابطه این مدلیه که : [tex]g(k)=3[3[3\cdots [3g(1) \frac{3^2}{2}] \frac{3^3}{3}] \frac{3^4}{4}] \cdots \frac{3^k}{k}=3^{k-1} \frac{3^k}{2} \frac{3^k}{3} \frac{3^k}{4} \cdots \frac{3^k}{k}[/tex]
و با کمی ساده سازی میفههم که :
[tex]g(k)=3^{k-1} \frac{3^k}{2} \frac{3^k}{3} \frac{3^k}{4} \cdots \frac{3^k}{k}=3^{k-1} 3^k(\frac{1}{2} \frac{1}{3} \frac{1}{4} \cdots \frac{1}{k})=[tex]g(k)\approx O(3^k(ln(k)))[/tex]
[/tex]
در نتیجه میتوان گفت که :[tex]g(k)\approx O(3^k(ln(k)))[/tex]
حال تغییر تابع رو برمیگردونیم و داریم : [tex]T(3^k)\approx O(3^k(ln(k)))[/tex]
و حال تغییر متغییر رو برمیگردونیم و داریم : [tex]T(n)\approx O(nloglog(n)) = O(nlog^2(n))[/tex]

سعی کردم آسون بگم.
موفق باشی.