כפל מטריצות – הבדלי גרסאות

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