推 ledia:看起來我的應該比你有效率不少 :p 03/18 23:40
→ YesIam118:何以見得呢? 03/18 23:46
→ YesIam118: 被通知原來跟suhorng大code演算法是一樣 Orz 03/19 00:20
推 ledia:一個是長度的長度次方, 一個是種類數的總長次方 03/19 01:04
→ ledia:嗯 不過你的底有些會 skip 掉, 我錯了, 應該不會差太多 03/19 01:05
→ YesIam118:我覺得這個演算法是時間是O(n!) n是字串長度 03/19 03:07
→ YesIam118:O(N!)己經是這個問題的lower bound了 03/19 03:09
→ yauhh:遞迴排列程式有到O(N!)嗎?不是O(N^k)就不錯了? 03/19 06:37
→ yauhh:我想是你們堅持要打破遞迴直接數每個數出現次數,才會O(N!).. 03/19 06:39
→ yauhh:但其實可以只比較這次呼叫所處理的值與鄰近值的關係,讓其他 03/19 06:41
→ yauhh:數值由遞迴呼叫處理掉,這樣只是O(N^2)或O(N^3). 03/19 06:42
推 ledia:output complexity 就是 O(n!) 了, 弄個 O(n^3) 來開開眼界 03/19 11:21
→ suhorng:哈哈, 我的方法是 O(n^n) XDDD 03/19 18:14
推 yauhh:哎呀,我犯了大錯了,不管是否遞迴,真是O(N^N)沒錯 03/20 05:53
→ yauhh:然後我所不解的是,在大家都O(N^N)前提下,計較效率,即執行時 03/20 05:54
→ yauhh:間,要幹什麼呢?這時候應該是看能節用多少空間吧 03/20 05:55
→ ledia:因為 (n/2)^n 和 n^n complexity 還是差很多的 03/20 06:48
→ ledia:像是重複排列的 case, 能只考慮種類數就會有不少 improve 03/20 06:49
推 ledia:因為很可能種類數只有字串總長的一半 03/20 06:51
→ YesIam118:事實上我的程式時間是O(n!) 空間是O(1) 03/20 11:13
→ YesIam118:ya你的程式的所需空間看起來反而是最多了 03/20 11:15
推 ledia:確定是 n! 嗎? :p 03/21 00:55
→ rephansu:不重複排列約n!吧? Y的呼叫次數 n個比n-1個多n倍再加1次 03/21 01:20
→ rephansu:而y的方法我就不懂了,直接拷貝不能跑...XD 03/21 01:27
→ rephansu:Slen==0成立時Slen+1必為1,那麼(*ls)->str[1]一定會出錯 03/21 06:36
→ rephansu:不管任何方法最花時間的還是印出的動作, 03/21 06:45
→ rephansu:要省空間的話,用迴圈解似乎能寫出更省的? 03/21 06:48
※ 編輯: YesIam118 來自: 125.231.5.145 (03/26 20:34)