時間復雜度:指的是算法隨著輸入量增大,運行時間的增長率

常見的幾種大O記法:O(logN)、O(N)、O(NlogN)、O(N^2)、O(N!)

插入排序中提到了鏈表和數組,是最基礎的數據結構,比如Java的HashMap就涉及到了鏈表和數組。理解這兩個在插入、刪除和查找操作的時間復雜度比較。有一個點是關于計算機內存的物理結構部分,一個基本類型在內存中怎么表示,數組又是怎么表示,鏈接在內存中是怎么存在的。一方面。理解數據結構的邏輯結構,但也要明白它們的物理存儲形式。

遞歸的概念:函數調用自身。基線和遞歸項的形式是很優美的,不能把基準條件漏了,否則立馬Java爆棧。這里涉及到了一個數據結構:棧,和計算機中的基本部分:函數調用在計算機中是怎么實現的,參考《深入理解計算機系統》相關部分。

快排:分治和遞歸怎么理解?遞歸是一種實現,分治是一種策略。這里分治是把原問題分解成兩部分子問題,然后利用遞歸操作子問題。快排的平均時間復雜度是O(NlogN),但在最壞情況:有序(正序或逆序)變成了O(N^2)。這里一個關鍵優化部分是怎么選擇pivot,可參考更理論化的算法書籍:《數據結構與算法分析:C語言描述》《算法導論》

哈希表在各種語言中屬于常用的集合。Java中的HashMap、HashTable,Python中的字典等,JSON數據格式也是。關鍵詞:hash函數計算索引,解決沖突的方法:鏈或者再次哈希等,負載因子(load factor)進行resize操作。

BFS:最好理解的是用鏈表來連接鄰居,這樣在當前元素出隊時,對它的鄰居們進行遍歷入隊操作就好理解了。隊列在BFS中是作為對所有元素進行遍歷的結構,從起點入隊開始,循環直到隊列為空,循環中對當前出隊元素的鄰居們進行入隊操作以及附加判斷。運行時間怎么理解是O(V+E),首先是對所有節點進行遍歷一次,在訪問鄰居時,相當于把從當前節點到它所有鄰居節點通過邊訪問一次,這就是時間復雜度的來源。

Dijkstra算法是針對DAGs(有向無環圖)求解單源最短路徑。每一次循環找還沒有處理的節點中距離最短的節點,關鍵操作:從起點到當前節點的鄰居節點的距離,能不能通過當前節點中轉減少距離,即不直接到達,先到當前節點再到鄰居節點的距離和是不是比直接到達的距離小,若小,則更新最短距離。這里怎么保證最終是最優的呢?用BFS來看,從起點的第一步可達的開始,就更新最短距離,慢慢擴大起點經過兩條邊到達的節點,最后的是最最優的。保證前面每一步是最優更新。至于是屬于動態規劃還是貪心,我還沒理解。。。

貪心算法:經典的區間問題:每一次都選擇當前最優,這里是區間結束最早的時間段,這樣最后最優。但不是所有都是最優。set-convering problem昨天一直在糾結它的時間復雜度問題,我的理解是直接解法:O(2^n),貪心:O(m*n)(m是state數,是station數),而書中給出是如下 enter image description here

動態規劃:0-1背包問題采用的圖解方法是最好理解,后面的公式也是來的水到渠成,推薦這一部分。最長公共子序列就不明白了。。。

KNN:完全是多余的部分,嚴格來說不是機器學習算法,沒有經過train和test,建議參考李航博士《統計學習方法》,第二版也出版了,有興趣的可以購進。我是讀到SVM部分就掛,那些個數學公式涉及的優化部分看不太懂。

最后:推薦了幾顆樹(紅黑樹、二叉搜索樹等),倒排索引,傅里葉變換(讓我想起了V2的一個帖子),并行算法不知道說了啥,MapReduce,好吧我再下載一次,做好準備再看,其它的我就不說了。

整本書,Github上有其它語言的實現,我以為只有Python,雖然Python也能寫,但是懶得打開Pycharm。

我一直看的是原理和時間復雜度,沒怎么注意代碼,書刷過到LeetCodo刷題吧。

隨便寫的筆記,是自己的理解,有一些還是有問題不完全理解,歡迎指出。