重讀Dijkstra’s Algorithm有感

首先是確認了Dijkstra的發音，依Wikipedia的定義，要唸[ˈdɛɪkstra]。

以前我一直有兩個疑問：

1. O(E*logV)不是比O(V^2)大嗎？為啥變成O(E*logV)後較好？
2. 當heap內的元素會被更動值時，做起來不是很麻煩嗎？time complexity的影響為何沒有被認真討論？連帶使我懷疑那堆怪異的數字，O(V*logV + E*logV) 之類的。

愚笨的我在重讀Algo時終於想通上面兩件事了，

1. sparse graph的定義：|E| = o(|V|^2)，注意，是small-o，也就是說當 n 趨近於無限大時，|E|/(|V|^2) = 0，於是，E*logV還是比V^2小。若對此感到疑惑的話，不妨想想當|E| = |V|^k，其中 k 可以是比 2 小的任意正實數，也就是說，|V|^(1.9)的情況下，E*logV仍比V^2小。

   小時候自以為有讀懂small-o，第三遍讀到這個符號時，才真的體會到它的含義。如同我以前把worst case和Big-O弄混一樣，Big-O只是方便表示上界的符號，不等同於worst case。所以，average case的Big-O、best case的Big-O都很合理，沒有認合奇怪的地方。

2. 我被heap的insert/delete動作限制住想法，自以為只有insert/delete時才適合做heapify，但當我們更新heap內任一元素時，可以從這被更新的元素開始做heapify，所以heap內的元素可以任意被更新，僅需 O(logV) 的代價。事先用個 array/hash table 就可以記好 heap 內的元素，當要更新特定元素時 (e.g. 某個vertex)，O(1)的時間即能完成值的更新。

   沒想到到今天我才真的弄懂Dijkstra, MST的運作細節，以前碰到 priority queue 的更新維護細節時，都下意識地含糊帶過。也許下次再重讀Algo時，又會發現我還沒真的弄懂吧？

另外最近讀《勇闖資訊新未來：打造資訊科技的幕後英雄》時有讀到Dijkestra的介紹，順便記一下他給年輕科學家的建議：

１．別和你的同事競爭。
２．嘗試你能作的最困難議題。
３．選擇對科學發展有益切題的研究方向，不要與科學界妥協。

現階段來說，第三點可能是我最需要的，要能保有自己的價值觀而不與大環境妥協，相當困難。然而，我想一個可貴且稀少的學者，應該具有這樣的氣魄。若我的觀念錯了，也只不過是少一個一般學者，對大環境來說沒什麼損失。不管前述看法是否正確，目前我還太嫩了，仍需要經驗來確認或修正自己的想法。