الگوریتم بازگشتی تابع [tex]\sum i[/tex] به صورت زیر می باشد
[tex]int\: \: \: \: \: \: \: \: Rec(int\: n)[/tex]
[tex]\opencurlybrace[/tex]
[tex]if(n==1)[/tex]
return 1
else
[tex]return\: \: \: \: n Rec(n-1)[/tex]
[tex]\closecurlybrace[/tex]
رابطه بازگشتی مربوط به مرتبه زمانی این الگوریتم به صورت [tex]T(n)=T(n-1) \theta(1)[/tex] می باشد
لطفا بگید چگونه رابطه بازگشتی بالا را بدست اورد ؟
پاسخ جدید (پاسخ کامل) :
توضیح:
[tex]\theta(1)[/tex] به خاطره عملیات جمع در عبارت
[tex]return\: \: \: \: \: n Rec(n-1)[/tex]
هستش و به صورت جمع ظاهر میشه.
اما قسمت اصلی رابطه بازگشتی به خاطر اینه که در ابتدا ما تابع [tex]Rec(n)[/tex] رو داریم و در فراخوانی مجدد تابع [tex]Rec(n-1)[/tex] رو داریم .پس رابطه مرتبه زمانی یه شکل زیر درمیاد:
[tex]Rec(n)=Rec(n-1) 1[/tex]
شما باید محاسبات مورد نیاز رو به دست آوردن مرتبه زمانی لحاظ کنید.
اما قسمت اصلی رابطه بازگشتی به خاطر اینه که در ابتدا ما تابع [tex]Rec(n)[/tex] رو داریم و در فراخوانی مجدد تابع [tex]Rec(n-1)[/tex] رو داریم .پس رابطه مرتبه زمانی یه شکل زیر درمیاد:
[tex]Rec(n)=Rec(n-1) 1[/tex]
شما باید محاسبات مورد نیاز رو به دست آوردن مرتبه زمانی لحاظ کنید.
[/quote]
این قسمت بالا را نفهمیدم، مثلا برای بدست اوردن رابطه بازگشتی الگوریتم a تفسیم بر b که در صفحه ۱۹ طراحی الگوریتم مدرسان شریف اومده چطوری بدست می اوریم یا الگوریتم بزرگترین مقسوم علیه مشترک
محاسبات مورد نیاز چی ان؟ لطفا بیشتر توضیح بدین
من این کتابو ندارم. اگه میتونید از اوون صفحه عکس بگیرید و آپلود کنید.
من این کتابو ندارم. اگه میتونید از اوون صفحه عکس بگیرید و آپلود کنید.
[/quote]
ببینید توی این کتاب الگوریتم های جمع اعداد ، فاکتوریل، ضرف، توان، تقسیم و بزرگترین مقسوم علیه مشترک را اورده، من می خوام بدونم هر کدومو چطوری [tex]T(n)[/tex] هاشونو یعنی رابطه بازگشتی هاشونو بدست می اریم تا بتونیم مرتبه زمانیشون هم بدست بیاریم
پاسخ :