Я придумал этот алгоритм для матричного умножения. Я где-то читал, что матричное умножение имеет временную сложность o (n ^ 2). Но я думаю, что мой этот алгоритм даст o (n ^ 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]
Наивный алгоритм, который есть у вас после того, как вы исправили его, как отмечено в комментариях, - это O (n ^ 3).
Существуют алгоритмы, которые несколько уменьшают это, но вы вряд ли найдете реализацию O (n ^ 2). Я считаю, что вопрос об наиболее эффективной реализации все еще открыт.
Для получения дополнительной информации см. эту статью в википедии Matrix Multiplication.
Используя линейную алгебру, существуют алгоритмы, которые достигают лучшей сложности, чем наивная O (n 3). Алгоритм Solvay Strassen достигает сложности O (n 2.807) за счет уменьшения количества умножений, требуемых для каждого субстрата 2x2, матрица от 8 до 7.
Самый быстрый алгоритм матричного умножения - алгоритм Coppersmith-Winograd со сложностью O (n 2.3737). Если матрица не огромна, эти алгоритмы не приводят к огромной разнице в времени вычислений. На практике проще и быстрее использовать параллельные алгоритмы для матричного умножения.
Стандартный способ умножения матрицы m-на-n на матрицу n-by-p имеет сложность O (mnp). Если все они "n" вам, то O (n ^ 3), а не O (n ^ 2). EDIT: в общем случае он не будет O (n ^ 2). Но существуют более быстрые алгоритмы для конкретных типов матриц - если вы знаете больше, вы сможете сделать лучше.
В матричном умножении есть 3 для цикла, мы используем, так как выполнение каждого цикла for требует сложности времени O(n). Таким образом, для трех циклов он становится O(n^3)