Какова асимптотика времени работы самого быстрого известного алгоритма умножения матриц?

задан 14 Дек '11 20:00

10|600 символов нужно символов осталось
3

Я слышал, что недавно этот результат был улучшен. Один молодой питерский ученый описал важность этого результата здесь: http://habrahabr.ru/post/133875/ Про теоретическую возможность квадратичного алгоритма пока ничего не нашел.

ссылка

отвечен 25 Май '13 23:49

10|600 символов нужно символов осталось
2

Как утверждает Википедия, самым быстрым из опубликованных является алгоритм Копперсмита-Винограда, сложность $%O(n^{2.375})$%. Теоретически было показана возможность существования алгоритма сложности $%O(n^{2})$%. Все это рассмотрено для перемножения квадратных матриц порядка n.

ссылка

отвечен 14 Дек '11 20:49

1

Копперсмит-Виноград -- это 2.376 всё же. Про теоретическую возможность квадратичного алгоритма не понял...

(14 Дек '11 20:52) Sasha
10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×254
×76
×17

задан
14 Дек '11 20:00

показан
3712 раз

обновлен
25 Май '13 23:49

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru