Бывает...
блин, вот читаю это, и плачу:
Алгоритм Штрассена ... В отличие от традиционного алгоритма умножения матриц, работающего за время Θ(n^3) = Θ(n^log2 8), алгоритм Штрассена умножает матрицы за время Θ(n^log2 7) = Θ(n^2.81).
...
<начинается разбор алгоритма, приведена некая процедура>
Однако с помощью этой процедуры нам не удалось уменьшить количество умножений. Как и в обычном методе, нам требуется 8 умножений.
...
<производится "финт ушами"> Таким образом, нам <уже> нужно всего <всего-то каких-то!> 7 умножений на каждом этапе рекурсии.
рофл же!
Штрассен был первым, кто показал возможность умножения матриц более эффективным способом... После публикации его работы начались поиски более быстрого алгоритма. Самым быстрым алгоритмом на сегодняшний день является алгоритм Копперсмита — Винограда, позволяющий перемножать матрицы за O(n^2.375) операций.
Существует модификация алгоритма Штрассена, для которой требуется 7 умножений и 15 сложений (вместо 18 для обычного алгоритма Штрассена).
Смотрю я на это, и понимаю, что математика и вот такие подобные выкидоны и увлечения -- это совершенно не моя стезя. По мне так лучше уж я буду каким-нибудь самодостаточным фермером в райской глухомани, чем восседать на утончающемся пике количества арифметических операций для какой-то математической задачи, пусть онакому-то и невероятно важна для технического прогресса.
Алгоритм Штрассена ... В отличие от традиционного алгоритма умножения матриц, работающего за время Θ(n^3) = Θ(n^log2 8), алгоритм Штрассена умножает матрицы за время Θ(n^log2 7) = Θ(n^2.81).
...
<начинается разбор алгоритма, приведена некая процедура>
Однако с помощью этой процедуры нам не удалось уменьшить количество умножений. Как и в обычном методе, нам требуется 8 умножений.
...
<производится "финт ушами"> Таким образом, нам <уже> нужно всего <всего-то каких-то!> 7 умножений на каждом этапе рекурсии.
рофл же!
Штрассен был первым, кто показал возможность умножения матриц более эффективным способом... После публикации его работы начались поиски более быстрого алгоритма. Самым быстрым алгоритмом на сегодняшний день является алгоритм Копперсмита — Винограда, позволяющий перемножать матрицы за O(n^2.375) операций.
Существует модификация алгоритма Штрассена, для которой требуется 7 умножений и 15 сложений (вместо 18 для обычного алгоритма Штрассена).
Смотрю я на это, и понимаю, что математика и вот такие подобные выкидоны и увлечения -- это совершенно не моя стезя. По мне так лучше уж я буду каким-нибудь самодостаточным фермером в райской глухомани, чем восседать на утончающемся пике количества арифметических операций для какой-то математической задачи, пусть она
-
-
04.06.2010 в 11:54-
-
05.06.2010 в 00:14