Алгоритм Копперсмита — Винограда

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

Алгоритм Копперсмита—Винограда — алгоритм умножения квадратных матриц, предложенный в 1987 году Д. Копперсмитом и Ш. Виноградом (англ.) и улучшенный в 2010 году Вирджинией Вильямс. В исходной версии асимптотическая сложность алгоритма составляла O(n2,3755), а в варианте Вильямс — O(n2,3727), где n — размер стороны матрицы, что пока является самым лучшим результатом среди известных алгоритмов.[1]

Однако на практике алгоритм Копперсмита—Винограда не используется, так как он имеет очень большую константу пропорциональности и начинает выигрывать в быстродействии у других известных алгоритмов только для матриц, размер которых превышает память современных компьютеров.

См. также[править | править исходный текст]

Литература[править | править исходный текст]

Ссылки[править | править исходный текст]

  1. Williams, Virginia (2011), Breaking the Coppersmith-Winograd barrier