Улучшение умножения наивного матрицы ⇐ C++

[Anonymous]

Мой учитель CS попросил нас «добавить небольшое изменение» в этот код, чтобы он запустил с сложностью времени n 3 - n 2 вместо нормального n 3 . Я не могу на всю жизнь понять это, и мне было интересно, что кто -то узнал. Я не думаю, что он говорит о методе Strassens.
с тех пор, как я посмотрел на это, возможно, это может воспользоваться тем фактом, что он заботится только о квадратной (диагональной) матрице. < /p>

void multiply(int n, int A[][], int B[][], int C[][]) {
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
C[j] = 0;
for (int k = 0; k < n; k++)
{
C[j] += A[k]*B[k][j];
}
}
}
}


Подробнее здесь: https://stackoverflow.com/questions/461 ... mprovement