持续创作，加快生长！这是我参加「日新方案 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)

  • 链表的翻转, 运用头插法.

1. 创立一个newHead指针指向null, 即ListNode newHead = null.
2. while循环让head往后走, 直到head指向null中止
3. 创立一个tmp来记录当时head的下一个节点, ListNode tmp = head.next
4. 让head的next指向newhead, 即 head.next = newHead
5. newhead指向当时的head, 即newhead = head
6. 将tmp赋值给head, 即head = tmp.
7. 进入下次循环即可

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，坑位有限，补白“网友”可被群管经过~