۰
subtitle
ارسال: #۱
مسئله ضرب ماتریس ها
با سلام
چرا در این معادله [tex]f(n)=7f(\frac{n}{2}) 15\frac{n^{2}}{4}[/tex] داریم:
[tex]\frac{n^{2}}{4}[/tex]
مرسی[/align]
چرا در این معادله [tex]f(n)=7f(\frac{n}{2}) 15\frac{n^{2}}{4}[/tex] داریم:
[tex]\frac{n^{2}}{4}[/tex]
مرسی[/align]
۰
ارسال: #۲
RE: مسئله ضرب ماتریس ها
چون تو هر مرحله، ماتریس ورودی به چهار تا ماتریس [tex]\frac{n}{2}*\frac{n}{2}[/tex] شکسته میشه پس سایز هر ماتریس میشه [tex]\frac{n}{2}*\frac{n}{2}[/tex] یا همون [tex]\frac{n^{2}}{4}[/tex] و طبق اون رابطه بازگشتی که شما نوشتی باید ۱۵ تا عمل جمع ماتریس‌ها با اندازه [tex]\frac{n^{2}}{4}[/tex] در هر مرحله انجام بشه.
ارسال: #۳
RE: مسئله ضرب ماتریس ها
(۳۱ خرداد ۱۳۹۰ ۰۸:۱۹ ب.ظ)mfXpert نوشته شده توسط: چون تو هر مرحله، ماتریس ورودی به چهار تا ماتریس [tex]\frac{n}{2}*\frac{n}{2}[/tex] شکسته میشه پس سایز هر ماتریس میشه [tex]\frac{n}{2}*\frac{n}{2}[/tex] یا همون [tex]\frac{n^{2}}{4}[/tex] و طبق اون رابطه بازگشتی که شما نوشتی باید ۱۵ تا عمل جمع ماتریس‌ها با اندازه [tex]\frac{n^{2}}{4}[/tex] در هر مرحله انجام بشه.
ممنونم از جوابتون ولی راستش من متوجه نشدم میشه مبتدی‌تر توضیح بدهید؟مر۳۰
۰
ارسال: #۴
RE: مسئله ضرب ماتریس ها
کتاب clrs دقیقا چنین نوشته:
کلید روش استراسن این است که کمی از انبوهیت درخت بازگشتی بکاهیم. یعنی به جای انجام هشت ضرب بازگشتی بر روی ماتریس n/2*n/2 فقط هفت ضرب انجام دهیم. هزینه حذف یک ضرب ماتریسی چندین جمع اضافی است ولی تعداد این جمع های اضافی ثابت است
این هزینه اضافی همون ۱۵ عمل جمع است ولی چرا ۲/۴^n ببین ما دو ماتریس n*n داشتیم که ضرب رو روی انها انجام میدادیم وقتی این ماتریس‌ها رو تقسیم کنیم چهار ماتریس از هر یک از این‌ها تشکیل می شود که هر کدام از انها n/2*n/2 بعد دارد و در یک ماتریس n/2*n/2 تعداد عناصر ۲/۴^n و ما ۱۵ عمل جمع رو این ماترس‌ها انجام میدیم و چون تعداد عناصر هر کدام از این ماتریس‌ها ۲/۴^n است داریم (۲/۴^n) ضرب در ۱۵ میشه
امیدوارم کافی باشه
کلید روش استراسن این است که کمی از انبوهیت درخت بازگشتی بکاهیم. یعنی به جای انجام هشت ضرب بازگشتی بر روی ماتریس n/2*n/2 فقط هفت ضرب انجام دهیم. هزینه حذف یک ضرب ماتریسی چندین جمع اضافی است ولی تعداد این جمع های اضافی ثابت است
این هزینه اضافی همون ۱۵ عمل جمع است ولی چرا ۲/۴^n ببین ما دو ماتریس n*n داشتیم که ضرب رو روی انها انجام میدادیم وقتی این ماتریس‌ها رو تقسیم کنیم چهار ماتریس از هر یک از این‌ها تشکیل می شود که هر کدام از انها n/2*n/2 بعد دارد و در یک ماتریس n/2*n/2 تعداد عناصر ۲/۴^n و ما ۱۵ عمل جمع رو این ماترس‌ها انجام میدیم و چون تعداد عناصر هر کدام از این ماتریس‌ها ۲/۴^n است داریم (۲/۴^n) ضرب در ۱۵ میشه
امیدوارم کافی باشه
۰
موضوع‌های مرتبط با این موضوع... |
|||||
| موضوع: | نویسنده | پاسخ: | بازدید: | آخرین ارسال | |
| کمک به حل مسئله | Moha33 | ۰ | ۱,۳۱۹ |
۰۵ تیر ۱۴۰۰ ۰۹:۴۲ ق.ظ آخرین ارسال: Moha33 |
|
 |
ذخیره ماتریس پایین مثلثی / بالا مثلثی به شیوه سطری یا ستونی | shayesteNEY | ۵ | ۱۰,۹۶۸ |
۲۲ مهر ۱۳۹۹ ۱۱:۲۸ ب.ظ آخرین ارسال: Negiiin |
 |
کامپیوتر یا هنر، مسئله این است | arian_61 | ۲ | ۴,۶۳۷ |
۲۵ دى ۱۳۹۸ ۱۱:۳۱ ق.ظ آخرین ارسال: packationmachinery |
| ضرب ماتریس ها | roller1829 | ۰ | ۲,۰۳۹ |
۱۹ مهر ۱۳۹۸ ۰۲:۴۸ ب.ظ آخرین ارسال: roller1829 |
|
| مسئله n_وزیر | Sanazzz | ۲ | ۳,۳۴۸ |
۱۱ بهمن ۱۳۹۷ ۰۳:۰۳ ب.ظ آخرین ارسال: Sanazzz |
|
| ماتریس ها در متلب | safoora s | ۱ | ۲,۱۵۲ |
۱۲ مرداد ۱۳۹۷ ۱۲:۲۲ ب.ظ آخرین ارسال: BBumir |
|
| صعودی کردن ماتریس mدرn | The BesT | ۷ | ۷,۳۲۵ |
۲۳ اردیبهشت ۱۳۹۷ ۰۲:۲۴ ب.ظ آخرین ارسال: Behnam |
|
|
دخیره ماتریس قطری و سه قطری | hossein14 | ۰ | ۲,۰۴۷ |
۲۷ آبان ۱۳۹۶ ۱۲:۱۷ ب.ظ آخرین ارسال: hossein14 |
| حل مشتق ماتریس | hanie_M | ۰ | ۳,۷۶۰ |
۲۵ آبان ۱۳۹۶ ۱۱:۵۹ ب.ظ آخرین ارسال: hanie_M |
|
| تبدیل تصویر به ماتریس در نرم افزار متلب | negar.v | ۳ | ۹,۴۴۹ |
۲۸ مهر ۱۳۹۶ ۱۲:۴۹ ق.ظ آخرین ارسال: farahnaz |
|
Can I see some ID?
Feeling left out?
نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. رمزت رو فراموش کردی؟ اینجا به یادت میاریم! close