حالت پیشرفته مستره!همون CLRS درسته!

خیلی ممنونم

قضیه ی master اینه :

مثالی از یک حالت خاص :
[tex]T(n)= 2T(n/2) lgn![/tex]
ببین سمت چپ میشه n به توان لگاریتم ۲ در مبنای ۲ که جواب میشه teta_n
سمت راست هم میشه : teta_nLgn
----
در اینجا حالت خاص رو داریم :
اینجا چون f(n در [tex]lg^k(n)[/tex] ضرب شده ابتدا [tex]lg^k(n)[/tex] رو حذف کن میشه:
سمت چپ میشه o_n
سمت راست هم میشه o_n
چون مساوی شدن پس سمت راست یعنی f(n) رو lgn ضرب می کنی میشه nlgn
---
حالا اون چیزی که حذف کرده بودیم یعنی [tex]lg^k(n)[/tex] رو دوباره درش ضرب کن میشه :
[tex]nlg^{k 1}(n)[/tex]
[tex]nlg^{2}(n)[/tex]
---------
در حالت کلی یک حالت داریم به اسم حالت تعمیم:
[tex]t(n)=aT(\frac{n}{b}) f(n)[/tex]
اگر در روش قضیه ی اصلی داشته باشیم :
[tex]f(n)\varepsilon \theta(n^{log_{b}^{a}})lg^k{n}[/tex]
و k>=0 باشد داریم:
[tex]T(n)\varepsilon \theta(n^{log_{b}^{a}})lg^{k 1}{n}[/tex]
----------------------
مثال :
[tex]T(n)=2t(n/2) nlgn=\theta(nlg^2n)[/tex]
مثال بعدی:
[tex]T(n)=4t(n/2) n^2lgn=\theta(n^2lg^2n)[/tex]
-----------------------
اینم حل سوال شما:
[tex]t(n)=4t(n/2) nlg(n!)=4t(n/2) n^2 lgn=\theta(n^2lg^2n)[/tex]

شبیهشو اینجا حل کردم :

مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.