با سلام
چرا در این معادله [tex]f(n)=7f(\frac{n}{2}) 15\frac{n^{2}}{4}[/tex] داریم:
[tex]\frac{n^{2}}{4}[/tex]
مرسی[/align]
چون تو هر مرحله، ماتریس ورودی به چهار تا ماتریس [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] در هر مرحله انجام بشه.
دقیقا درسته اگه متوجه نشدیدن توضیح بدیم.
(۳۱ خرداد ۱۳۹۰ ۰۸:۱۹ ب.ظ)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] در هر مرحله انجام بشه.
ممنونم از جوابتون ولی راستش من متوجه نشدم میشه مبتدی‌تر توضیح بدهید؟مر۳۰
کتاب clrs دقیقا چنین نوشته:
کلید روش استراسن این است که کمی از انبوهیت درخت بازگشتی بکاهیم. یعنی به جای انجام هشت ضرب بازگشتی بر روی ماتریس n/2*n/2 فقط هفت ضرب انجام دهیم. هزینه حذف یک ضرب ماتریسی چندین جمع اضافی است ولی تعداد این جمع های اضافی ثابت است
این هزینه اضافی همون ۱۵ عمل جمع است ولی چرا ۲/۴^n ببین ما دو ماتریس n*n داشتیم که ضرب رو روی انها انجام میدادیم وقتی این ماتریس‌ها رو تقسیم کنیم چهار ماتریس از هر یک از این‌ها تشکیل می شود که هر کدام از انها n/2*n/2 بعد دارد و در یک ماتریس n/2*n/2 تعداد عناصر ۲/۴^n و ما ۱۵ عمل جمع رو این ماترس‌ها انجام میدیم و چون تعداد عناصر هر کدام از این ماتریس‌ها ۲/۴^n است داریم (۲/۴^n) ضرب در ۱۵ میشه
امیدوارم کافی باشه