推 cakeboy:是F heap用在dijkstra 可以把時間壓在O(e+nlogn) 01/18 22:51
→ aoqq12:可以問一下他是怎麼做嗎？ 01/18 22:53
→ aoqq12:有點沒概念 01/18 22:53
推 cakeboy:就是dijkstra 一開始不是要挑未拜訪頂點中距離成本最小的 01/18 22:56
→ cakeboy:所以用f-heap的delete min運算 花O(logn) 然後後面如果新 01/18 22:58
→ cakeboy:算出來的值比之前的小不是要替換嗎 所以相當於 f heap 01/18 22:58
→ cakeboy:的 decrease key 花O(1) for every(u,w) 這邊一共有e個邊 01/18 23:00
→ cakeboy:所以執行O(e)次,所以搭配adjacency list可以在O(e+nlogn) 01/18 23:02
推 listplayers:F heap用在dijkstra不是O(nlog(n+e))嗎?還是我記錯了? 01/18 23:02
→ aoqq12:!~!!!!太感謝了 我懂了 01/18 23:03
→ aoqq12:b heap 才是 01/18 23:03
→ aoqq12:f heap 可以少掉合併的時間 01/18 23:06
→ aoqq12:前幾題有人知道嗎 orz 01/18 23:18
→ cakeboy:kruskal 是eloge 邊少有利邊多就變n^2loge 01/18 23:21
→ aoqq12:可是他不是還是要每個都check到嗎 是用adj matrix 01/18 23:23
→ aoqq12:不論邊多或邊少 adj list才可以有差別? 01/18 23:24
推 cakeboy:我記得kruskal 是用union 看有沒有cycle 花logn 01/18 23:25
→ cakeboy:有e個邊 所以就eloge 01/18 23:26
→ aoqq12:嗯嗯對啊 可是我比較疑惑的點是 因為他用adj matrix 01/18 23:29
推 dy957:原PO說的V^2 感覺換個角度想就是E欸 我覺得答案是O(ElgV) 01/18 23:29
推 cakeboy:我說錯了一開始是先挑 min cost edge 用heap花 O(eloge) 01/18 23:30
→ aoqq12:所以 他每次找min edge都要掃過 adj matrix一次 01/18 23:30
→ aoqq12:!!!!對吼還可以排序 01/18 23:31
→ aoqq12:可是這樣會違反題意嗎 因為他說用adj matrix去做 01/18 23:31
推 cakeboy:一個圖最多邊c(n,2),用matrix的話應該只要看他有沒有相連 01/18 23:34
→ cakeboy:傳回應該只要o(1)不用全部找 01/18 23:34
→ aoqq12:嗯嗯有道理= = 我一直以為限制在adj matrix的方法內 01/18 23:36
推 cakeboy:所以只要check n(n-1)/2個邊 然後搭配union find這樣 不知 01/18 23:37
→ cakeboy:對不對 01/18 23:37
→ aoqq12:如果找最佳的應該是對啦 不過題意要是能在清楚點就好了 01/18 23:39
→ cakeboy:引線是因為用link list會浪費掉n+1的指標所以把它拿來當 01/18 23:40
→ cakeboy:引線,可以簡化中序追蹤 01/18 23:40
→ cakeboy:所以100個點就有101條引線 01/18 23:41
→ cakeboy:第四大題我覺得是錯,因為他說any sort algo 但是radix 01/18 23:43
→ cakeboy:counting sort不用nlogn 其實這提他寫一大堆,感覺是看關 01/18 23:44
→ cakeboy:鍵字 01/18 23:44
→ aoqq12:嗯嗯!! 太感謝啦 第四題對吼..他寫any= = 01/18 23:47
→ aoqq12:囧... 01/18 23:48
→ dy957:第四題根據補習班老師的說法 他說是錯的= = 01/18 23:54
→ dy957:應該是敘述出了問題 是因為comparison tree所以才nlgn吧 01/18 23:55
→ aoqq12:嗯嗯3q 01/19 01:25
→ privatewind:因為dijkstra需要找每次向外擴張最短的點 01/19 08:11
推 skill91002:cake大的講解，讓我更了解dijkstra's的運作了@@ 不然 01/19 16:03
→ skill91002:本來看MIT那本被搞得很亂 感謝! 01/19 16:04