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

看板Grad-ProbAsk作者 (Firefighter)時間14年前 (2012/02/17 22:54), 編輯推噓1(1推 0噓 8→)
留言9則, 3人參與, 最新討論串1/1
1. http://ppt.cc/fnJO 2. http://ppt.cc/jpHL 我猜是1.E 2.B 純瞎猜...完全不知道why -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 42.72.160.41
推
02/18 01:13, , 1F
我的答案第一題是E 看每次呼叫perm都要N! 共N次
02/18 01:13, 1F
→
02/18 01:13, , 2F
所以是O(n*n!)
02/18 01:13, 2F
→
02/18 01:14, , 3F
第二題 我認為是B 因為他說有非常大的機率程式執行為
02/18 01:14, 3F
→
02/18 01:15, , 4F
O(logn) 非常小的機率p執行時間為O(n) 所以anortized
02/18 01:15, 4F
→
02/18 01:16, , 5F
(近似的意思) 程式執行當然會接近 O(logn)
02/18 01:16, 5F
→
02/18 01:17, , 6F
而且他提到的事已大量的輸入資料下去測 而不是拿單一
02/18 01:17, 6F
→
02/18 01:18, , 7F
一次的結果
02/18 01:18, 7F
→
02/18 10:27, , 8F
amortized analysis是均攤吧
02/18 10:27, 8F
→
02/18 11:46, , 9F
沒關係 我看得懂XD
02/18 11:46, 9F
‣ 更多 dunkjames 的文章
文章代碼(AID): #1FFce_Yf (Grad-ProbAsk)