сложность времени алгоритма умножения матриц

Question

Я придумал этот алгоритм для умножения матриц. Я где-то читал, что умножение матриц имеет временную сложность o (n ^ 2). Но я думаю, что мой этот алгоритм даст о (п ^ 3). Я не знаю, как рассчитать временную сложность вложенных циклов. Поэтому, пожалуйста, поправьте меня.

for i=1 to n
   for j=1 to n    
     c[i][j]=0
     for k=1 to n
         c[i][j] = c[i][j]+a[i][k]*b[k][j]

Answer 1

Используя линейную алгебру, существуют алгоритмы, которые достигают большей сложности, чем наивный O (n ³ ). Solvay Strassen Алгоритм обеспечивает сложность O (n ^2.807 ), уменьшая количество умножений, необходимых для каждой субматрицы 2x2, с 8 до 7.

Самый быстрыйИзвестным алгоритмом умножения матриц является алгоритм Копперсмита-Винограда со сложностью O (n ^2.3737 ).Если матрица не огромна, эти алгоритмы не приводят к большой разнице во времени вычислений.На практике проще и быстрее использовать параллельные алгоритмы для умножения матриц.

Answer 2

Наивный алгоритм, который вы получите после того, как исправите его, как отмечено в комментариях, - это O (n ^ 3).

Существуют алгоритмы, которые несколько уменьшают это, но вымаловероятно, чтобы найти реализацию O (n ^ 2).Я считаю, что вопрос о наиболее эффективной реализации до сих пор остается открытым.

См. Эту статью в Википедии по Умножение матриц для получения дополнительной информации.

Answer 3

Стандартный способ умножения матрицы m на n на матрицу n на p имеет сложность O (mnp). Если для вас все это "n", то это O (n ^ 3), а не O (n ^ 2). РЕДАКТИРОВАТЬ: это не будет O (n ^ 2) в общем случае. Но существуют более быстрые алгоритмы для определенных типов матриц - если вы знаете больше, вы можете добиться большего успеха.

Answer 4

В матричном умножении есть 3 для цикла, который мы используем, поскольку выполнение каждого для цикла требует сложности времени O(n). Таким образом, для трех петель это становится O(n^3)