Detail of message

Online Judge

Problem Set

Authors

Online Contests

User

Re:是不是 m(k!) 个状态更加自然？这样时间复杂度是O( m(k!) ) 空间复杂度是 O(mk)

Posted by bobobo at 2009-10-03 01:56:52 on Problem 2978
In Reply To:是不是 m*(k!) 个状态更加自然？这样时间复杂度是O( m*(k!) ) 空间复杂度是 O(mk) Posted by:bobobo at 2009-10-03 01:37:45

> 比 O( m*(2^k)*k ) 易于理解 且状态数更少 赫赫

错了... 枚举k!种可能 每种可能的时间复杂度为O(m*k) 总时间复杂度是 O(m*k*(k!))...
但是记录状态的空间复杂度为O(mk) 用滚动数组可以达到O(k)

Followed by:

Post your reply here: