اگر حد آستانه تقسیم در مسئله ضرب ماتریس ها به روش استراسن ماتریس های ۴*۴ باشد انگاه تعداد فراخوانی های الگوریتم استراسن برای ضرب دوماتریس ۶۴*۶۴ چقدر خواهد بود؟
سلام
اگر درخت بازگشت رو از [tex]T(64)[/tex] رو به پایین رسم کنید و هر بار نصف کنید، تا زمانی که به [tex]T(4)[/tex] می رسید و [tex]T(4)=1[/tex] رو آستانه در نظر بگیرید.
با توجه به رابطه بازگشتی استراسن داریم :
[tex]T(n)=7T(\frac{n}{2})[/tex]
[tex]7^0+7^1+7^2+7^3+7^4=\sum^4_{i=0}=\frac{7^{4+1}-1}{7-1}[/tex]
مفهوم توان های عدد هفت :
۵ سطحی هست که از درخت بازگشت و با توجه به رابطه بازگشتی بدست می آید