Изменения

Перейти к: навигация, поиск

Динамическое программирование по профилю

31 байт убрано, 01:22, 14 января 2013
Задача о симпатичных узорах
''' Оценка памяти : '''
<tex>O(2^{2n}+2^{2n}\times m)</tex>, так же можно заметить что в массиве <tex>a</tex> для k состояния нам нужно только k-1 состояние, при такой реализации нужно будет <tex>O(2^{2n})</tex>. Еще можно не считать массив d, а просто каждый раз перепроверять можем ли мы перейти в это состояние в итоге потребуется <tex>O(2\times 2^n)</tex> памяти, но нам потребуется больше времени <tex>2^{2n}\times m\times f(i,j)</tex>, где <tex>f(i,j)</tex> время проверки возможности перехода из i в j, обычно проверка равна равно n и тогда время получается <tex>O(2^{2n}\times m\times n)</tex>.
== См. также ==
27
правок

Навигация