|
Какова асимптотика времени работы самого быстрого известного алгоритма умножения матриц? задан 14 Дек '11 20:00 
Sasha |
|
Я слышал, что недавно этот результат был улучшен. Один молодой питерский ученый описал важность этого результата здесь: http://habrahabr.ru/post/133875/ Про теоретическую возможность квадратичного алгоритма пока ничего не нашел. отвечен 25 Май '13 23:49 
AlexGolovnev |
|
Как утверждает Википедия, самым быстрым из опубликованных является алгоритм Копперсмита-Винограда, сложность $%O(n^{2.375})$%. Теоретически было показана возможность существования алгоритма сложности $%O(n^{2})$%. Все это рассмотрено для перемножения квадратных матриц порядка n. отвечен 14 Дек '11 20:49 
Occama 1
Копперсмит-Виноград -- это 2.376 всё же. Про теоретическую возможность квадратичного алгоритма не понял...
(14 Дек '11 20:52)
Sasha
|