(۲۷ مهر ۱۳۹۰ ۰۸:۱۵ ب.ظ)پشتکار نوشته شده توسط:  [tex]T(n)=\left\{\begin{matrix} 1&n=1 \\ 2T(\frac{n}{4}) logn & else \end{matrix}\right.[/tex]


۱) [tex]O(\sqrt{n})[/tex]

۲) [tex]O(logn)[/tex]

۳) [tex]O(\sqrt{n}-logn)[/tex]

۴) [tex]O(n)[/tex]

طبق قضیه Master گزینه ۱ درست است
log n<n^(log2 dar mabna 4
log 2 dar mabna 4)=n^1/2

به نظرم گزینه‌ی دو درسته. درخت رو بکشین می شه:



کدوم گزینه ست جواب؟

من اینطوری حل کردم

[tex]g(n)=n^{log_{b}^{a}}=n^{log_{4}^{2}}=n^{\frac{1}{log_{2}^{4}}}=n^{\frac{1}{2}}[/tex]


[tex]f(n)=logn[/tex]

G>F
پس داریم:
[tex]T(n)=g(n)=\sqrt{n}[/tex]

پس جواب یک صحیحه ولی پارسه گفته جواب ۴

کجای راه حلم اشتباهه؟؟؟

طبق قضیه اصلی جواب صحیح گزینه یک هستش.
فکر می کنم که با درخت هم قابل حله.

فکر نمی کنم این سوال نکته خاصی داشته باشه و اگر با استفاده از قضیه اصلی حل کنید گزینه یک میشه

آره سوال خیلی ساده هست ولی میخواستم مطمئن شم که درست رفتم
آخه پارسه جواب اشتباه داده بود
چندتا سوال دیگه هم همینطوری جواب اشتباه داده...
وقت کردم همشونو می ذارم
متشکرم

می شه یکی از دوستان درخت رو بکشن. بعد از کشیدن درخت اینطوری نمی شه؟