Сколько шагов нужно для умножения матриц n*n?

У меня есть странный вопрос в вопросе предыдущего года, а именно: если алгоритму требуется 21 шаг для умножения матриц 7 * 7, то сколько шагов потребуется для умножения матриц n * n?

Я попытался сделать умножение матриц 7 * 7 и подсчитал, сколько умножений сделано. Затем я попытался связать n умножений с шагами. Но это не работает .

От многих людей я слышал, что ответ равен 3n, но они не могут объяснить причину того, что ответ равен 3n.

Можете ли вы просто дать мне представление, как я могу решить этот вопрос?


algorithm matrix calculation multiplication problem-steps-recorder
person A Stranger    schedule 11.11.2018    source источник
comment
Больше похоже на (n-1) n/2.   -  person Willem Van Onsem    schedule 11.11.2018
comment
Объясните логику вашего решения   -  person A Stranger    schedule 11.11.2018
comment
Ну, вы перечисляете треугольник элементов, поэтому для этого требуется (n-1) n/2 шагов.   -  person Willem Van Onsem    schedule 11.11.2018
comment
Можете ли вы опубликовать ответ с объяснением деталей?   -  person A Stranger    schedule 11.11.2018

Ответы (1)


arrow_upward
2
arrow_downward

Учтите, что для каждой строки row.dot(column) вам нужно сделать одно и то же, и вы должны сделать это для каждой пары row.column, поэтому кажется, что каждое измерение даст вам 21/7=3 шагов, поскольку у вас есть 7 row.column пары, требующие в общей сложности 21 шагов.

person kabanus    schedule 11.11.2018