پیچیدگی زمانی ماتریس n.n

ایا به جز استراسن کسی پیچبدگی ماتریn.n را کاهش داده
اگه ممکنه سایت معرفی کنید

ممنون

بله یه الگوریتمی هست که توسط وینوگراد و کوپر اسمیت نوشته شده و پیچیدیگی زمانیش O(n^2.376) هست ولی مقدار ثابت بزرگی داره که باعث می شه فقط برای مقادیر خیلی بزرگ کارا تر از الگوریتم استراسن باشه ولی در هر حال این بهترین الگوریتم شناخته شده برای ضرب ماتریس ها ی n*n هست

http://en.wikipedia.org/wiki/Coppers...grad_algorithm

ضمن اینکه ...
حد بالای ضرب ماتریس، بیگ امگای n به توان دو است. یعنی هیچ الگوریتمی نمیتونی بنویسی که از n به توان 2 بهتر عمل کنه.

سلام

لینک داده شده کامل نیست از دوستان کسی می تونه لینکی بده که هم شبه کد و هم رابطه بازگشتی این الگوریتم باشد؟

الگوریتم ضرب ماتریس های n*n به صورت ۳ حلقه ی for تودرتو نوشته میشه
به ازای هر for تو در تو یه n . پس ۳ تا for تودر تو میشه : n*n*n که برابره با n^3

الگوریتم وینوگراد تا سال 2010 سریعترین بوده.
تو سال 2010 الگوریتم توسط Andrew Stothers بهبود پیدا کرده و تو سال 2011 ویرجینیا ویلیامز از استنفورد دوباره اونو سریعتر کرده.
همین اواخرم توی 2014 فرانسوا لو گال متود ویلیامز رو ساده تر کرده و سریعترش کرده.
همچنین توجه داشته باش که از الگوریتم کاپراسمیت-وینوگراد نمیشه در عمل استفاده کرد، چون ضریب ثابت اون خیلی بزرگه و فقط برای ضرب ماتریس های خیلی بزرگ میشه ازش استفاده کرد که سخت افزارهای امروزی قابلیت پردازش اونارو ندارن.

نقل قول:

---

نوشته شده توسط darknes666

الگوریتم وینوگراد تا سال 2010 سریعترین بوده.
تو سال 2010 الگوریتم توسط Andrew Stothers بهبود پیدا کرده و تو سال 2011 ویرجینیا ویلیامز از استنفورد دوباره اونو سریعتر کرده.
همین اواخرم توی 2014 فرانسوا لو گال متود ویلیامز رو ساده تر کرده و سریعترش کرده.
همچنین توجه داشته باش که از الگوریتم کاپراسمیت-وینوگراد نمیشه در عمل استفاده کرد، چون ضریب ثابت اون خیلی بزرگه و فقط برای ضرب ماتریس های خیلی بزرگ میشه ازش استفاده کرد که سخت افزارهای امروزی قابلیت پردازش اونارو ندارن.

---

توضیحات بسیار خوبی بود