Редактирование: Метод четырёх русских для умножения матриц

Перейти к: навигация, поиск

Внимание! Вы не авторизовались на сайте. Ваш IP-адрес будет публично видимым, если вы будете вносить любые правки. Если вы войдёте или создадите учётную запись, правки вместо этого будут связаны с вашим именем пользователя, а также у вас появятся другие преимущества.

Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия Ваш текст
Строка 1: Строка 1:
{{Задача
+
Дано две квадратных матрицы <tex>A_{[n \times n]}</tex> и <tex>B_{[n \times n]}</tex>,  
|definition = Дано две квадратных матрицы <tex>A_{[n \times n]}</tex> и <tex>B_{[n \times n]}</tex>,  
 
 
состоящие из нулей и единиц. Нужно найти их произведение. При этом, все операции выполняются по модулю <tex>2</tex>.
 
состоящие из нулей и единиц. Нужно найти их произведение. При этом, все операции выполняются по модулю <tex>2</tex>.
}}
+
 
</noinclude>
 
<includeonly>{{#if: {{{neat|}}}|
 
<div style="background-color: #fcfcfc; float:left;">
 
<div style="background-color: #ddd;">'''Задача:'''</div>
 
<div style="border:1px dashed #2f6fab; padding: 8px; font-style: italic;">{{{definition}}}</div>
 
</div>|
 
<table border="0" width="100%">
 
<tr><td style="background-color: #ddd">'''Задача:'''</td></tr>
 
<tr><td style="border:1px dashed #2f6fab; padding: 8px; background-color: #fcfcfc; font-style: italic;">{{{definition}}}</td></tr>
 
</table>}}
 
</includeonly>
 
 
== Простое решение ==
 
== Простое решение ==
  
Если мы будем считать произведение матриц <tex>C = A \cdot B</tex> по определению <tex dpi=130>\left(c_{i, j} = \sum\limits_{k = 1}^n a_{i,k}b_{k,j}\right)</tex>, то сложность работы алгоритма составит <tex>O(n^3)</tex> {{---}} каждый из <tex>n^2</tex> элементов результирующей матрицы <tex>C</tex> вычисляется за время, пропорциональное <tex>n</tex>.
+
Если мы будем считать произведение матриц <tex>C = A \cdot B</tex> по определению <tex dpi=140>(c_{i, j} = \sum\limits_{k = 1}^n a_{i,k}b_{k,j})</tex>, то сложность работы алгоритма составит <tex>O(n^3)</tex> {{---}} каждый из <tex>n^2</tex> элементов результирующей матрицы <tex>C</tex> вычисляется за время, пропорциональное <tex>n</tex>.
  
 
Сейчас будет показано, как немного уменьшить это время.
 
Сейчас будет показано, как немного уменьшить это время.
Строка 28: Строка 16:
 
Аналогично поступим с матрицей <tex>B</tex>, вместо строк деля столбцы. Получим матрицу <tex dpi=140>B'_{\lceil\frac nk\rceil\times n}</tex>.
 
Аналогично поступим с матрицей <tex>B</tex>, вместо строк деля столбцы. Получим матрицу <tex dpi=140>B'_{\lceil\frac nk\rceil\times n}</tex>.
  
Теперь, если вместо произведения матриц <tex>A</tex> и <tex>B</tex> считать произведение новых матриц <tex>A'</tex> и <tex>B'</tex>, воспользовавшись посчитанными скалярными произведениями, то каждый элемент матрицы <tex>C</tex> будет получаться уже за время, пропорциональное <tex>\lceil \dfrac{n}{k} \rceil</tex> вместо <tex>n</tex>, и время произведения матриц сократится с <tex>O(n^3)</tex> до <tex>O(n^2 \cdot\dfrac nk) = O(\dfrac{n^3}{k}) </tex>.
+
Теперь, если вместо произведения матриц <tex>A</tex> и <tex>B</tex> считать произведение новых матриц <tex>A'</tex> и <tex>B'</tex>, воспользовавшись посчитанными скалярными произведениями, то каждый элемент матрицы <tex>C</tex> будет получаться уже за время, пропорциональное <tex>\lceil \frac nk \rceil</tex> вместо <tex>n</tex>, и время произведения матриц сократится с <tex>O(n^3)</tex> до <tex dpi=140>O(n^2 \cdot\frac nk) = O(\frac{n^3}{k}) </tex>.
  
 
== Оценка сложности алгоритма и выбор k ==
 
== Оценка сложности алгоритма и выбор k ==
Строка 36: Строка 24:
  
 
* Предподсчёт скалярных произведений работает за <tex>O(2^{2k}k)</tex>.
 
* Предподсчёт скалярных произведений работает за <tex>O(2^{2k}k)</tex>.
* Создание матриц <tex>A'</tex> и <tex>B'</tex> {{---}} <tex>O(n^2)</tex>.
+
* Создание матриц <tex>A'</tex> и <tex>B'</tex> {{---}} <tex>O(n^2)</tex>
* Перемножение полученных матриц {{---}} <tex>O(\dfrac{n^3}{k})</tex>.
+
* Перемножение полученных матриц {{---}} <tex dpi=140>O(\frac{n^3}{k})</tex>
  
Итого: <tex>O(2^{2k}k) + O(\dfrac{n^3}{k})</tex>.
+
Итого: <tex>O(2^{2k}k) + O(\frac{n^3}{k})</tex>.
Выбрав  <tex>k = \log n </tex>, получаем требуемую асимптотику <tex>O(n^2 \log n) + O(\dfrac{n^3}{\log n}) = O(\dfrac{n^3}{\log n})</tex>
+
Выбрав  <tex>k = \log n </tex>, получаем требуемую асимптотику <tex dpi=140>O(n^2 \log n) + O(\frac{n^3}{\log n}) = O(\frac{n^3}{\log n})</tex>
  
 
== Пример работы алгоритма ==
 
== Пример работы алгоритма ==
Строка 70: Строка 58:
  
 
<tex>
 
<tex>
\begin{array}{|c|c|c|c|c|}   
+
\begin{tabular}{|c|c|c|c|c|}   
 
         \hline   
 
         \hline   
 
           &  \textbf{00} & \textbf{01} & \textbf{10} & \textbf{11} \\
 
           &  \textbf{00} & \textbf{01} & \textbf{10} & \textbf{11} \\
Строка 82: Строка 70:
 
           \textbf{11} & 0 & 1 & 1 & 0\\                   
 
           \textbf{11} & 0 & 1 & 1 & 0\\                   
 
         \hline   
 
         \hline   
       \end{array}  
+
       \end{tabular}  
 
</tex>
 
</tex>
  
Строка 125: Строка 113:
 
[[Категория: Дискретная математика и алгоритмы]]
 
[[Категория: Дискретная математика и алгоритмы]]
 
[[Категория: Динамическое программирование]]
 
[[Категория: Динамическое программирование]]
[[Категория: Способы оптимизации методов динамического программирования]]
 

Пожалуйста, учтите, что любой ваш вклад в проект «Викиконспекты» может быть отредактирован или удалён другими участниками. Если вы не хотите, чтобы кто-либо изменял ваши тексты, не помещайте их сюда.
Вы также подтверждаете, что являетесь автором вносимых дополнений, или скопировали их из источника, допускающего свободное распространение и изменение своего содержимого (см. Викиконспекты:Авторские права). НЕ РАЗМЕЩАЙТЕ БЕЗ РАЗРЕШЕНИЯ ОХРАНЯЕМЫЕ АВТОРСКИМ ПРАВОМ МАТЕРИАЛЫ!

Чтобы изменить эту страницу, пожалуйста, ответьте на приведённый ниже вопрос (подробнее):

Отменить | Справка по редактированию (в новом окне)

Шаблоны, используемые на этой странице: