Форум программистов, компьютерный форум CyberForum.ru

Бинарное возведение матрицы в степень - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 15, средняя оценка - 4.87
AncinetHero
49 / 49 / 3
Регистрация: 22.05.2011
Сообщений: 326
19.03.2012, 15:16     Бинарное возведение матрицы в степень #1
Подскажите, пожалуйста, как оно реализуется, причем, пишут, что если матрица размером n*n, и нужно возвести ее в степень k - сложность O( n^3 log k ).
O( n^3 * k ) написать не сложно, а вот как тут применить бинарное возведение? Может я не знаю каких-то тождеств?

Добавлено через 33 минуты
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
19.03.2012, 15:16     Бинарное возведение матрицы в степень
Посмотрите здесь:

Возведение a в степень b C++
возведение в степень C++
C++ Возведение в степень
C++ Возведение в степень
C++ Бинарное и блочное возведение в степень С++
C++ Возведение матрицы в степень
Возведение матрицы в степень C++
C++ Возведение матрицы в степень

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
vndtta
66 / 43 / 5
Регистрация: 17.10.2011
Сообщений: 146
Завершенные тесты: 1
19.03.2012, 16:03     Бинарное возведение матрицы в степень #2
http://ru.wikipedia.org/wiki/Алгоритм_Штрассена
вот тут описано
AncinetHero
49 / 49 / 3
Регистрация: 22.05.2011
Сообщений: 326
20.03.2012, 01:19  [ТС]     Бинарное возведение матрицы в степень #3
Меня интересует именно бинарное возведение
Yandex
Объявления
20.03.2012, 01:19     Бинарное возведение матрицы в степень
Ответ Создать тему
Опции темы

Текущее время: 21:51. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru