作者joeboy (揪立)
看板Grad-ProbAsk
標題[理工] 100台大電機DS
時間Thu Feb 2 00:24:49 2017
http://i.imgur.com/Kh0DSTB.jpg
想問第8的C選項
有看到一個可以解決的演算法
Kadane's algorithm
雖然之前有人推文說可以用singly linked list實作
但是google都找不到實作法耶
順便問一下A選項是O(1)嗎？
http://i.imgur.com/mM5xRPJ.jpg
http://i.imgur.com/TS8dYoS.jpg
ADT關心的應該是做什麼做什麼，而不用去看該怎麼實作吧？
前人的答案給AE 我是AD想問看看
再問看看DS中的tree該看成有向還是無向呢QQ
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 42.73.88.28
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1485966292.A.F3F.html
推 krusnoopy: kadane 就只是從頭掃到尾記錄一些東西而已,用link list 02/02 01:55
→ krusnoopy: 當然也可以 02/02 01:55
推 krusnoopy: D說:怎麼用應該被藏起來(藏起來怎麼用....) 02/02 01:57
→ krusnoopy: E說實做應該被隱藏起來,所以選E不選D 02/02 01:58
→ aa06697: A是O(1). delete才會是O(n) 02/02 08:36
推 k1992313: A因該是敘述的問題吧，他已經給定一個位置，所以才是O(1 02/02 10:26
→ k1992313: )，插入任意位置應該也是要O(n)? 02/02 10:26
→ aa06697: 回樓上 yes 任意位置的話insert delete都是O(n) 02/02 11:40
→ z83ul6: tree無向加一 02/07 17:28