v.pan روشی ابداع کرده است که به وسیله ان می توان ماتریس های ۶۸*۶۸ را با ۱۳۲۴۶۴ ضرب و ماتریس های ۷۰×۷۰ را با ۱۴۳۶۴۰ ضرب و ماتریس های ۷۲×۷۲ را با ۱۵۵۴۲۴ ضرب در هم ضرب کرد.اگر از این روشها در یک الگوریتم تقسیم و حل برای ضرب ماتریسها استفاده کنیم کدام یک سریعترین زمان اجرای حدی را خواهد داشت؟سرعت این روش نسبت به الگوریتم استراسن چگونه خواهد بود؟(سوال clrs هست)
از روش معمولی ضرب با رابطهی بازگشتی زیر استفاده می کنیم ولی باید توجه کنید که شکسته شدن ابعاد تا بعد موردنظر انجام شود:
[tex]T\left( n \right )= 8T\left( \frac{n}{2} \right )[/tex]
خوب برای مورد اول که تا ابعاد ۶۸ شکسته میشه جواب رو به کمک جایگذاری برابر است با:
[tex]T\left( n \right )= 8T\left( \frac{n}{2} \right )= 8\left( 8T\left \left( \frac{n}{4} \right )\right )...= 8^{i}T\left( \frac{n}{2^{i}} \right )[/tex]
و همچنین تعداد سطوح:
[tex]\frac{n}{2^{i}}= 68\Rightarrow i= \lg \frac{n}{68}[/tex]
و پیچیدگی نهایی برای بعد ۶۸:
[tex]8^{\lg \frac{n}{68}}*\left( 132464 \right )[/tex]
و بقیه موارد هم به همین طریق حل میشه:
برای بعد ۷۰:
[tex]8^{\lg \frac{n}{70}}*\left( 143640 \right )[/tex]
و برای بعد ۷۲:
[tex]8^{\lg \frac{n}{72}}*\left( 155424 \right )[/tex]
در پیچیدگی های بالا اگر n به سمت بی نهایت بره بخش اول که نمایی است برای هر سه تقریبا برابر میشه ولی ثابت ابعاد ۶۸ کمتره که خودشو نشون میده پس روش تقسیم وحل برای مورد ۶۸ سریعتر خواهد بود.
در ضرب استریسن تابع نمایی اول با پایهی ۷ است و به مراتب سریعتر از این سه الگوریتم خواهد بود.