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

תוכן שנמחק תוכן שנוסף
Nurick (שיחה | תרומות)
מ שוחזר מעריכות של 213.151.59.151 (שיחה) לעריכה האחרונה של Addbot
←‏סיבוכיות הכפל: ראו http://theory.stanford.edu/~virgi/sigactcolumn.pdf
שורה 24:
ב-[[1969]] הראה [[וולקר שטראסן]] כי ניתן להכפיל מטריצות באופן יעיל יותר ("[[אלגוריתם שטראסן]]") של <math>n^{\log_2 7}</math> (בערך 2.807).
 
ב-[[19901987]] הצליחו דון קופרסמיט ושמואל וינוגרד להגיע לאלגוריתם מכפלה שהסיבוכיות שלו נמוכה עד כדי n בחזקת 2.376, ונכוןחסם שהחזיק מעמד עשרות שנים עד שיפורו ל-2.374 בשנת 2010 ואח"כ ל-2.373. נכון ל[[20112014]] זו הסיבוכיות הטובה ביותר; אם כי הקבועים העצומים הופכים את האלגוריתם הזה לתאורטי בלבד.
 
===שימושי הכפל===