[理工] [資結] 請教2題時間複雜度

[dunkjames (Firefighter)]

1. http://ppt.cc/fnJO

2. http://ppt.cc/jpHL

我猜是1.E 2.B 純瞎猜...完全不知道why

--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 42.72.160.41
推 cksh3300110:我的答案第一題是E 看每次呼叫perm都要N! 共N次
→ cksh3300110:所以是O(n*n!)
→ cksh3300110:第二題 我認為是B 因為他說有非常大的機率程式執行為
→ cksh3300110:O(logn) 非常小的機率p執行時間為O(n) 所以anortized
→ cksh3300110:(近似的意思) 程式執行當然會接近 O(logn)
→ cksh3300110:而且他提到的事已大量的輸入資料下去測 而不是拿單一
→ cksh3300110:一次的結果
→ suhorng:amortized analysis是均攤吧
→ dunkjames:沒關係 我看得懂XD