Задача на сумму матриц
Допустим у меня есть некая матрица A размера q × q. Мне нужно найти сумму A + A2 + ... + An, и сложность нахождения такой суммы должна быть O(q3log(n)). Как это сделать?
Ответы (1 шт):
Автор решения: Harry
→ Ссылка
Сначала немного матричной математики...
Откуда совсем просто получается (I - единичная матрица)
и
Ну, а дальше - быстрое возведение в степень требует log(n) умножений. Каждое умножение - не будем умничать и звать на помощь Штрассена :) - выполняется за q3. Вычитание - за q2, обратная матрица - q3. Таким образом, в результате получается требуемое O(q3log(n))...