這門 20 幾小時的視訊課程塞滿了需要上幾個月的電腦科學課程和面試準備教材。
這些內容直接基於講師上學期的私人程式設計訓練。
課程包含了可以幫助學生到 Google、特斯拉、亞馬遜和臉書這樣的大公司進行了一模一樣的面試的電腦科學內容。
對於參加線上課程的學生來說，沒有什麼是被刪減的; 這才是真正的交易: 我們從基礎開始，然後最終涵蓋”進階主題”，類似的課程迴避了 Heaps、 Graphs 和 Dijkstra 的最短路徑演算法。
課程會開始教你如何使用 Big O 符號來分析程式碼的時間和空間的複雜性。
涵蓋了遞迴的來龍去脈。 我們學習了一種解決任何困難編碼問題的五個步驟。
我們涵蓋了常見的程式設計模式。
我們實現了流行的搜尋演算法。
我們編寫了6 種不同的排序演算法: Bubble，Selection，Insertion，Quick，Merge，Radix Sort。
然後，我們改變方法，從頭開始實現我們自己的資料結構，包括連結串列(linked lists)、樹(trees)、堆(heaps)、雜湊表(hash tables)和圖表(graph)(graphs)。
我們學習走訪樹(traverse trees)和圖表，並涵蓋 Dijkstra 的最短路徑演算法。此課程還包括專門用於動態程式設計的整個部分。
https://softnshare.com/js-algorithms-and-data-structures-masterclass/
dijkstra資料結構 在 [考題] 103高考資訊處理-資料結構第6題- 看板Examination 的美食出口停車場
我好像摸出一點頭緒了,回來自問自答XD
若 G=(U,E)為一權重圖（weighted graph），每條邊的權重均不為負數，則單源最短路徑
問題（Single Source Shortest Path Problem）可以用著名的 Dijkstra 演算法求得，
回答下列問題：
(一)說明 Dijkstra 演算法的主要觀念。
(二)Dijkstra 演算法在最差情況下（Worst Case Analysis），下列三個功能 Insert、
Delete、Decrease_Key 各自需要執行的次數，可用 Big-Oh 符號表示。
(三)若是要在O(|E|+|V|log|V|)最差情況分析下的時間內執行 Dijkstra 演算法，請問該
選擇使用那種資料結構，並說明其原因。
第(二)小題>>
Insert Delete Decrease_Key
高點答案 O(|V|) O(|V|) O(|E|)
公職王答案 O(1) O(VlogV) O(1)
問題1:想請問哪個答案才是正確的?
以下我原來的想法(深藍色的部分)是錯的!
我自己是偏向高點的答案,
因為題目有說是在最差情況下的執行次數,
而 Dijkstra 演算法的資料結構如為一般heap,
insert/delete/decrease_key,所需花費的時間都是O(log n),
如使用F-heap,除了delete依舊需要O(log n),
其餘的所需花的時間都是O(1),
所以依題意我比較可以理解高點的答案.
後來再我多翻了幾次參考書,還是一樣偏向高點的答案,
但原因跟上面不一樣.
我新的想法是:
1.Dijkstra演算法可分為
Insert 用於加入新選擇的點
Delete 用於選出離出發點邊最小的點
Decrease_key 用於檢查邊,更新最短距離
2.Dijkstra演算法如果使用資料結構:鄰接串列 + Fibonacci heaps(F-heaps)
每次執行時間和執行次數為
每次執行時間 執行次數
Insert O(log|V|) O(|V|)
Delete O(1) O(|V|)
Decrease_key O(1) O(|E|)
3.總時間 = 每次執行時間*執行次數
= O(log|V|)*O(|V|) + O(1)*O(|V|) + O(1)*O(|E|)
= O(|V|log|V|+|V|+|E|) |V|太小可省略
= O(|E|+|V|log|V|)
從上面三點可以發現,
高點的答案是執行次數,
公職王的答案則是每次執行時間,
所以我覺得高點的答案比較切合題意!
而其中第三點可以回答第(三)小題,
如果所花總時間為O(|E|+|V|log|V|),
資料結構應為鄰接串列 + Fibonacci heaps
問題2:另外想請問為什麼Decrease_Key的時間複雜度是O(|E|)?
應該說Decrease_Key的執行次數是O(|E|),
因為Decrease_Key是用在"用於檢查邊,更新最短距離",
所以執行次數為邊的總和.
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 140.135.242.239
※ 文章網址: https://www.ptt.cc/bbs/Examination/M.1409997907.A.6B6.html
我把我的想法補充上來了,
其中有些地方其實我也不是十分確定我是不是對的,
如果有錯歡迎討論: DDDDD
※ 編輯: yearndeath (140.135.242.239), 09/07/2014 14:57:23
... <看更多>