سلام دوستان می شه خواهش کنم گزینه ای که به نظرتون درست هست رو با دلیل برای من بگید؟
فکر کنم اون [tex]\binom{n}{2}[/tex] نیست بلکه [tex]n/2[/tex] است و اشتباه تایپی بوده چون در غیراینصورت اصلا n=1 نمیشه و هر بار به جای اینکه کم بشه زیاد میشه.
n توانی از 2 است و باید اونقدر بر 2 تقسیم بشه تا به 1 برسه پس logn بار باید تابع اجرا بشه و گزینه 1 درسته.
مثلا n=8
[tex]f(8)\rightarrow f(4)\rightarrow f(2)\rightarrow f(1)\rightarrow return1[/tex]
که چهار بار اجرا شد یعنی [tex]log8 1[/tex]
بله منم میخاستم بگم صورت سوال اشتباهه
گزینه 2 جواب است تو کتاب مقسمی نوشت
(t(n/2)+t(n/2) =o(n) or o(2^lgn
(13 اردیبهشت 1390 02:51 ب.ظ)benaifur نوشته شده توسط: [ -> ]گزینه 2 جواب است تو کتاب مقسمی نوشت
(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]
خیلی واضحه که جواب logn می شه در واقع زمان اجرا برابر است با
T(n)=T(n/2)+1 = o(logn)
(14 اردیبهشت 1390 07:34 ب.ظ)khodam نوشته شده توسط: [ -> ]خیلی واضحه که جواب logn می شه در واقع زمان اجرا برابر است با
T(n)=T(n/2)+1 = o(logn)
مشکل من هم با سوالهای دانشگاه آزاد وضوح و سادگی نیست ... تا حالا این همه سوال غلط از نظر مفهومی از نظر شکلی از نظر تایپی یکجا ندیده بودم
