Re: [問題] 遞迴排列-- 避免重複字元的遞迴

看板C_and_CPP作者 (Godhere)時間15年前 (2010/03/18 22:54), 編輯推噓6(6推 0噓 21→)
留言27則, 5人參與, 最新討論串6/6 (看更多)
好吧 這麼多人這麼好心分享 那小弟也不藏私了 給大家看看最簡單也最有效率的作法 其實只要自己劃劃遞迴樹出來大概都能觀察到吧 -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 125.231.1.177
推
03/18 23:40, , 1F
看起來我的應該比你有效率不少 :p
03/18 23:40, 1F
→
03/18 23:46, , 2F
何以見得呢?
03/18 23:46, 2F
→
03/19 00:20, , 3F
被通知原來跟suhorng大code演算法是一樣 Orz
03/19 00:20, 3F
推
03/19 01:04, , 4F
一個是長度的長度次方, 一個是種類數的總長次方
03/19 01:04, 4F
→
03/19 01:05, , 5F
嗯 不過你的底有些會 skip 掉, 我錯了, 應該不會差太多
03/19 01:05, 5F
→
03/19 03:07, , 6F
我覺得這個演算法是時間是O(n!) n是字串長度
03/19 03:07, 6F
→
03/19 03:09, , 7F
O(N!)己經是這個問題的lower bound了
03/19 03:09, 7F
→
03/19 06:37, , 8F
遞迴排列程式有到O(N!)嗎?不是O(N^k)就不錯了?
03/19 06:37, 8F
→
03/19 06:39, , 9F
我想是你們堅持要打破遞迴直接數每個數出現次數,才會O(N!)..
03/19 06:39, 9F
→
03/19 06:41, , 10F
但其實可以只比較這次呼叫所處理的值與鄰近值的關係,讓其他
03/19 06:41, 10F
→
03/19 06:42, , 11F
數值由遞迴呼叫處理掉,這樣只是O(N^2)或O(N^3).
03/19 06:42, 11F
推
03/19 11:21, , 12F
output complexity 就是 O(n!) 了, 弄個 O(n^3) 來開開眼界
03/19 11:21, 12F
→
03/19 18:14, , 13F
哈哈, 我的方法是 O(n^n) XDDD
03/19 18:14, 13F
推
03/20 05:53, , 14F
哎呀,我犯了大錯了,不管是否遞迴,真是O(N^N)沒錯
03/20 05:53, 14F
→
03/20 05:54, , 15F
然後我所不解的是,在大家都O(N^N)前提下,計較效率,即執行時
03/20 05:54, 15F
→
03/20 05:55, , 16F
間,要幹什麼呢?這時候應該是看能節用多少空間吧
03/20 05:55, 16F
→
03/20 06:48, , 17F
因為 (n/2)^n 和 n^n complexity 還是差很多的
03/20 06:48, 17F
→
03/20 06:49, , 18F
像是重複排列的 case, 能只考慮種類數就會有不少 improve
03/20 06:49, 18F
推
03/20 06:51, , 19F
因為很可能種類數只有字串總長的一半
03/20 06:51, 19F
→
03/20 11:13, , 20F
事實上我的程式時間是O(n!) 空間是O(1)
03/20 11:13, 20F
→
03/20 11:15, , 21F
ya你的程式的所需空間看起來反而是最多了
03/20 11:15, 21F
推
03/21 00:55, , 22F
確定是 n! 嗎? :p
03/21 00:55, 22F
→
03/21 01:20, , 23F
不重複排列約n!吧? Y的呼叫次數 n個比n-1個多n倍再加1次
03/21 01:20, 23F
→
03/21 01:27, , 24F
而y的方法我就不懂了,直接拷貝不能跑...XD
03/21 01:27, 24F
→
03/21 06:36, , 25F
Slen==0成立時Slen+1必為1,那麼(*ls)->str[1]一定會出錯
03/21 06:36, 25F
→
03/21 06:45, , 26F
不管任何方法最花時間的還是印出的動作,
03/21 06:45, 26F
→
03/21 06:48, , 27F
要省空間的話,用迴圈解似乎能寫出更省的?
03/21 06:48, 27F
※ 編輯: YesIam118 來自: 125.231.5.145 (03/26 20:34)
‣ 更多 YesIam118 的文章
文章代碼(AID): #1BeZwDYi (C_and_CPP)
討論串 (同標題文章)
完整討論串 (本文為第 6 之 6 篇)：
排序： 最新先 | 最舊先 | 留言數
在新視窗開啟完整討論串 (共6篇)
‣ 更多 YesIam118 的文章
文章代碼(AID): #1BeZwDYi (C_and_CPP)