با سلام
تابع بازگشتی زیر داده شده و می خواهیم زمان اجرای تابع رو بدست بیاریم.
(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 صدا زده میشود که برابر است با تعداد فراخوانیهایی که برای محاسبه f(n-3) نیاز هست ضربدر دو + یکباری که خود f(n) صدا زده شده است:
[tex]T(n)=2T(n-3) 1[/tex]
(۰۴ مرداد ۱۳۹۱ ۰۵:۳۹ ب.ظ)GCC نوشته شده توسط: من فکر میکنم اینجا باید تعداد فراخوانیهای تابع را بشماریم.
یعنی تعداد دفعاتی که f صدا زده میشود که برابر است با تعداد فراخوانیهایی که برای محاسبه f(n-3) نیاز هست ضربدر دو + یکباری که خود f(n) صدا زده شده است:
[tex]T(n)=2T(n-3) 1[/tex]
اگه تعداد فراخوانی ها باشه درسته، ولی توی جوابش آورده که اگر T(n) زمان اجرای تابع فرض شود جواب این میشه.
(۰۴ مرداد ۱۳۹۱ ۰۶:۰۱ ب.ظ)maryam_ak نوشته شده توسط:(04 مرداد ۱۳۹۱ ۰۵:۳۹ ب.ظ)GCC نوشته شده توسط: من فکر میکنم اینجا باید تعداد فراخوانیهای تابع را بشماریم.
یعنی تعداد دفعاتی که f صدا زده میشود که برابر است با تعداد فراخوانیهایی که برای محاسبه f(n-3) نیاز هست ضربدر دو + یکباری که خود f(n) صدا زده شده است:
[tex]T(n)=2T(n-3) 1[/tex]
اگه تعداد فراخوانی ها باشه درسته، ولی توی جوابش آورده که اگر T(n) زمان اجرای تابع فرض شود جواب این میشه.
ببینید ما در محاسبه پیچیدگی یه الگوریتم معیارمون باید مشخص باشه مثلا بگیم : " منظور از هزینه همان تعداد فراخوانی هاست" یا "منظور از هزینه تعداد جمع های انجام شده است" و ... تا اینجا اوکی ؟ ولی بعضی وقت ها دنبال مقدار تایع هستیم که این مقدار تایع با هزینه تابع ممکنه یکی باشه ممکنه یکی نباشه !
در این تابع که شما گفتین مقدار تابع از حل این معادله بدست می آید : [tex]T(n)=T(n-3) T(n-3) n[/tex]
هزینه تابع در صورتی که تعداد فراخوانی مورد نظر باشد (که معمولا در اکثر مواقع اگه نگن منظور همینه) میشود :
[tex]T(n)=T(n-3) T(n-3) 1=2T(n-3) 1[/tex]
(۰۸ مرداد ۱۳۹۲ ۰۳:۴۲ ب.ظ)vojoudi نوشته شده توسط: ببینید ما در محاسبه پیچیدگی یه الگوریتم معیارمون باید مشخص باشه مثلا بگیم : " منظور از هزینه همان تعداد فراخوانی هاست" یا "منظور از هزینه تعداد جمع های انجام شده است" و ... تا اینجا اوکی ؟ ولی بعضی وقت ها دنبال مقدار تایع هستیم که این مقدار تایع با هزینه تابع ممکنه یکی باشه ممکنه یکی نباشه !
در این تابع که شما گفتین مقدار تابع از حل این معادله بدست می آید : [tex]T(n)=T(n-3) T(n-3) n[/tex]
هزینه تابع در صورتی که تعداد فراخوانی مورد نظر باشد (که معمولا در اکثر مواقع اگه نگن منظور همینه) میشود :
[tex]T(n)=T(n-3) T(n-3) 1=2T(n-3) 1[/tex]
نه این استدلال غلطه
چون اگه n+ هم نداشتیم جوابمون با الان فرقی نداشت!
(۰۸ مرداد ۱۳۹۲ ۰۶:۵۸ ب.ظ)mohsen f نوشته شده توسط:(08 مرداد ۱۳۹۲ ۰۳:۴۲ ب.ظ)vojoudi نوشته شده توسط: ببینید ما در محاسبه پیچیدگی یه الگوریتم معیارمون باید مشخص باشه مثلا بگیم : " منظور از هزینه همان تعداد فراخوانی هاست" یا "منظور از هزینه تعداد جمع های انجام شده است" و ... تا اینجا اوکی ؟ ولی بعضی وقت ها دنبال مقدار تایع هستیم که این مقدار تایع با هزینه تابع ممکنه یکی باشه ممکنه یکی نباشه !
در این تابع که شما گفتین مقدار تابع از حل این معادله بدست می آید : [tex]T(n)=T(n-3) T(n-3) n[/tex]
هزینه تابع در صورتی که تعداد فراخوانی مورد نظر باشد (که معمولا در اکثر مواقع اگه نگن منظور همینه) میشود :
[tex]T(n)=T(n-3) T(n-3) 1=2T(n-3) 1[/tex]
نه این استدلال غلطه
چون اگه n+ هم نداشتیم جوابمون با الان فرقی نداشت!
شما نگرفتی من چی گفتم ! من اون یک رو بخاطر n که نذاشتم ! من اون یک رو بخاطر این گذاشتم که یک بار تابع خودش رو فراخوانی میکنه بعلاوه [tex]2T(n-3)[/tex]