سلام بچه ها
دو تا سوال از ساختمان داده هستش که من درخت بازگشت اولی رو کامل رسم می کنم اما اینکه گفته مرتبه ش می شه Omega برام سواله ؟آخه من فکر می کردم که مرتبش O بزرگ می شه نه امگا!!!
دومی هم باز درخت رو رسم می کنم توی سیگما گرفتن و همین طور حل با جایگذاریش مشکل دارم ممنون می شم کمک کنید
درخت تون رو نمی تونم مشاهده کنم !؟
[attachment=16299]نمی دونم چی شد من عکس رو فک کردم ارسال کردم به هر حال ببخشید اینم از عکس
در سوال اول :
اگر قبول کنید که درخت مقادیر شما تا ارتفاع [tex]\lceil\: \log\: _{\frac{3}{2}}n\: \rceil[/tex] رشد کنه داریم [tex]cn\: n(Log\: \: _{\frac{3}{2}}n\: \: \: 1)[/tex] و این به صورت مجانبی برابر است با [tex]O(nlogn)[/tex]
در سوال دوم :
اگر درخت بازگشت رو رسم کنید به [tex]cn\: \: \sum_{i=0}^{\lceil\: \log\: n\: \rceil}(\frac{4}{2})^in\: =\: cn\: \: \sum_{i=0}^{\infty}n(2^n-1)[/tex] اما اگر با روش جایگذاری برید داریم : [tex]T(n)=4T(\frac{n}{2}) n\: =4^2T(\frac{n}{4}) n 2n=4^3T(\frac{n}{8}) n n 2n=...=4^nT(n-n) 1 \frac{1}{2} \frac{1}{4} .... n\: =\: O(4^n)[/tex]
(۲۹ خرداد ۱۳۹۳ ۱۱:۴۲ ب.ظ)Pakniat نوشته شده توسط: در سوال اول :
اگر قبول کنید که درخت مقادیر شما تا ارتفاع [tex]\lceil\: \log\: _{\frac{3}{2}}n\: \rceil[/tex] رشد کنه داریم [tex]cn\: n(Log\: \: _{\frac{3}{2}}n\: \: \: 1)[/tex] و این به صورت مجانبی برابر است با [tex]O(nlogn)[/tex]
در سوال دوم :
اگر درخت بازگشت رو رسم کنید به [tex]cn\: \: \sum_{i=0}^{\lceil\: \log\: n\: \rceil}(\frac{4}{2})^in\: =\: cn\: \: \sum_{i=0}^{\infty}n(2^n-1)[/tex] اما اگر با روش جایگذاری برید داریم : [tex]T(n)=4T(\frac{n}{2}) n\: =4^2T(\frac{n}{4}) n 2n=4^3T(\frac{n}{8}) n n 2n=...=4^nT(n-n) 1 \frac{1}{2} \frac{1}{4} .... n\: =\: O(4^n)[/tex]
من هم همین رو می گم ولی آخه برای سوال اول گفته که مرتبه امگا می شه نه O ؟؟؟یه سری سوالا تو کنکور هست که سوال دقیقا سر همین مساله هستش؟؟/