با توجه به تابع بازگشتی زیر مرتبه زمان را بیابید:
![[تصویر: 153086_1_1379086621.png]](https://img.manesht.ir/153086_1_1379086621.png)
(۱۹ دى ۱۳۹۱ ۰۷:۱۷ ب.ظ)mosaferkuchulu نوشته شده توسط: [tex]f(n)=2f(n-3) n[/tex]
[tex]2(2f(n-6) (n-3)) n =4f(n-6) 2(n-3) n[/tex]
[tex]=4(2 f(n-9) (n-6)) 2(n-3) n[/tex]
[tex]=8f(n-9) 4(n-6) 2(n-3) n[/tex]
[tex]=2^{3}f(n-9) 2^{2}(n-6) 2^{1}(n-3) n[/tex]
...
اگر همینطور ادامه بدیم تعداد n/3 جمله به دست می اد و جواب می شه:
[tex]\frac{2^{\frac{n}{3}}-1}{2-1}= O(2^{\frac{n}{3}})[/tex]
سلام
جواب شما اشتباه است لطفآ اصلاح بفرمائید. جواب خیلی آسونه ! میشه : O(n)
چرا ؟ چون تعداد فراخوانی ها از مرتبه خطی است.
اگه متوجه نشدین بگین دوباره بگم.
(۱۹ دى ۱۳۹۱ ۱۱:۲۸ ب.ظ)nazaninzahra2 نوشته شده توسط: میشه : O(n)موافقم
چرا ؟ چون تعداد فراخوانی ها از مرتبه خطی است.
نقل قول: سلام
جواب شما اشتباه است لطفآ اصلاح بفرمائید. جواب خیلی آسونه ! میشه : O(n)
چرا ؟ چون تعداد فراخوانی ها از مرتبه خطی است.
اگه متوجه نشدین بگین دوباره بگم.
بله متوجه اشتباهم شدم.ممنون از تذکرتون.پست و حذف کردم.
لطفا بیشتر توضیح بدید.
(۲۰ دى ۱۳۹۱ ۰۸:۰۱ ب.ظ)egm1176 نوشته شده توسط: لطفا بیشتر توضیح بدید.[tex]T(n)=T(n-3) \Theta (1) \leq T(n-1) \Theta (1)=\Theta (n)[/tex]
این سوال از اون سوالاتیه که در نگاه اول ممکنه اشتباه کنیم
من حدس میزنم این تست رو مثل فرضا (۲T(n-1 در نظر گرفته اید که مرتبه اون نمایی میشه اما دقت کنید در این سوال مقدار عدد ۲ که در تابع f ضرب میشه با اون ۲یی که در T ضرب شده فرق داره چراکه اونی که در T ضرب شده می خواد بگه به ازای پارمتر درون پرانتزش این تابع ۲ بار فراخوانی میشه اما اونی که در f ضرب شده یعنی حاصل تابع رو در عدد ۲ ضرب کن ( نه ۲ بار فراخوانی تابع ) . در ضمن اون nی که با f جمع شده یک عدد ثابت است که در مرتبه زمانی (O(1 محاسبه میشود . که این باز هم با T(n-1)+n فرق داره
در واقع این fی که اینجا اومده یه تابع هست اما T معرف یک رابطه بازگشتی هست که تعداد تکرار تابع رو نشون میده .
(۲۱ دى ۱۳۹۱ ۰۱:۱۹ ق.ظ)Masoud05 نوشته شده توسط: این سوال از اون سوالاتیه که در نگاه اول ممکنه اشتباه کنیم
من حدس میزنم این تست رو مثل فرضا (۲T(n-1 در نظر گرفته اید که مرتبه اون نمایی میشه اما دقت کنید در این سوال مقدار عدد ۲ که در تابع f ضرب میشه با اون ۲یی که در T ضرب شده فرق داره چراکه اونی که در T ضرب شده می خواد بگه به ازای پارمتر درون پرانتزش این تابع ۲ بار فراخوانی میشه اما اونی که در f ضرب شده یعنی حاصل تابع رو در عدد ۲ ضرب کن ( نه ۲ بار فراخوانی تابع ) . در ضمن اون nی که با f جمع شده یک عدد ثابت است که در مرتبه زمانی (O(1 محاسبه میشود . که این باز هم با T(n-1)+n فرق داره
در واقع این fی که اینجا اومده یه تابع هست اما T معرف یک رابطه بازگشتی هست که تعداد تکرار تابع رو نشون میده .
بله من دقیقا همون اشتباه و کردم.بعد که بچه ها تذکر دادن و دوباره نگاه کردم متوجه شدم.
ممنون از توضیحاتتون.
این نشون دهنده ی اهمیت دقت در موفقیته
(۲۱ دى ۱۳۹۱ ۱۱:۱۵ ق.ظ)mosaferkuchulu نوشته شده توسط:(21 دى ۱۳۹۱ ۰۱:۱۹ ق.ظ)Masoud05 نوشته شده توسط: این سوال از اون سوالاتیه که در نگاه اول ممکنه اشتباه کنیم
من حدس میزنم این تست رو مثل فرضا (۲T(n-1 در نظر گرفته اید که مرتبه اون نمایی میشه اما دقت کنید در این سوال مقدار عدد ۲ که در تابع f ضرب میشه با اون ۲یی که در T ضرب شده فرق داره چراکه اونی که در T ضرب شده می خواد بگه به ازای پارمتر درون پرانتزش این تابع ۲ بار فراخوانی میشه اما اونی که در f ضرب شده یعنی حاصل تابع رو در عدد ۲ ضرب کن ( نه ۲ بار فراخوانی تابع ) . در ضمن اون nی که با f جمع شده یک عدد ثابت است که در مرتبه زمانی (O(1 محاسبه میشود . که این باز هم با T(n-1)+n فرق داره
در واقع این fی که اینجا اومده یه تابع هست اما T معرف یک رابطه بازگشتی هست که تعداد تکرار تابع رو نشون میده .
بله من دقیقا همون اشتباه و کردم.بعد که بچه ها تذکر دادن و دوباره نگاه کردم متوجه شدم.
ممنون از توضیحاتتون.
این نشون دهنده ی اهمیت دقت در موفقیته
البته منظور من اصلا شما نبودید چون اصلا حواسم به ارسال شما نبود . اما یادمه سال قبل هم همین سوال مطرح شده بود و تو کتابخونه هم که درس میخوندم این سوال رو یه نفر دیگه هم ازم پرسیده بود و همه اشتباهات ناشی از یک سوء تفاهم در معنای عدد پشت تابع هست
بالاخره پیداش کردم
: بیشتر منظورم ارسال شماره ۸ هست مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.