۰
subtitle
ارسال: #۱
  
سوال ۴۸ آزاد فناوری اطلاعات سال ۸۵
سلام دوستان می شه خواهش کنم گزینه ای که به نظرتون درست هست رو با دلیل برای من بگید؟
۰
ارسال: #۲
  
سوال ۴۸ ارشد آزاد ۸۵ گرایش فناوری اطلاعات
خیلی واضحه که جواب logn می شه در واقع زمان اجرا برابر است با
T(n)=T(n/2)+1 = o(logn)
T(n)=T(n/2)+1 = o(logn)
ارسال: #۳
  
RE: سوال ۴۸ ارشد آزاد ۸۵ گرایش فناوری اطلاعات
۱
ارسال: #۴
  
RE: سوال ۴۸ ارشد آزاد ۸۵ گرایش فناوری اطلاعات
فکر کنم اون [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]
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
(t(n/2)+t(n/2) =o(n) or o(2^lgn
ارسال: #۷
  
RE: سوال ۴۸ ارشد آزاد ۸۵ گرایش فناوری اطلاعات
(۱۳ اردیبهشت ۱۳۹۰ ۰۲:۵۱ ب.ظ)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]
Can I see some ID?
Feeling left out?
نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. رمزت رو فراموش کردی؟ اینجا به یادت میاریم! close