כפל מטריצות – הבדלי גרסאות
תוכן שנמחק תוכן שנוסף
הוספת קישור לערך על שמואל וינוגרד |
|||
שורה 22:
הכפלת שתי מטריצות ריבועיות בגודל n על n על פי ההגדרה דורש סיבוכיות של סדר גודל n בשלישית פעולות.
ב-[[1969]] הראה [[וולקר שטראסן]] כי ניתן להכפיל מטריצות באופן יעיל יותר ("[[אלגוריתם שטראסן]]") של <math>n^{\log_2 7}</math> (בערך 2.807). שיפורים נוספים הורידו את החזקה ל-2.376 ([[דון קופרסמיט]] ו[[שמואל וינוגרד]], [[1987]]), ואז ל-2.373 ([[2010]]). זו הסיבוכיות הטובה ביותר הידועה, אם כי הקבועים העצומים הופכים את האלגוריתם הזה לתאורטי בלבד.
===שימושי הכפל===
| |||