По теме: Возведение в степень кажется может быть выполнено за

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

умножений в конечном поле, но алгоритм Штрассена например дает ещё больше операций, а именно

. Умножение итоговой матрицы на вектор потребует в лучшем случае

умножений. Кстати, возможно ли так эффективно производить матрично-векторное перемножение для произвольных квадратных матриц?
В итоге, количество операций будет порядка

, где

-- стоимость умножения над

. Кратко эту оценку можно записать (оптимистично положив

) как

. Получилось почти тоже, что и у
Xaositect'а...
2
AndreyXYZЦитата:
мне необходимо получить оценку не хуже

Возможно ли это?
Да. Теоретически. Алгоритм мне не известен.
