(۲۶ فروردین ۱۳۹۶ ۰۳:۳۱ ب.ظ)msour44 نوشته شده توسط:  سلام
باید توجه کرد که فقط در گام اول تعداد ضرب کاهش می یابد و لی در گام های بعدی همان مسئله کلاسیک ضرب دو چند جمله ای است.
ورابطه بازگشتی مسئله اصلی ضرب دو چندجمله ای هم برابر با [tex]T(n)=3T(\frac{n}{2})+\theta(n)[/tex]
در واقع به طور کلی ضرب دو چند جمله ای با درجه n-1 (برای راحتی) به ضرب چند جمله ای های درجه n/2 -1 تبدیل می کنیم
[tex]A(x)=Aَ_l+A_r\: x^{\frac{n}{2}}[/tex] , [tex]B'(x)=B'َ_l+B'_r\: x^{\frac{n}{2}}[/tex]
[tex]C(x)=a_lb_l+[(a_l+a_r)(b'_l+b'_r)-a_lb'_l-a_rb'_r]x^{\frac{n}{2}}+a_rb'_rx^{{n}}[/tex]
[tex]b'_l[/tex] در سوال صفراست
[tex]C(x)=[(a_l+a_r).b'_r-a_rb'_r]x^{\frac{n}{2}}+a_rb'_rx^n[/tex]
کافی است دو ضرب [tex](a_l+a_r)b'_r[/tex] و [tex]a_rb'_r[/tex] را محاسبه و در عبارت بالا قرار دهیم این دو ضرب با همان روش کلاسیک انجام می شود ولی درجه چند جمله ای ها تقریبا نصف شده که تقریبا [tex]\frac{n}{2}[/tex] می گیرم پس رابطه بازگشتی ان برابر با
[tex]T(\frac{n}{2})=3T(\frac{n}{4})+\theta(\frac{n}{2})[/tex]
که دارای مرتبه[tex]O(n^{\lg3})[/tex] است و دوتا ازاین ضرب ها داریم که در مرتبه نهایی تاثیری ندارد.
اینکه رابطه بازگشتی تغییر نمی کند اگر منظور طراح رابطه بازگشتی که از لحاظ مرتبه(هزینه الگوریتم) تغییر نمی کند بله رابطه جدید از لحاظ مرتبه معادل رابطه اولیه است.گزینه۲ (البته بعد از تصحیح غلط املایی)
ممکن است این ابهام هم پیش بیاید که منظور از رابطه بازگشتی کدام رابطه است رابطه تعداد ضرب ها یا تعداد جمع ها یا تعداد شیفت ها یا هزینه کلی یا...