時間複雜度我的是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

請您先登陸，再發跟帖！