时间复杂度我的是O(n), 空间复杂度也是O(n).

来源: 612309 于 2011-12-11 19:53:52 [] [博客] [旧帖] [给我悄悄话] 阅读数 : (322 bytes)
本帖于 2011-12-12 02:34:33 时间, 由版主 笑比哭好 编辑

时间复杂度我的是O(n), 单个节点空间复杂度也是O(n)，未优化系统整体空间复杂度是O(n^2).如果用共享内存，系统整体空间复杂度降为O(n)。

况且，复杂度O(n^2)，还属于P问题，不是NP-hard. 是计算机算法可接受范围。而你的答案跟不不符合要求，没有资格谈空间，时间复杂度。


所有跟帖： 

• 其实，我的空间复杂度只是O(1)而已. -612309- ♀ 给 612309 发送悄悄话 612309 的博客首页 (109 bytes) () 12/11/2011 postreply 20:00:30

• 单个结点需要递归前面所有结点的结果, 是NX(N-1), 全部结点复杂度O(n^3) -a7a8- ♀ 给 a7a8 发送悄悄话 (0 bytes) () 12/12/2011 postreply 06:08:55

• 更正一下,单个结点因为递归所有前面结点,复杂度为∑N! -a7a8- ♀ 给 a7a8 发送悄悄话 (0 bytes) () 12/12/2011 postreply 06:55:46

请您先登陆，再发跟帖！