Возведение Матрицы в степень: различия между версиями
Материал из Algocode wiki
Глеб (обсуждение | вклад) |
Глеб (обсуждение | вклад) |
||
Строка 2: | Строка 2: | ||
$A^{x} = A^{x - 1}\cdot A = A \cdot A \cdot \dots \cdot A$ | $A^{x} = A^{x - 1}\cdot A = A \cdot A \cdot \dots \cdot A$ | ||
+ | |||
+ | ==Быстрое возведение в степень== | ||
+ | |||
+ | Мы уже знаем, что такое быстрое возведение в степень, заметим что для его применения мы требовали одну вещь $((A \cdot A) \cdot A) \cdot A = A^2 \cdot A^2$, но как мы знаем для матриц верно свойство $A \cdot (B \cdot C) = (A \cdot B) \cdot C$ | ||
+ | |||
+ | Тогда мы можем просто написать для матриц быстрое возведение в степень - Оно будет работать за $O(log(n) \cdot size^3)$, если нужно матрицу $A \in Mat_{size \ size}$ возвести в $n$-ую степень | ||
+ | |||
+ | {{Автор|Глеб Лобанов|glebodin}} |
Текущая версия на 11:19, 30 октября 2019
Определение
$A^{x} = A^{x - 1}\cdot A = A \cdot A \cdot \dots \cdot A$
Быстрое возведение в степень
Мы уже знаем, что такое быстрое возведение в степень, заметим что для его применения мы требовали одну вещь $((A \cdot A) \cdot A) \cdot A = A^2 \cdot A^2$, но как мы знаем для матриц верно свойство $A \cdot (B \cdot C) = (A \cdot B) \cdot C$
Тогда мы можем просто написать для матриц быстрое возведение в степень - Оно будет работать за $O(log(n) \cdot size^3)$, если нужно матрицу $A \in Mat_{size \ size}$ возвести в $n$-ую степень
Автор конспекта: Глеб Лобанов
По всем вопросам пишите в telegram @glebodin