سلام وقت بخیر
در این مبحث در کتاب پارسه ۳ قضیه وجود داره حال چگونه با استفاده از این ۳ قضیه می توان مسائل رو حل کرد و رابطه بازگشتی رو بدست اورد برای مثال:
t(n)= 8t (n/9)+nlogn
t(n)= 2t (n/2)+logn!
ایا روش تستی برای حل وجود دارد؟
برای سوال اول :
چون : [tex]n\cdot\log\: n\: \in\: Omega(n^{\log\: _9^8})[/tex]
پس مرتبه زمانی سوال اول اینه:
[tex]T(n)=\: O(n\cdot\log\: n)[/tex]
برای سوال دوم:
چون : [tex]\log\: n\: \in\: O(n^{\log\: _2^2})\: \: \: or\: \: \log\: n\: \in\: O(n)[/tex]
پس [tex]T(n)=O(n)[/tex]