Re: [理工] [資結]-台大98-軟體設計 對答
: 不好意思 因為文章太長他不給我貼 所以才砍一部分文章 sorry
: 想問一下這兩題 其中第3題的9-20格他不是都給ptr了嗎??
: 為何還要花O(n)啊?? 還有22 跟 26格不是一個填A另一個就要B嗎
: 因為假設sort是遞增min就O(1) max不就要O(n)嗎
: 因為要從第一個一到最後一個ptr
3-9，10，13，14
題目說 delete(L,p) deletes a object point by p from L
因為是singlist
A->X->B
若x為所指，想要刪除X必須知道前一個節點的位置
因此必須從兩端搜索，worst case是n/2
A->link=p->link;
delete p;
sort不sort是一樣的
而precessor要找到前一個節點，作法雷同。
至於9~20(除了9，10，13，14)
我本來就寫A阿，是O(1)
3-22，26
題目的第1.2行說
one root pointer one tail pointer
point to first and last node
: 至於最後一提的第3小提
: 還是不知道要選A or B以及選的理由
: 煩請解惑 謝謝
選A
因為A對每個邊都進行relax，這樣負值的邊也可以被考慮進去
而B每次選可到達但是最小的邊
如
4
-------
/ \
a---c---b
5 -2
由a點開始，選擇ab為最小邊後，
依據該演算法，
output ab最短路徑為5
但實際上ab最短路徑應為3
由此可知此演算法在邊值有負值時，將會有問題發生。
若是不了解可以參考 dijkstra's algo 跟 bellman's algo
http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm
http://en.wikipedia.org/wiki/Bellman-Ford_algorithm
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 61.216.173.134
推
02/16 21:30, , 1F
02/16 21:30, 1F
→
02/16 21:31, , 2F
02/16 21:31, 2F
推
02/16 23:44, , 3F
02/16 23:44, 3F
→
02/16 23:51, , 4F
02/16 23:51, 4F
→
02/16 23:52, , 5F
02/16 23:52, 5F
→
02/16 23:52, , 6F
02/16 23:52, 6F
討論串 (同標題文章)
本文引述了以下文章的的內容：
完整討論串 (本文為第 6 之 8 篇)：