زمان کنونی: ۱۴ اردیبهشت ۱۴۰۳, ۰۱:۲۹ ب.ظ مهمان گرامی به انجمن مانشت خوش آمدید. برای استفاده از تمامی امکانات انجمن می‌توانید عضو شوید.
گزینه‌های شما (ورودثبت نام)

با استفاده از تقسیم و حل کدام یک از سریعترند؟( ضرب ماتریسها به روش pan و استراسن )

ارسال:
  

sal_dovomi پرسیده:

با استفاده از تقسیم و حل کدام یک از سریعترند؟( ضرب ماتریسها به روش 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 به سمت بی نهایت بره بخش اول که نمایی است برای هر سه تقریبا برابر میشه ولی ثابت ابعاد ۶۸ کمتره که خودشو نشون میده پس روش تقسیم وحل برای مورد ۶۸ سریعتر خواهد بود.
در ضرب استریسن تابع نمایی اول با پایه‌ی ۷ است و به مراتب سریعتر از این سه الگوریتم خواهد بود.



موضوع‌های مرتبط با این موضوع...
موضوع: نویسنده پاسخ: بازدید: آخرین ارسال
  پارسه، مدرسان شریف،ماهان و.... کدام یک بهتره؟؟؟ alim93 ۶۴ ۶۷,۱۸۹ ۰۷ تیر ۱۴۰۱ ۱۲:۵۶ ق.ظ
آخرین ارسال: عزیز دادخواه
  استفاده از پشته armiii ۰ ۹۴۹ ۰۳ دى ۱۴۰۰ ۱۲:۴۳ ق.ظ
آخرین ارسال: armiii
  کدام زبان برای هوش مصنوعی بهتر است؟ فرق بین زبان های هوش مصنوعی چیست؟ azam2075 ۳ ۵,۵۴۹ ۱۴ مهر ۱۴۰۰ ۰۷:۲۱ ب.ظ
آخرین ارسال: علیصا
  آزمون آزمایشی ارشد کدام موسسه را شرکت کنیم Ali1991khe ۲ ۳,۲۳۴ ۱۴ آبان ۱۳۹۹ ۱۲:۰۹ ق.ظ
آخرین ارسال: Ali1991khe
  آزمون آزمایشی ارشد کدام موسسه را شرکت کنیم Ali1991khe ۲ ۳,۰۰۹ ۰۸ آبان ۱۳۹۹ ۱۲:۰۴ ب.ظ
آخرین ارسال: Ali1991khe
  کدام زبان برنامه‌نویسی بهترین انتخاب است؟ elecomco ۲ ۲,۸۰۰ ۱۰ شهریور ۱۳۹۹ ۰۵:۱۶ ب.ظ
آخرین ارسال: kilookiloo
  فرصت استفاده از استعداد برای ورودی دکتری wskf ۳ ۳,۰۳۸ ۲۴ فروردین ۱۳۹۹ ۰۵:۵۷ ب.ظ
آخرین ارسال: wskf
  کسی از صداگیر گوشی استفاده میکنه؟ pooyaa ۱۳ ۴۰,۹۳۷ ۱۷ اسفند ۱۳۹۸ ۱۰:۲۰ ب.ظ
آخرین ارسال: malihe.74
  تعداد روش های نوشتن عدد n ss311 ۲ ۳,۰۳۶ ۱۳ بهمن ۱۳۹۸ ۰۵:۲۷ ب.ظ
آخرین ارسال: ss311
  مشاوره روش تحقیق و تحلیل آماری sirvan.t ۰ ۱,۹۶۱ ۱۷ آذر ۱۳۹۸ ۱۲:۵۹ ق.ظ
آخرین ارسال: sirvan.t

پرش به انجمن:

Can I see some ID?

به خاطر سپاری رمز Cancel

Feeling left out?


نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. رمزت رو فراموش کردی؟ اینجا به یادت میاریم! close

رمزت رو فراموش کردی؟

Feeling left out?


نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. close