۰
subtitle
ارسال: #۱
کدامیک از روابط زیر نمیتوانند بیان کننده یک رابطه بازگشتی باشند؟
با عرض سلام.
کدامیک از این روابط نمیتوانند بیان کننده یک رابطه بازگشتی باشند؟چرا؟
الف)[tex]T(n)=T(n-1) - O(n)[/tex]
ب)[tex]T(n)=4*T(n-1) \Theta (n^2)[/tex]
ج)[tex]T(n)=T(n-1) T(n-2) O(n)[/tex]
د)[tex]T(n)=log(log(n)) T(\frac{n}{2}) O(1)[/tex]
پیغام admin: از این به بعد برای نوشتن فرمول‍ها از TeX استفاده نمایید. این سوال ویرایش شد.
کدامیک از این روابط نمیتوانند بیان کننده یک رابطه بازگشتی باشند؟چرا؟
الف)[tex]T(n)=T(n-1) - O(n)[/tex]
ب)[tex]T(n)=4*T(n-1) \Theta (n^2)[/tex]
ج)[tex]T(n)=T(n-1) T(n-2) O(n)[/tex]
د)[tex]T(n)=log(log(n)) T(\frac{n}{2}) O(1)[/tex]
پیغام admin: از این به بعد برای نوشتن فرمول‍ها از TeX استفاده نمایید. این سوال ویرایش شد.
۰
ارسال: #۲
RE: کدامیک از روابط زیر نمیتوانند بیان کننده یک رابطه بازگشتی باشند؟
بنظرم فقط الف، اگه جای (O(n مقدار n بود اونوقت این گزینه هم صحیح میشد اما برای مورد د هیچ منعی به نظرم نمیاد و صحبت مریم خانم فکر کنم غلطه چون خیلی از روابط داخلشون یه ضریب غیر ثابت هست . منظور آقا جواد رو هم نمیدونم چیه ولی به احتمال قوی گزینه د مشکلی نداره
اما درباره گزینه الف حرف آفاق خانم درسته اما با کمی تغییر بیان . در واقع علامت منها یعنی هر بار تابع مجدد فراخونی میشه یه بخش از هزینه اش کم میشه . اگه به فرمولی که در بخش نکات تقسیم و غلبه راجع بهش صحبت کردیم دقت کنید این مقداری که کسر میشه همون زمان ترکیب مسئله هست!!!
اما درباره گزینه الف حرف آفاق خانم درسته اما با کمی تغییر بیان . در واقع علامت منها یعنی هر بار تابع مجدد فراخونی میشه یه بخش از هزینه اش کم میشه . اگه به فرمولی که در بخش نکات تقسیم و غلبه راجع بهش صحبت کردیم دقت کنید این مقداری که کسر میشه همون زمان ترکیب مسئله هست!!!
ارسال: #۳
RE: کدامیک از روابط زیر نمیتوانند بیان کننده یک رابطه بازگشتی باشند؟
(۲۳ دى ۱۳۸۹ ۱۱:۱۸ ب.ظ)Masoud05 نوشته شده توسط: بنظرم فقط الف، اگه جای (O(n مقدار n بود اونوقت این گزینه هم صحیح میشد اما برای مورد د هیچ منعی به نظرم نمیاد و صحبت مریم خانم فکر کنم غلطه چون خیلی از روابط داخلشون یه ضریب غیر ثابت هست . منظور آقا جواد رو هم نمیدونم چیه ولی به احتمال قوی گزینه د مشکلی ندارهاره من هرجور چک کردم گزینه د مشکلی نداره به نظرم دوستان تهرانی اگه به یک استاد خوب دسترسی دارند این سوال ببرند حتما دلیل گزینه اول رو بپرسند
۰
ارسال: #۴
کدامیک از روابط زیر نمیتوانند بیان کننده یک رابطه بازگشتی باشند؟
فکر کنم الف چون - داره 
آخه اینجوری که مرتبه کل هم منفی میشه!!!!
آخه اینجوری که مرتبه کل هم منفی میشه!!!!
۰
ارسال: #۵
کدامیک از روابط زیر نمیتوانند بیان کننده یک رابطه بازگشتی باشند؟
فکر کنم د
چون t(n/2 ضریبش ثابت نیست و به n بستگی داره
چون t(n/2 ضریبش ثابت نیست و به n بستگی داره
۰
ارسال: #۶
RE: کدامیک از روابط زیر نمیتوانند بیان کننده یک رابطه بازگشتی باشند؟
معذرت میخوام.فراموش کردم که عرض کنم گزینه صحیح گزینه ۱ هستش که البته چون دلیلشو نمیدونستم سوالو مطرح کردم
۰
ارسال: #۷
کدامیک از روابط زیر نمیتوانند بیان کننده یک رابطه بازگشتی باشند؟
گزینه الف رو میشه بخاطر - رد کرد(از قول افاق)
گرینه د هم داره دوبار لگاریتم میگیره و نمیشه گفت داره n/2 رو خنثی میکنه
گرینه د هم داره دوبار لگاریتم میگیره و نمیشه گفت داره n/2 رو خنثی میکنه
Can I see some ID?
Feeling left out?
نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. رمزت رو فراموش کردی؟ اینجا به یادت میاریم! close