سلام
بنده در درس طراحی الگوریتم در قسمت جمع و تفریق استراسن به مشکل برخوردم اگر دوستان لطف کنند و کمی ساده تر از کتاب توضیح بدهند سپاسگذار خواهم بود
در قسمت ضرب ها که فرمول به شکل زیر است و مشکلی نیست
[attachment=4266]
اما در قسمت جمع و تفریق چرا باید تعداد ضرب ها رو هم بنویسیم ( (۷t(n/2 ) مگر ما تعداد جمع ها و تفریق ها رو نیاز نداریم
[attachment=4267]
این قسمت رو اصلا متوجه نشدم چجوری حساب کرد که به جواب نهایی رسید
[attachment=4268]
در مورد سوال دوم log7 در مبنای ۲ معادل عدد ۲/۸۱ هستش حالا چون ما مقدار دقیق رو می خواییم از [tex]\theta[/tex] استفاده کنیم چون ۲/۸۱>2 لذا [tex]\theta (n^{2.81})[/tex]
در مورد سوال اول در این الگوریتم تا حدی از تعداد عملیات ضرب کم می شود و از [tex]n^{3}[/tex] به [tex]n^{2.81}[/tex] کاهش دارد.اما عملیات جمع که در حالت بدون تقسیم و غلبه ۴ تا بود به ۱۸ تا افزایش می یابد یعنی از تعداد ضرب کم و به تعداد جمع اضافه می کنیم اما چون عملیات مدنظر همان ضرب است لذا این الگوریتم کاراتر است .
شما دقت کن هر چه مقدار n بیشتر میشه عملیات جمع هم زیاد میشه . اگه n=2 باشد دقیقا ۷ عمل ضرب و ۱۸ عمل جمع داریم حال شما n=4 باشد چون عملیات جمع به ضرب وابسته هست عملیات جمع افزایش میابد [tex]T(n=4)=7T(2) 18(2)^{2}=7*18 18*4=198[/tex] با هر تعداد افزایش n عملیات جمع بشدت زیاد می شود
برای یادگیری کامل این مطلب میتونید به کتاب راهیان ارشد رجوع کنید
ممنون
اما متوجه نمیشوم که چه عملیاتی [tex]t(n)=7t(\frac{n}{2}) 18(\frac{n}{2})^{2}[/tex] میشود تا استراسن به این فرمول میرسد [tex]6n^{2.81}-6n^{2}[/tex]
ببین دوست من این بر میگرده به حل روابط بازگشتی این تابع بازگشتی [tex]T(n)=7T(n/2) (18/4)n^{2}[/tex] به فرم [tex]T(n)=aT(n/b) Cn^{k}[/tex] می باشد که برای حل آن باید [tex]a[/tex] را با [tex]b^{k}[/tex] مقایسه کنیم اینجا [tex](a=7) >(b^{k}=2^{2}=4)[/tex] چون [tex]a[/tex] بزرگتر است جواب معادله می شود [tex]\theta (n^ {log7})=\theta (n^{2.81})[/tex]
برای یادگیری روابط بازگشتی به کتاب راهیان یا پوران یا مراجع مثل نیپولیتان و clrs رجوع کنید
نفهمیدی این لینک رو هم یه نگاه بنداز امروز دیدم خوب بود :
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.