0

Изучая разреженные матрицы (у которых большинство элементов не 0, а допустим x, и которые организованы в виде списка тринарных элементов, состояющих из двух индексов и значения), достаточно легко подобрать алгоритм для умножения двух матриц и подсчитать его сложность, которая будет о(n^3) при матрицах n*n, если x = 0.

По моему анализу, той же эффективности можно достичь при х != 0, но алгоритм будет намного сложнее.

Смысл примерно в том же, - мы циклично получаем строку, для каждой строки получаем каждый столбец, но сложность самого алгоритма уже зависит от того, как мы работаем с теми столбцами и строками, которые либо полностью наполненны значением х, либо частично. То есть, можно в отдельности считать количество элементов которые дадут х^2 и прибавлять их к нынешний сумме (новому элементу на месте i,j). Также в отдельности считать произведение х и реальных значений или вдоль строки или вдоль столбца пока не дойдем до индекса, где есть оба реальных значения, произведение которых нужно добавить к считаемой сумме.

То есть формула сумма для k от 0 до n (i,k)*(k,j) становится не линеарной.

Кто нибудь понял примерно тот алгоритм, который я прикинул? У меня не получается написать даже его примерный псевдокод.

Может кто-нибудь знает хорошие источники по данной теме или может накидать этот алгоритм в наиболее простом виде здесь?

1 ответ 1

2

Понял ли я алгоритм? нет.

Изучая разреженные матрицы (у которых большинство элементов не 0, а допустим x, и которые ... которая будет о(n^3) при матрицах n*n, если x=0

Как-то странно. Не 0, но вот при равном 0... При равных 0 элементах сложность точно O(n^2) - записать n^2 нулей.

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

А почитать - то классика (хоть и древняя): Писсанецки С. Технология разреженных матриц - в Интернете можно найти. Есть еще такая Matrix Template Library, можно посмотреть ее, но это очень профессиональный код, там просто так, с налета, не разобраться.

Ваш ответ

Нажимая на кнопку «Отправить ответ», вы соглашаетесь с нашими условиями использования и подтверждаете, что прочитали и поняли наши политику конфиденциальности и нормы поведения.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.