۰
subtitle
ارسال: #۱
سوال طراحی الگوریتم از پوران (محاسبه زمان اجرای الگوریتم بازگشتی)
با سلام
تابع بازگشتی زیر داده شده و می خواهیم زمان اجرای تابع رو بدست بیاریم.
(f(int n
if(n<=1) return n
return f(n-3)+f(n-3)+ n
جوابش:
T(n)=T(n-3) + T(n-3) + 1
می خوام بدونم که اینجا ما چه چیزی رو داریم می شماریم ؟ اگه داریم تعداد جمع ها رو می شماریم چرا به جای ۱، ۲ نیست چون تعداد جمع ها ۲ هست.
تابع بازگشتی زیر داده شده و می خواهیم زمان اجرای تابع رو بدست بیاریم.
(f(int n
if(n<=1) return n
return f(n-3)+f(n-3)+ n
جوابش:
T(n)=T(n-3) + T(n-3) + 1
می خوام بدونم که اینجا ما چه چیزی رو داریم می شماریم ؟ اگه داریم تعداد جمع ها رو می شماریم چرا به جای ۱، ۲ نیست چون تعداد جمع ها ۲ هست.
۰
ارسال: #۲
RE: سوال طراحی الگوریتم از پوران (محاسبه زمان اجرای الگوریتم بازگشتی)
من فکر میکنم اینجا باید تعداد فراخوانیهای تابع را بشماریم.
یعنی تعداد دفعاتی که f صدا زده میشود که برابر است با تعداد فراخوانیهایی که برای محاسبه f(n-3) نیاز هست ضربدر دو + یکباری که خود f(n) صدا زده شده است:
[tex]T(n)=2T(n-3) 1[/tex]
یعنی تعداد دفعاتی که f صدا زده میشود که برابر است با تعداد فراخوانیهایی که برای محاسبه f(n-3) نیاز هست ضربدر دو + یکباری که خود f(n) صدا زده شده است:
[tex]T(n)=2T(n-3) 1[/tex]
ارسال: #۳
RE: سوال طراحی الگوریتم از پوران (محاسبه زمان اجرای الگوریتم بازگشتی)
(۰۴ مرداد ۱۳۹۱ ۰۵:۳۹ ب.ظ)GCC نوشته شده توسط: من فکر میکنم اینجا باید تعداد فراخوانیهای تابع را بشماریم.
یعنی تعداد دفعاتی که f صدا زده میشود که برابر است با تعداد فراخوانیهایی که برای محاسبه f(n-3) نیاز هست ضربدر دو + یکباری که خود f(n) صدا زده شده است:
[tex]T(n)=2T(n-3) 1[/tex]
اگه تعداد فراخوانی ها باشه درسته، ولی توی جوابش آورده که اگر T(n) زمان اجرای تابع فرض شود جواب این میشه.
Can I see some ID?
Feeling left out?
نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. رمزت رو فراموش کردی؟ اینجا به یادت میاریم! close