تالار گفتمان مانشت

با توجه به تابع بازگشتی زیر مرتبه زمان را بیابید:

(19 دى 1391 07:17 ب.ظ)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)
چرا ؟ چون تعداد فراخوانی ها از مرتبه خطی است.
اگه متوجه نشدین بگین دوباره بگم.

(19 دى 1391 11:28 ب.ظ)nazaninzahra2 نوشته شده توسط: [ -> ]میشه : O(n)
چرا ؟ چون تعداد فراخوانی ها از مرتبه خطی است.

موافقم

نقل قول: سلام
جواب شما اشتباه است لطفآ اصلاح بفرمائید. جواب خیلی آسونه ! میشه : O(n)
چرا ؟ چون تعداد فراخوانی ها از مرتبه خطی است.
اگه متوجه نشدین بگین دوباره بگم.

بله متوجه اشتباهم شدم.ممنون از تذکرتون.پست و حذف کردم.

لطفا بیشتر توضیح بدید.

(20 دى 1391 08:01 ب.ظ)egm1176 نوشته شده توسط: [ -> ]لطفا بیشتر توضیح بدید.

[tex]T(n)=T(n-3) \Theta (1) \leq T(n-1) \Theta (1)=\Theta (n)[/tex]

این سوال از اون سوالاتیه که در نگاه اول ممکنه اشتباه کنیم
من حدس میزنم این تست رو مثل فرضا (2T(n-1 در نظر گرفته اید که مرتبه اون نمایی میشه اما دقت کنید در این سوال مقدار عدد 2 که در تابع f ضرب میشه با اون 2یی که در T ضرب شده فرق داره چراکه اونی که در T ضرب شده می خواد بگه به ازای پارمتر درون پرانتزش این تابع 2 بار فراخوانی میشه اما اونی که در f ضرب شده یعنی حاصل تابع رو در عدد 2 ضرب کن ( نه 2 بار فراخوانی تابع ) . در ضمن اون nی که با f جمع شده یک عدد ثابت است که در مرتبه زمانی (O(1 محاسبه میشود . که این باز هم با T(n-1)+n فرق داره

در واقع این fی که اینجا اومده یه تابع هست اما T معرف یک رابطه بازگشتی هست که تعداد تکرار تابع رو نشون میده .

(21 دى 1391 01:19 ق.ظ)Masoud05 نوشته شده توسط: [ -> ]این سوال از اون سوالاتیه که در نگاه اول ممکنه اشتباه کنیم
من حدس میزنم این تست رو مثل فرضا (۲T(n-1 در نظر گرفته اید که مرتبه اون نمایی میشه اما دقت کنید در این سوال مقدار عدد ۲ که در تابع f ضرب میشه با اون ۲یی که در T ضرب شده فرق داره چراکه اونی که در T ضرب شده می خواد بگه به ازای پارمتر درون پرانتزش این تابع ۲ بار فراخوانی میشه اما اونی که در f ضرب شده یعنی حاصل تابع رو در عدد ۲ ضرب کن ( نه ۲ بار فراخوانی تابع ) . در ضمن اون nی که با f جمع شده یک عدد ثابت است که در مرتبه زمانی (O(1 محاسبه میشود . که این باز هم با T(n-1)+n فرق داره

در واقع این fی که اینجا اومده یه تابع هست اما T معرف یک رابطه بازگشتی هست که تعداد تکرار تابع رو نشون میده .

بله من دقیقا همون اشتباه و کردم.بعد که بچه ها تذکر دادن و دوباره نگاه کردم متوجه شدم.
ممنون از توضیحاتتون.
این نشون دهنده ی اهمیت دقت در موفقیته

(21 دى 1391 11:15 ق.ظ)mosaferkuchulu نوشته شده توسط: [ -> ]

(21 دى 1391 01:19 ق.ظ)Masoud05 نوشته شده توسط: [ -> ]این سوال از اون سوالاتیه که در نگاه اول ممکنه اشتباه کنیم
من حدس میزنم این تست رو مثل فرضا (۲T(n-1 در نظر گرفته اید که مرتبه اون نمایی میشه اما دقت کنید در این سوال مقدار عدد ۲ که در تابع f ضرب میشه با اون ۲یی که در T ضرب شده فرق داره چراکه اونی که در T ضرب شده می خواد بگه به ازای پارمتر درون پرانتزش این تابع ۲ بار فراخوانی میشه اما اونی که در f ضرب شده یعنی حاصل تابع رو در عدد ۲ ضرب کن ( نه ۲ بار فراخوانی تابع ) . در ضمن اون nی که با f جمع شده یک عدد ثابت است که در مرتبه زمانی (O(1 محاسبه میشود . که این باز هم با T(n-1)+n فرق داره

در واقع این fی که اینجا اومده یه تابع هست اما T معرف یک رابطه بازگشتی هست که تعداد تکرار تابع رو نشون میده .

بله من دقیقا همون اشتباه و کردم.بعد که بچه ها تذکر دادن و دوباره نگاه کردم متوجه شدم.
ممنون از توضیحاتتون.
این نشون دهنده ی اهمیت دقت در موفقیته

البته منظور من اصلا شما نبودید چون اصلا حواسم به ارسال شما نبود . اما یادمه سال قبل هم همین سوال مطرح شده بود و تو کتابخونه هم که درس میخوندم این سوال رو یه نفر دیگه هم ازم پرسیده بود و همه اشتباهات ناشی از یک سوء تفاهم در معنای عدد پشت تابع هست

بالاخره پیداش کردم : بیشتر منظورم ارسال شماره 8 هست

مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.