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