化思路是極簡)
空間復雜度 O(n) 算法執(zhí)行過程中額外申請的存儲空間不包括輸入數(shù)據(jù)空間優(yōu)化技術從空間復雜度的角度進行空間優(yōu)化時顧名思義就是讓空間復雜度不復雜思路就是極簡不額外申請不留的銷毀/釋放只留當前所需不得不留的壓縮。什么是空間復雜度數(shù)組arr 有 1 億個元素都叫total。那么數(shù)組的空間復雜度O(1)。因為不管 arr 有 1 個元素還是 1 億個total 就一個變量。for x in arr: total x return total # 空間復雜度 O(1)不管 arr 多大total 始終一個變量包含一億個 int的 數(shù)組空間復雜度算法層面O(1)沒開新數(shù)組數(shù)組本身占用內(nèi)存1 億 × 4 字節(jié) 400 MB跟算法無關實際占的物理空間叫footprint不等于空間復雜度。又開個等長數(shù)組呢空間復雜度變成O(1億)了因為額外開了個和輸入一樣大的數(shù)組。def copy(arr): return [x for x in arr] # 空間復雜度 O(n)額外開了一個等長數(shù)組算法的空間復雜度O(n)就是給這個算法額外申請多大空間快速排序的空間復雜度O(log n)—— arr 是輸入不算遞歸棧是額外開的算。隨著遞歸分區(qū)棧層數(shù)加深后進先出彈出后棧幀銷毀遞歸棧呆著的內(nèi)存空間是額外申請的。def quicksort(arr): quicksort_helper(arr, 0, len(arr)-1) # 遞歸棧給這個遞歸棧申請多大空間呢上面知道數(shù)組的空間復雜度是O(1)分區(qū)1次棧層數(shù)1平均情況下O(log n)層那么快速排序需要的臨時空間——平均空間復雜度就是O(log n)。最壞空間復雜度是O(n2。數(shù)據(jù)實際占的空間有沒有用有用但它在另一個層面叫內(nèi)存占用 / footprint不叫空間復雜度。工程上關心的幾個真實指標指標含義例子字面量空間數(shù)據(jù)結構實際占的字節(jié)struct Node { int val; Node* next; }占 16 字節(jié)空間復雜度算法額外開的空間遞歸棧、臨時數(shù)組駐留集RSS進程實際占的物理內(nèi)存看top命令對象頭開銷每個對象的元數(shù)據(jù)Java開銷小Python開銷大整個算法占用的空間≈數(shù)據(jù)結構實際占的字節(jié)算法額外開的空間進程實際占的物理內(nèi)存每個對象的元數(shù)據(jù)常見算法 / 數(shù)據(jù)結構復雜度速查表1、基礎數(shù)據(jù)結構數(shù)據(jù)結構 / 操作時間平均時間最壞空間適用場景數(shù)組按下標訪問O(1)O(1)O(n)隨機訪問順序查找O(n)O(n)O(1)無序線性查找二分查找O(log n)O(log n)O(1)有序數(shù)組冒泡 / 選擇 / 插入排序O(n2)O(n2)O(1)小數(shù)據(jù)、教學歸并排序O(n log n)O(n log n)O(n)穩(wěn)定排序、大數(shù)據(jù)快速排序O(n log n)O(n2)O(log n)通用排序首選堆排序O(n log n)O(n log n)O(1)原地排序、Top K哈希表查找O(1)O(n)O(n)鍵值映射BST二叉搜索樹O(log n)O(n)O(n)有序數(shù)據(jù)AVL / 紅黑樹O(log n)O(log n)O(n)平衡有序B 樹 / B 樹O(log n)O(log n)O(n)磁盤存儲、數(shù)據(jù)庫索引跳表O(log n)O(n)O(n)有序集合、RedisTrie前綴樹O(m)O(m)O(Σ·m)字符串前綴、自動補全并查集路徑壓縮O(α(n)) ≈ O(1)O(log n)O(n)連通性問題2、按問題選數(shù)據(jù)結構的決策樹速記同一個問題不同數(shù)據(jù)結構空間差很多存 1000 個點、10000 條邊的圖鄰接表O(VE) 1.1 萬鄰接矩陣O(V2) 100 萬差了將近 100 倍所以稀疏圖千萬別用鄰接矩陣。需求選查第 K 大 / 動態(tài) Top K堆范圍求和 單點修改樹狀數(shù)組 / 線段樹前綴匹配Trie連通性判斷并查集最短路Dijkstra / SPFA字符串匹配KMP / Z 算法區(qū)間最值ST 表 / 線段樹緩存 / 鍵值查找哈希表 LRU充分理解空間復雜度有什么用可以從空間復雜度角度進行空間優(yōu)化?？臻g優(yōu)化思路是極簡不浪費不額外申請不留的銷毀/釋放只留當前所需不得不留的壓縮。常用的空間優(yōu)化技術有滾動數(shù)組在動態(tài)規(guī)劃中只保留當前計算所需的前幾行/列數(shù)據(jù)而非整個二維表格將空間從 O(n2) 降至 O(n)。狀態(tài)壓縮用位運算等技巧將多維狀態(tài)壓縮到一維或?qū)顟B(tài)用整數(shù)表示減少存儲開銷。推導式 / 遞推數(shù)據(jù)邊用邊銷毀不保留中間完整副本例如流式處理或迭代計算。局部變量作用域及時釋放臨時變量避免不必要的長生命周期占用內(nèi)存。原地算法直接在輸入數(shù)據(jù)上修改不額外申請等規(guī)模存儲空間。數(shù)據(jù)分塊 / 懶加載只加載當前需要處理的數(shù)據(jù)塊而非一次性載入全部數(shù)據(jù)。fivebliss
精度處理：BigDecimal、DecimalFormat等5種保留小數(shù)方法詳解)
動走向末路？逆向成本趨零，廠商定價策略或被顛覆！)
據(jù)范圍問題)
站與個人知識庫管理實戰(zhàn))
學公式并轉(zhuǎn)換為LaTeX代碼)
據(jù)手冊實戰(zhàn)解讀：從內(nèi)部原理到防坑應用全解析)
字化建設提速 300%+，這家互聯(lián)網(wǎng)集團做對了什么？)
