[理工] 資結 permutation的時間複雜度

[q5332159 (chiu)]

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 字元
→ FRAXIS: 而且每個輸出都可以在 O(n) 的時間內找出來
→ q5332159: 那我是不是寫錯了?應該是總共會進入第一個if n!次?><
→ q5332159: 每個輸出都可以在 O(n) 的時間內找出來是因為else中的迴
→ q5332159: 圈嗎？
推 sarsman: 沒寫錯，進入第一個迴圈的話就只是print表格，頂多是O(n)
→ sarsman: O(n!)的部份是for中呼叫perm的次數
→ q5332159: 了解~感謝大家