Изучая разреженные матрицы (у которых большинство элементов не 0, а допустим x, и которые организованы в виде списка тринарных элементов, состояющих из двух индексов и значения), достаточно легко подобрать алгоритм для умножения двух матриц и подсчитать его сложность, которая будет о(n^3)
при матрицах n*n
, если x = 0
.
По моему анализу, той же эффективности можно достичь при х != 0
, но алгоритм будет намного сложнее.
Смысл примерно в том же, - мы циклично получаем строку, для каждой строки получаем каждый столбец, но сложность самого алгоритма уже зависит от того, как мы работаем с теми столбцами и строками, которые либо полностью наполненны значением х, либо частично. То есть, можно в отдельности считать количество элементов которые дадут х^2
и прибавлять их к нынешний сумме (новому элементу на месте i,j).
Также в отдельности считать произведение х и реальных значений или вдоль строки или вдоль столбца пока не дойдем до индекса, где есть оба реальных значения, произведение которых нужно добавить к считаемой сумме.
То есть формула сумма для k от 0 до n (i,k)*(k,j)
становится не линеарной.
Кто нибудь понял примерно тот алгоритм, который я прикинул? У меня не получается написать даже его примерный псевдокод.
Может кто-нибудь знает хорошие источники по данной теме или может накидать этот алгоритм в наиболее простом виде здесь?