[理工] 100台大電機DS 對答案
挖個舊文
有幾題希望大家能夠幫忙釋疑一下~
: 3.A
: p*O(n)+(1-p)*O(log(n))
: amortized runtime = ─────────── ≒ O(log(n))
: 1
: 應該和Ｋ沒關係，Ｋ次input代表run Ｋ次
我查到的armotized analysis是說他不考慮機率
而是可能的worst case
如果照此說法答案應該是O(pn)才對
因為這個算法看起來好像是找average case才對?
:6. 我選E
:
: ...c...f...l...n...w... 1:number
: / / | \ \ 2:which
: a...o o...u .e. 1 2 3:can
: / \ | | | 4:collisions
: 3 4 5 6 a... 5:following
: | 6:function
: ...d...s... 7:lead
: / \ 8:least
: 7 8
:
: 一個顏色是一個branch node 所以有六個？
他跟我對題目的理解完全不同
我是覺得應該每個字母都會有一個node
在該層重複的則會扣掉
而不是像上面寫的搜尋到一半就可以直接得知結果
也就是以lead和least為例
l
|
e
|
a
/ \
..s. d..
| |
t 1
|
1
光這個就會產生6個internal node
不知道理解有沒有問題
雖然最後答案也是一樣啦XD
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 61.60.217.209
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1449498610.A.35C.html
討論串 (同標題文章)
完整討論串 (本文為第 3 之 3 篇)：