為什麼這篇Permutation 時間複雜度鄉民發文收入到精華區：因為在Permutation 時間複雜度這個討論話題中，有許多相關的文章在討論，這篇最有參考價值！作者q5332159 (chiu)看板Grad-ProbAsk標題[理工] 資結 permutati...
https://i.imgur.com/I9pv4MU.jpg
做如圖的permutation程式的時間複雜度是O(n*n!)
這是怎麼算出來的？
O(n*n!)中的n是因為總共會進入第一個if n次嗎？
那n!是怎麼來的？
謝謝大家解答~~
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 27.247.33.144
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1508034504.A.FD8.html
推 FRAXIS: n! 是因為有 n! 個輸出， n 是因為每次輸出有 n 字元 10/15 10:53
→ FRAXIS: 而且每個輸出都可以在 O(n) 的時間內找出來 10/15 10:53
→ q5332159: 那我是不是寫錯了?應該是總共會進入第一個if n!次?>< 10/15 11:21
→ q5332159: 每個輸出都可以在 O(n) 的時間內找出來是因為else中的迴 10/15 11:23
→ q5332159: 圈嗎？ 10/15 11:23
推 sarsman: 沒寫錯，進入第一個迴圈的話就只是print表格，頂多是O(n) 10/15 11:29
→ sarsman: O(n!)的部份是for中呼叫perm的次數 10/15 11:32
→ q5332159: 了解~感謝大家 10/15 19:41