سلام دوستان می شه خواهش کنم گزینه ای که به نظرتون درست هست رو با دلیل برای من بگید؟
فکر کنم اون [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 نوشته شده توسط: گزینه ۲ جواب است تو کتاب مقسمی نوشتنه اگر [tex]f(n/2) f(n/2)[/tex]
(t(n/2)+t(n/2) =o(n) or o(2^lgn
رو داشتیم حرف شما درست بود چون تابع درختی میشد شبیه فیبوناچی
اما حالا [tex]f(n/2) n/2[/tex]
داریم که میشه.
[tex]T(n)=T(n/2)[/tex]
[tex]O(logn)[/tex]
خیلی واضحه که جواب logn می شه در واقع زمان اجرا برابر است با
T(n)=T(n/2)+1 = o(logn)
(۱۴ اردیبهشت ۱۳۹۰ ۰۷:۳۴ ب.ظ)khodam نوشته شده توسط: خیلی واضحه که جواب logn می شه در واقع زمان اجرا برابر است با
T(n)=T(n/2)+1 = o(logn)
مشکل من هم با سوالهای دانشگاه آزاد وضوح و سادگی نیست ... تا حالا این همه سوال غلط از نظر مفهومی از نظر شکلی از نظر تایپی یکجا ندیده بودم
