۰
subtitle
ارسال: #۱
  
با استفاده از تقسیم و حل کدام یک از سریعترند؟( ضرب ماتریسها به روش pan و استراسن )
v.pan روشی ابداع کرده است که به وسیله ان می توان ماتریس های ۶۸*۶۸ را با ۱۳۲۴۶۴ ضرب و ماتریس های ۷۰×۷۰ را با ۱۴۳۶۴۰ ضرب و ماتریس های ۷۲×۷۲ را با ۱۵۵۴۲۴ ضرب در هم ضرب کرد.اگر از این روشها در یک الگوریتم تقسیم و حل برای ضرب ماتریسها استفاده کنیم کدام یک سریعترین زمان اجرای حدی را خواهد داشت؟سرعت این روش نسبت به الگوریتم استراسن چگونه خواهد بود؟(سوال clrs هست)
۰
ارسال: #۲
  
RE: با استفاده از تقسیم و حل کدام یک سریعترند؟
از روش معمولی ضرب با رابطهی بازگشتی زیر استفاده می کنیم ولی باید توجه کنید که شکسته شدن ابعاد تا بعد موردنظر انجام شود:
[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 به سمت بی نهایت بره بخش اول که نمایی است برای هر سه تقریبا برابر میشه ولی ثابت ابعاد ۶۸ کمتره که خودشو نشون میده پس روش تقسیم وحل برای مورد ۶۸ سریعتر خواهد بود.
در ضرب استریسن تابع نمایی اول با پایهی ۷ است و به مراتب سریعتر از این سه الگوریتم خواهد بود.
[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 به سمت بی نهایت بره بخش اول که نمایی است برای هر سه تقریبا برابر میشه ولی ثابت ابعاد ۶۸ کمتره که خودشو نشون میده پس روش تقسیم وحل برای مورد ۶۸ سریعتر خواهد بود.
در ضرب استریسن تابع نمایی اول با پایهی ۷ است و به مراتب سریعتر از این سه الگوریتم خواهد بود.
Can I see some ID?
Feeling left out?
نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. رمزت رو فراموش کردی؟ اینجا به یادت میاریم! close