(۱۴ اردیبهشت ۱۳۹۰ ۰۷:۳۴ ب.ظ)khodam نوشته شده توسط:  خیلی واضحه که جواب logn می شه در واقع زمان اجرا برابر است با
T(n)=T(n/2)+1 = o(logn)

مشکل من هم با سوالهای دانشگاه آزاد وضوح و سادگی نیست ... تا حالا این همه سوال غلط از نظر مفهومی از نظر شکلی از نظر تایپی یکجا ندیده بودم

فکر کنم اون [tex]\binom{n}{2}[/tex] نیست بلکه [tex]n/2[/tex] است و اشتباه تایپی بوده چون در غیراینصورت اصلا n=1 نمیشه و هر بار به جای اینکه کم بشه زیاد میشه.

n توانی از ۲ است و باید اونقدر بر ۲ تقسیم بشه تا به ۱ برسه پس logn بار باید تابع اجرا بشه و گزینه ۱ درسته.

مثلا n=8

[tex]f(8)\rightarrow f(4)\rightarrow f(2)\rightarrow f(1)\rightarrow return1[/tex]

که چهار بار اجرا شد یعنی [tex]log8 1[/tex]

بله منم میخاستم بگم صورت سوال اشتباهه

گزینه ۲ جواب است تو کتاب مقسمی نوشت
(t(n/2)+t(n/2) =o(n) or o(2^lgn

(۱۳ اردیبهشت ۱۳۹۰ ۰۲:۵۱ ب.ظ)benaifur نوشته شده توسط:  گزینه ۲ جواب است تو کتاب مقسمی نوشت
(t(n/2)+t(n/2) =o(n) or o(2^lgn

نه اگر [tex]f(n/2) f(n/2)[/tex]

رو داشتیم حرف شما درست بود چون تابع درختی میشد شبیه فیبوناچی
اما حالا [tex]f(n/2) n/2[/tex]
داریم که میشه.
[tex]T(n)=T(n/2)[/tex]
[tex]O(logn)[/tex]