[理工] 100台大電機丙 第一題

[angel861047 (你逆)]

大家好想要請教一下，爬文答案是E

http://i.imgur.com/g42qaAZ.png

http://i.imgur.com/gA4c9Eo.png

http://i.imgur.com/hU4Oo7D.png

'*********************
'剛剛發現漏貼一張sorry
'*********************
http://i.imgur.com/CJCEOHC.png

http://i.imgur.com/svnagSd.png


不知道為啥我跑完一次之後變成n!，想問大家我是不是哪裡漏了沒考慮到?



--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 36.236.38.21
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1484276538.A.E9E.html
推 cshcsh6847: 你每個K後面寫的是那個loop的還是加總的呢？
回cshcsh6847 K後面那個是第一次進去for的i
推 yupog2003: 我認為你漏掉swap的time complexity了？
→ yupog2003: 我算了兩個版本，一個是有包含swap的，一個沒有
→ yupog2003: 我發現不包含swap的那個跟你一樣
→ yupog2003: 包含swap：T(n)=(n-1)[T(n-1)+1], T(n)=O(n*n!)
→ yupog2003: 不包含swap:T(n)=(n-1)T(n-1)，T(n)=n!
→ yupog2003: 以上兩個的T(1)=n
→ yupog2003: 但我其實也沒很肯定到底要不要包含swap，不過這兩種版
→ yupog2003: 本硬要在選項選的話，似乎(E)選項都是最近的？
→ yupog2003: 我看你的推導過程感覺不出什麼問題就是了
→ yupog2003: 補充說明一下，我這邊的n其實不是題目給的n，應該是
→ yupog2003: n-k才對，就是他們兩個的差值，我重寫好了
→ yupog2003: 令x=n-k
→ yupog2003: 包含swap:T(x)=(x-1)[T(x-1)+1], T(1)=n, T(n)=n*n!
→ yupog2003: 不包含swap:T(x)=(x-1)T(x-1), T(1)=n, T(n)=n!
→ yupog2003: 阿阿上面應該都要用big-Oh包起來才對
推 krusnoopy: 印出所有的排列組合,有n!種,每一種都要印出來花n,所以O
→ krusnoopy: (n!*n)
推 krusnoopy: 我沒仔細看,可能沒考慮到印一次花O(n)吧
→ angel861047: 感謝大家回覆我先看一下@@
※ 編輯: angel861047 (36.236.38.21), 01/13/2017 15:31:58
→ yupog2003: 我找到原因了，其實這個程式根本是錯的，他沒辦法輸出
→ yupog2003: 所有的permutation
→ yupog2003: else的那個for迴圈要用for (i=k;i<n;i++)才會正確輸出
→ yupog2003: 所有permutation，他這樣寫只會輸出(n-1)!個字串
→ yupog2003: 所以每個char算O(1)的話，的確是原po那樣導的沒錯
→ yupog2003: 但是直覺來說我覺得k大的解釋最好，因為考試根本無法
→ yupog2003: 驗證到這麼細，就是在考k大說的觀念而已
→ yupog2003: http://imgur.com/a/a709Y 注意上下兩個版本的for迴圈
的確是直接用K大那樣解最快XD，謝謝!
※ 編輯: angel861047 (36.236.38.21), 01/13/2017 18:30:56