持續創作，加速成長！這是我參與「掘金日新計劃 · 10 月更文挑戰」的第5天，點選檢視活動詳情

1. 前言

• 在iOS行業演算法除了面試時的篩選作用, 還有其他作用嗎?
• 不少一線iOS開發人員可能都會存在這個疑問. 存在即合理, 因為常見的實際業務中, 演算法用到的確實不多.
• 然而, 演算法真的沒用嗎? 非也, 程式 = 演算法 + 資料結構
• 演算法和資料結構的運用體現在iOS底層設計的方方面面.
• 下面就拋磚引玉, 跟大家一起聊聊一些關於演算法的淺見, 閱讀中如發現錯誤, 還望評論區指正:)

2. iOS開發中的演算法相關基操Tips

2.1 我們一般從以下幾個維度來評估演算法的優劣

• 正確性、可讀性、健壯性

• 時間複雜度、空間複雜度

• 演算法優化的方向, 用盡量少的儲存空間, 用盡量少的執行步驟.

• 對於不能兼顧的時候, 會採用空間換時間, 或者時間換空間的方式來完成. 

2.1.1 時間複雜度

• 大O表示法中, 時間複雜度的公式是: T(n) = O(f(n)), 其中f(n)表示每個程式碼執行次數之和, 而O表示正比例關係, 這個公式的全稱是:演算法的漸進時間複雜度.
• 常見的時間複雜度量級從上至下越來越大:
• • 常數階O(1)
• • 對數階O(logN)
• • 線性對數階O(nlogN)
• • 平方階O(n²)
• • 立方階O(n³)
• • K次方階O(n^k)
• • 指數階O(2^n)

2.1.2 空間複雜度

• 空間複雜度是對一個演算法在執行過程中臨時佔用儲存空間大小的一個量度, 同樣反映的是一個趨勢, 我們用S(n)來定義.
• 空間複雜度比較常用的有: O(1)、O(n)、O(n²).
• 如果演算法執行所需要的臨時空間不隨著某個變數n的大小而變化, 即此演算法空間複雜度為一個常量, 可表示為O(1) // 程式碼中的i、j、m所分配的空間都不隨著處理資料量變化, 因此它的空間複雜度S(n) = O(1) int j = 1; int j = 2; ++i; j++; int m = i + j;
• 空間複雜度O(n) int[] m = new int[n]; for (i = 1; i <= n; ++i) { j = i; j++ }
• 這段程式碼中, 第一行new了一個數組出來, 這個資料佔用的大小為n, 這段程式碼的2-6航, 雖然有迴圈, 但沒有再分配新的空間, 因此, 這段程式碼的空間複雜度主要看第一行即可, 即S(n) = O(n);

2.2 常見的資料結構及演算法思想

• 資料結構是計算機儲存、組織資料的方式. 有線性結構, 樹形結構, 圖形結構
• 常見的線性表有：陣列, 連結串列, 棧, 佇列, 雜湊表

2.2.1 陣列是一種順序儲存的線性表, 所有元素的記憶體地址是連續的.

• 但是很多語言陣列是無法動態修改容量的, 例如我們NSArray. 所以需要動態擴容. 

• 陣列的優點是查詢的時間複雜度為O（1）, 新增和刪除資料的時間複雜度為O（n）. 

• 陣列的缺點是在擴容的時候需要頻繁操作資料, 而且會導致佔用過大的記憶體, 存在記憶體浪費. 

• 為了解決它的缺點, 就有了連結串列.

2.2.2 連結串列是一種鏈式儲存的線性表. 所有元素的記憶體地址是不連續的.

• 它的優點是, 不造成記憶體空間的浪費. 

• 但是它的查詢效率低O（n)

• 連結串列的翻轉, 使用頭插法.  ```

• 建立一個newHead指標指向null,  即ListNode newHead = null. 

• while迴圈讓head往後走, 直到head指向null停止

• 建立一個tmp來記錄當前head的下一個節點,  ListNode tmp = head.next

• 讓head的next指向newhead,  即 head.next = newHead

• newhead指向當前的head, 即newhead = head

• 將tmp賦值給head, 即head = tmp. 

• 進入下次迴圈即可 ```

2.2.2.1 如何判斷連結串列是否有環?

• 是通過快慢指標來實現.
• 快指標每次前進兩步, 慢指標每次前進1步. 這樣如果快慢指標能相遇, 就表示有環. 

2.2.2.2 雙向連結串列是含有前後指標的. 兩者對比

• 動態陣列：開闢銷燬記憶體空間的次數相對較少, 但可能造成記憶體空間的浪費

• 雙向連結串列, 開闢和銷燬記憶體空間的次數相對較多, 但不會造成記憶體浪費

• 如果頻繁在尾部進行新增, 刪除操作, 那麼動態陣列, 雙向連結串列均可選擇. 

• 如果頻繁在頭部進行新增, 刪除操作, 可以使用雙向連結串列, 因為動態陣列要將資料全部移動

• 如果在任意位置新增刪除, 可以選擇雙向連結串列

• 如果有頻繁的查詢, 使用動態陣列. 

2.2.2.3 如何通過陣列來模擬連結串列？

• 靜態連結串列就是在連結串列的節點中存放值和下一個元素的索引. 

• 刪除排序連結串列的重複元素, 或者刪除連結串列的重複元素, 重複元素不保留, 都是採用雙指標的方法. 

2.2.2.4 棧是一種特殊的線性表, 只能在一端進行操作. 遵循LIFO, 先進後出

• 棧的實現可以採用動態陣列和連結串列. 

• 可以用來解決匹配問題. 

2.2.2.5 佇列是一種特殊的線性表, 只能在頭尾兩端進行操作.

• 隊尾入隊, 對頭出隊. 遵循FIFO原則. 

• 因為佇列是在頭尾操作, 建議採用雙向連結串列實現. 

• 如何用棧實現佇列：準備兩個棧, instack和outstack. 入隊時push到instack

• 出隊時, 如果outstack不為空, outstack彈出棧頂元素, 如果outstack為空, 就將instack所有元素逐一彈出, push到outstack中, outstack彈出棧頂元素. 

• ps: 雙端佇列是能在頭尾兩端進行新增和刪除的佇列. 

2.2.3 樹形結構

• 節點的度：子樹的個數

• 樹的度：所有節點度中的最大值

• 葉子節點：度為0的節點

• 非葉子節點：度不為0的節點

• 層數：根節點在第一次, 根節點的子節點在第二層

• 節點的深度：從根節點到當前節點的唯一路徑上的節點總數

• 節點的高度：從當前節點到最遠葉子節點的路徑上的節點總數

• 樹的深度：所有節點高度中的最大值

• 二叉樹：每個節點的度最大為2

• 完全二叉樹是指對樹的節點從上到下編號都會與滿二叉樹對應. 

• 它的性質是度為1的節點只有左子樹. 度為1的節點要麼是1個要麼是0個. 

2.2.3.1 二叉樹的遍歷

• 前, 中, 後序遍歷, 採用棧來實現. 

• 層序遍歷採用佇列來實現

2.2.3.2 二叉搜尋樹

• 任意一個節點的值都大於其左子樹所有節點的值, 任意一個節點的值都小於其右子樹所有節點的值. 

2.2.3.3 刪除節點：

• 對於葉子節點：直接刪除

• 對於度為1的節點：用子節點替代原來節點的位置

• 對於度為2的節點：先用前驅結點或者後繼節點的值覆蓋原節點的值

• 這裡前驅結點是指中序遍歷中節點的前一個節點. 

• 後繼節點是中序遍歷中後一個節點的值. 

2.2.3.4 因為對樹的節點刪除後

• 可能會成為一個像連結串列的形式, 這樣就達不到讓新增, 刪除, 搜尋的複雜度維持在O（logn）, 所以就有了平衡二叉樹. 

• 平衡二叉樹是要求樹的左右子樹高度相差不超過1.所以就有了AVL樹, 紅黑樹

• 平衡因子：某結點的左右子樹的高度差不超過1.

• B樹是一種平衡的多路搜尋樹. 

2.2.3.5 紅黑樹

• 節點是red或者black

• 根節點是black

• 葉子節點都是black

• red節點的子節點都是black

• 從任一節點到葉子節點的所有路徑都包含相同數量的black節點. 

2.2.4 雜湊表

• 雜湊表是空間換時間的典型. 它的底層是使用的陣列, 

2.2.4.1 雜湊衝突的解決方法有哪些

• 開放地址法：就是按照一定的規則向其他地址探測, 直到遇到空桶

• 還可以再hash, 還有就是鏈地址法, 通過連結串列連線起來

• jdk1.8中的雜湊表是採用連結串列+紅黑樹解決雜湊衝突的. 

• 雜湊函式是用來計算索引值的, 首先將key經過雜湊函式生成一個hash值

• 然後將hash值跟陣列大小進行相關運算, 生成一個索引值

• 所以要求key必須是可hash的, 而且是可比較的. 

2.2.5 堆

• 堆的一個重要性質, 任意節點的值總是大於等於 或 小於等於 子節點的值

2.2.5.1 堆的新增

• 堆底新增元素, 然後開始上濾, 就是和它的父節點進行比較, 如果比父節點大, 就交換位置, 然後重複這個過程, 直到根節點. 

2.2.5.2 堆的刪除

• 刪除堆頂元素, 先用最後一個節點覆蓋根節點, 然後刪除最後一個節點, 然後執行下濾操作, 直到沒有子節點了. 

2.2.5.3 批量建堆

• 自上而下的上濾. 就是利用層序遍歷的結果來進行上濾操作. 因為層序遍歷就是陣列的正序遍歷. （這裡從第二層開始即可, 第一層是根節點）
• 自下而上的下濾. 這裡是第一個非葉子節點開始. 
• ps: 優先順序佇列通過二叉堆來實現. 

2.2.6 各種排序

2.2.6.1 快排

• 原理, 逐漸的將每一個元素變成軸點元素
• 用軸點元素分開序列, 左邊都是小於等於軸點元素, 右邊大於
• 這樣就可以把原來的序列分開成兩個序列
• 遞迴同樣的操作, 直到每個元素都變成軸點元素

2.2.6.2 堆排序

• 首先是原地建堆, 然後交換堆頂元素與尾元素. 然後將堆的數量-1, 再重複上面的操作, 
• 對序列進行原地建堆, 重複執行下沉操作, nlogK, K遠小於N

2.2.6.3 歸併排序

• 歸併排序就是先拆後組合.
• 不斷地將當前的序列分割成兩個子序列, 直到不能分割
• 不斷地將子序列合併成大的有序序列, 最終完成排序.

2.2.6.4 希爾排序

• 希爾排序就是把序列看作是一個矩陣, 分成m列, 逐列進行排序. 

2.2.6.5 計數排序

• 計數排序, 桶排序, 基數排序都不是基於比較的排序. 

2.2.7 遞迴

• 遞迴的基本思想是拆解問題.

2.2.8 回溯

• 什麼是回溯
• 八皇后遊戲
• • 8 * 8的方格
• • 在每一個格子裡放一個皇后
• • 皇后同一行同一列同一個斜線不能出現兩個
• • 攻擊範圍內不能有第二個皇后
• • 有多少種排法
• 九皇后, 回溯思想
• • 走迷宮, 當我們遇到N條選擇, 一直往下走,
• • 走不通回退一步, 選擇其他的走
• • 遍歷了所有的可能
• • 選擇一條路出發, 能進則進, 不能進就退一步
• • 嘗試另外一條路

2.2.9 分治

• 什麼是分治?
• • 將原問題分解成若干個子問題
• • 保持子問題結構和原問題是一致的, 只是規模上不一致
• • 子問題又能不斷地被分解成若干個子問題
• • 直到子問題是可以輕易地得出結果,
• • 結構是一樣的, 得到原問題的解
• 例如12個數字, 找最大值
• • 首先把12個數字分成3組, 4個一組
• • 三組裡的最大數
• • 4個數字, 兩兩一組,
• • 得到第一組中最大的
• • 子問題找到父問題的答案
• • 三個中最大的就找到了

3. iOS中的資料結構演算法應用🌰

3.1 自動釋放池AutoReleasePool

• 自動釋放池AutoReleasePool就是基於棧和雙向連結串列這兩種資料結構實現的.
• 從資料結構的角度來看AutoReleasePool是以棧為結點通過雙向連結串列的形式組合而成.

3.2 UINavigationController的push和pop

• iOS中最常見的推入和彈出頁面, 就是應用就是了棧結構.

3.3 iOS圖片快取框架SDWebImage中的資料結構和演算法

• SDWebImage的記憶體設計中,
• 淘汰策略使用了佇列的資料結構, 以佇列先進先出的方式做淘汰
• 採用了LRU演算法, 如30分鐘內是否使用過, 做圖片快取淘汰策略

發文不易, 喜歡點讚的人更有好運氣👍 :), 定期更新+關注不迷路~

ps：歡迎加入筆者18年建立的研究iOS稽核及前沿技術的三千人扣群：662339934，坑位有限，備註“掘金網友”可被群管通過~