思路
- 遍歷常見的算法思路
- 遍歷常見的數(shù)據(jù)結(jié)構(gòu)
- 空間和時(shí)間的交換（哈希表）
- 預(yù)處理信息（排序）
- 在瓶頸處尋找答案（O(nlogn)+O(n2)罪郊；O(n3)）
實(shí)際編寫問題
- 極端條件的判斷
數(shù)組為空？字符串為空凿可？數(shù)量為0敛瓷？指針為null蛇受？
- 代碼規(guī)范（變量名）
- 模塊化敞斋，復(fù)用性
解密時(shí)間復(fù)雜度大O
- O(nlogn+n) = O(nlogn)
- O(nlogn+n^2) = O(n^2)
- O(AlogA+B)不變
對鄰接表實(shí)現(xiàn)的圖進(jìn)行遍歷：
時(shí)間復(fù)雜度：O(V+E)
數(shù)據(jù)規(guī)模的概念
前提：如果想在1s之內(nèi)解決問題：
- O(n2)的算法可以處理大約104級別的數(shù)據(jù);
- O(n)的算法可以處理大約10^8級別的數(shù)據(jù);
- O(nlogn)的算法可以處理大約10^7級別的數(shù)據(jù)
空間復(fù)雜度
- 多開一個(gè)輔助的數(shù)組：O(n);
- 多開一個(gè)輔助的二維數(shù)組：O(n^2);
- 多開常數(shù)空間：O(1);
注意：遞歸的調(diào)用是有空間代價(jià)的，遞歸調(diào)用的深度就是空間的復(fù)雜度恼除。
