با عرض سلام.
کدامیک از این روابط نمیتوانند بیان کننده یک رابطه بازگشتی باشند؟چرا؟
الف)[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 استفاده نمایید. این سوال ویرایش شد.
فکر کنم الف چون - داره
آخه اینجوری که مرتبه کل هم منفی میشه!!!!
فکر کنم د
چون t(n/2 ضریبش ثابت نیست و به n بستگی داره
معذرت میخوام.فراموش کردم که عرض کنم گزینه صحیح گزینه ۱ هستش که البته چون دلیلشو نمیدونستم سوالو مطرح کردم
گزینه الف رو میشه بخاطر - رد کرد(از قول افاق)
گرینه د هم داره دوبار لگاریتم میگیره و نمیشه گفت داره n/2 رو خنثی میکنه
بنظرم فقط الف، اگه جای (O(n مقدار n بود اونوقت این گزینه هم صحیح میشد اما برای مورد د هیچ منعی به نظرم نمیاد و صحبت مریم خانم فکر کنم غلطه چون خیلی از روابط داخلشون یه ضریب غیر ثابت هست . منظور آقا جواد رو هم نمیدونم چیه ولی به احتمال قوی گزینه د مشکلی نداره
اما درباره گزینه الف حرف آفاق خانم درسته اما با کمی تغییر بیان . در واقع علامت منها یعنی هر بار تابع مجدد فراخونی میشه یه بخش از هزینه اش کم میشه . اگه به فرمولی که در بخش نکات تقسیم و غلبه راجع بهش صحبت کردیم دقت کنید این مقداری که کسر میشه همون زمان ترکیب مسئله هست!!!
(۲۳ دى ۱۳۸۹ ۱۱:۱۸ ب.ظ)Masoud05 نوشته شده توسط: بنظرم فقط الف، اگه جای (O(n مقدار n بود اونوقت این گزینه هم صحیح میشد اما برای مورد د هیچ منعی به نظرم نمیاد و صحبت مریم خانم فکر کنم غلطه چون خیلی از روابط داخلشون یه ضریب غیر ثابت هست . منظور آقا جواد رو هم نمیدونم چیه ولی به احتمال قوی گزینه د مشکلی ندارهاره من هرجور چک کردم گزینه د مشکلی نداره به نظرم دوستان تهرانی اگه به یک استاد خوب دسترسی دارند این سوال ببرند حتما دلیل گزینه اول رو بپرسند