关于我的仓库

• 这篇文章是我为面试准备的学习总结中的一篇
• 我将准备面试中找到的所有学习资料，写的Demo，写的博客都放在了这个仓库里iOS-Engineer-Interview
• 欢迎star👏👏
• 其中的博客在简书，CSDN都有发布
• 博客中提到的相关的代码Demo可以在仓库里相应的文件夹里找到

前言

• 该系列为学习《数据结构与算法之美》的系列学习笔记
• 总结规律为一周一更，内容包括其中的重要知识带你，以及课后题的解答
• 算法的学习学与刷题并进，希望能真正养成解算法题的思维
• LeetCode刷题仓库：LeetCode-All-In
• 多说无益，你应该开始打代码了

01讲为什么要学习数据结构和算法

• 想要通关大厂面试，千万别让数据结构和算法拖了后腿
• 我们学任何知识都是为了“用”的，是为了解决实际工作问题的
• 业务开发工程师，你真的愿意做一辈子CRUD boy吗？【crud是指在做计算处理时的增加(Create)、读取查询(Retrieve)、更新(Update)和删除(Delete)几个单词的首字母简写。crud主要被用在描述软件系统中数据库或者持久层的基本操作功能。】
• 不需要自己实现，并不代表什么都不需要了解。
• 在基础框架中，一般都揉和了很多基础数据结构和算法的设计思想。
• 掌握数据结构和算法，不管对于阅读框架源码，还是理解其背后的设计思想，都是非常有用的。
• 基础架构研发工程师，写出达到开源水平的框架才是你的目标！
• 对编程还有追求？不想被行业淘汰？那就不要只会写凑合能用的代码！
• 掌握了数据结构与算法，你看待问题的深度，解决问题的角度就会完全不一样。

课后题：你为什么要学习数据结构和算法呢？在过去的软件开发中，数据结构和算法在哪些地方帮到了你？

• 在最开始对算法有概念是在刚大一的时候，当时学校没开C语言，都是自己在那里做算法题，对于算法也是在那个时候开始用些许认识的，当时就会觉得很奇妙
• 后来参加了蓝桥杯，ACM校赛，开始意识到自己和高手之间有多深的差距，进入实验室学习iOS开发后，算法也是基本放下，也是明显感到和后台舍友之间的差距越来越大
• 目前数据结构和算法，算法课都已经上完，对于各种算法好像懂点，看到题也能像孔乙己一样支支吾吾说个DP出来，可一到上手敲的时候，还是gg
• 即将参加面试，算法作为重要的一环，我不希望会拖我后腿，甚至希望能是个加分项，为此，我会✊到底
• 过去的软件开发，在iOS开发阶段，调的都是Apple的API，没怎么用到算法与数据结构知识，但最近阅读RunTime源码的时候，由于Apple用了很多Hash的知识，没有这方面的知识很容易对源码产生困惑

02讲如何抓住重点，系统高效地学习数据结构与算法

• 数据结构是为算法服务的，算法要作用在特定的数据结构之上。
• 复杂度分析对于学习算法有很大的用处，✊学好

img

• 十个数据结构：数组、链表、栈、队列、散列表、二叉树、堆、跳表、图、Trie树

• 十个算法：递归、排序、二分查找、搜索、哈希算法、贪心算法、分治算法、回溯算法、动态规划、字符串匹配算法

• 不要为了学习而学习，而是要学习它的“来历”“自身的特点”“适合解决的问题”以及“实际的应用场景”。

课后题：请思考一下你自己学习这个专栏的方法，你在之前学习数据结构和算法的过程中，遇到过什么样的困难或者疑惑吗？

• 这篇文章就是方法的一部分，在每一讲学完以后都会写成这样一块的总结，另外每天在LeetCode两道题
• 困难与疑惑真的是在于总感觉代码写不出来，想想挺对，一写就错

03讲复杂度分析（上）：如何分析、统计算法的执行效率和资源消耗

• 复杂度分析是整个算法学习的精髓，只要掌握了它，数据结构和算法的内容基本上就掌握了一半。
• 监控得到的运行时间受限于测试环境，测试数据，无法真正体现复杂度，因此我们需要一个不用具体测试数据，可以粗略估计算法的执行效率的方法

img

• 其中T(n)表示代码执行的时间；n表示数据规模的大小；f(n)表示每行代码执行的次数总和。因为这是一个公式，所以用f(n)来表示。公式中的O，表示代码的执行时间T(n)与f(n)表达式成正比。
• 这也就到了大O时间复杂度的本质，它不是代码真正的执行时间，而是代码执行时间随数据规模增长的变化趋势，真正名字应该是渐进时间复杂度（asymptotic time complexity），简称时间复杂度。

img

• 对于复杂度量级，我们可以粗略地分为两类，多项式量级和非多项式量级。其中，非多项式量级只有两个：O(2n)和O(n!)。
• 当数据规模n越来越大时，非多项式量级算法的执行时间会急剧增加，求解问题的执行时间会无限增长。所以，非多项式时间复杂度的算法其实是非常低效的算法。

O(1)

• 由于大O表示的是代码执行时间的变化趋势，因此O(1)其实很好理解，就是时间是定死的
• 一般情况下，只要算法中不存在循环语句、递归语句，即使有成千上万行的代码，其时间复杂度也是Ο(1)。

O(logn)、O(nlogn)

• 不管是以2为底、以3为底，还是以10为底，我们可以把所有对数阶的时间复杂度都记为O(logn)，因为log3n就等于log32 * log2n，O(log3n) = O(C * log2n)，在采用大O标记复杂度的时候，可以忽略系数，即O(Cf(n)) = O(f(n))

空间复杂度

• 时间复杂度的全称是渐进时间复杂度，表示算法的执行时间与数据规模之间的增长关系。类比一下，空间复杂度全称就是渐进空间复杂度（asymptotic space complexity），表示算法的存储空间与数据规模之间的增长关系。

复杂度增进曲线

img

课后题：有人说，我们项目之前都会进行性能测试，再做代码的时间复杂度、空间复杂度分析，是不是多此一举呢？而且，每段代码都分析一下时间复杂度、空间复杂度，是不是很浪费时间呢？你怎么看待这个问题呢？

• 这个问题我觉得主要还是推出了时间复杂度，空间复杂度的概念后，我们在交流算法的时候有了一个交流的平台，我们能感性的了解到算法中的好坏，效率的高低
• 对于真正投入使用的时候，肯定实际测试要测，复杂度分析也要做

04讲复杂度分析（下）：浅析最好、最坏、平均、均摊时间复杂度

加权平均时间复杂度 = 平均时间复杂度 = 期望时间复杂度

// n表示数组array的长度
int find(int[] array, int n, int x) {
  int i = 0;
  int pos = -1;
  for (; i < n; ++i) {
    if (array[i] == x) {
       pos = i;
       break;
    }
  }
  return pos;
}

• 我们在长度为n的数组里搜索x的时候，由于一旦找到就会退出循环，导致不是每次运行都会肯定走n次，因此需要引入平均时间复杂度概念
• 要查找的变量x在数组中的位置，有n+1种情况：在数组的0～n-1位置中和不在数组中。我们把每种情况下，查找需要遍历的元素个数累加起来，然后再除以n+1，就可以得到需要遍历的元素个数的平均值，即：

img

• 我们现在假设在数组与不在数组里的概率都是1/2，x出现在数组中每个位置的可能性都是1/n，这样，在搜索数组里的数据的时候，x出现在数组里的概率就是1/(2n)，x不出现在数组里的概率就是1/2
• 这里我的理解方式就是，x要能出现在数组里，前提条件就是先有了出现在数组里的那个可能性2/1，在此基础上才有了接下来来的1/n
• 现在的平均复杂度就是：

img

均摊时间复杂度

举例：

 // array表示一个长度为n的数组
 // 代码中的array.length就等于n
 int[] array = new int[n];
 int count = 0;
 
 void insert(int val) {
    if (count == array.length) {
       int sum = 0;
       for (int i = 0; i < array.length; ++i) {
          sum = sum + array[i];
       }
       array[0] = sum;
       count = 1;
    }

    array[count] = val;
    ++count;
 }

• 这是一个插入函数，两种情况：
  • count == array.length，count记录者当前插入到第几位，当count == len的时候，也就意味着数组里元素被插满了，此时便会遍历整个数组，求和，输入到首位。并令count = 1，等待下一次循环
  • 正常情况下赋值，count++

加权平均时间复杂度

• 假设数组的长度是n，根据数据插入的位置的不同，我们可以分为n种情况，每种情况的时间复杂度是O(1)。除此之外，还有一种“额外”的情况，就是在数组没有空闲空间时插入一个数据，这个时候的时间复杂度是O(n)。而且，这n+1种情况发生的概率一样，都是1/(n+1)。所以，根据加权平均的计算方法，我们求得的平均时间复杂度就是：

img

均摊时间复杂度

• 我们可以注意到一个规律，每次进行完O(n)的操作后，由于count回到了1，下面的n - 1个操作都是O(1)复杂度的
• 在此规律上，我们可以把耗时长的那个O(n)操作平均分配下去，这样平均下去，等同于每次操作都是O(1)【2次】
• 这样来看，时间复杂度就是O(1)
• 因此，均摊时间复杂度等同于就是特殊的时间复杂度算法，本身没有什么特别之处

课后题：你可以用今天学习的知识，来分析一下下面这个add()函数的时间复杂度。

// 全局变量，大小为10的数组array，长度len，下标i。
int array[] = new int[10]; 
int len = 10;
int i = 0;

// 往数组中添加一个元素
void add(int element) {
   if (i >= len) { // 数组空间不够了
     // 重新申请一个2倍大小的数组空间
     int new_array[] = new int[len*2];
     // 把原来array数组中的数据依次copy到new_array
     for (int j = 0; j < len; ++j) {
       new_array[j] = array[j];
     }
     // new_array复制给array，array现在大小就是2倍len了
     array = new_array;
     len = 2 * len;
   }
   // 将element放到下标为i的位置，下标i加一
   array[i] = element;
   ++i;
}

• 该算法的最好情况时间复杂度(best case time complexity)为O(1);
• 最坏情况时间复杂度(worst case time complexity)为O(n);
• 平均情况时间复杂度(average case time complexity)为O(1);
• 时间复杂度感觉还是没必要这么复杂，像这道题，只有一种情况会是O(n)，其他情况都肯定是O(1)，没有纠结的必要

05讲数组：为什么很多编程语言中数组都从0开始编号

• 数组（Array）是一种线性表数据结构。它用一组连续的内存空间，来存储一组具有相同类型的数据。
• 线性表（Linear List）。顾名思义，线性表就是数据排成像一条线一样的结构。每个线性表上的数据最多只有前和后两个方向。其实除了数组，链表、队列、栈等也是线性表结构。【线性表只有前后有联系】

img

• 与之相反的，在非线性表中，数据不是简单的前后关系

img

• 连续的内存空间和相同类型的数据。

• 不精确：链表适合插入、删除，时间复杂度O(1)；数组适合查找，查找时间复杂度为O(1)

• 精确：数组是适合查找操作，但是查找的时间复杂度并不为O(1)。即便是排好序的数组，你用二分查找，时间复杂度也是O(logn)。所以，正确的表述应该是，数组支持随机访问，根据下标随机访问的时间复杂度为O(1)。

• 数组删除的优化：将多次删除操作集中在一起执行，每次删除都是标记一待删除的数据，真正的删除等到内存不够的时候一口气进行，同时这也是java中的JVM删除

数组越界：黄金体验镇魂曲--永远无法到达的彼岸

int main(int argc, char* argv[]){
    int i = 0;
    int arr[3] = {0};
    for(; i<=3; i++){
        arr[i] = 0;
        printf("hello world\n");
    }
    return 0;
}

• 数组其实就是一块连续的内存，当我们越界的时候就会访问到其他内存空间
• 函数体内的局部变量存在栈上，且是连续压栈。在Linux进程的内存布局中，栈区在高地址空间，从高向低增长。变量i和arr在相邻地址，且i比arr的地址大，所以arr越界正好访问到i。当然，前提是i和arr元素同类型，否则那段代码仍是未决行为。
• 组越界在C语言中是一种未决行为，并没有规定数组访问越界时编译器应该如何处理。因为，访问数组的本质就是访问一段连续内存，只要数组通过偏移计算得到的内存地址是可用的，那么程序就可能不会报任何错误。
• 当然这个具体还是要看编译器与电脑具体情况，在我的CodeRunner上就是非常普通的崩溃了，在打印三次之后
• 总之，如果是在符合上述入栈规则的编译器中使用的话，就会出现无限打印的情况
• 因为arr[3]访问到的就是是i的地址，等于就是不停的在修改i的值，自然会导致无限循环
• 数组寻址公示：a[i]_address = base_address + i * data_type_size

数组编号为什么从0开始，而不是从1开始

• 我们已经知道在内存里面不存在真正的数组，只有一段内存，我们有的只是首地址以及单位长度
• 因此下标其实描述的是数组的编译量，也就是从首地址开始的偏移程度
• 当我们的下标是从0开始的时候，我们的寻址公式是：a[i]_address = base_address + i * data_type_size
• 而当我们的下标是从1开始的时候，我们的寻址公式就会变成：a[k]_address = base_address + (k-1)*type_size
• 这样多了一个减法操作，对于CPU来说，就多了一个减法指令

课后题

前面我基于数组的原理引出JVM的标记清除垃圾回收算法的核心理念。我不知道你是否使用Java语言，理解JVM，如果你熟悉，可以在回顾下你理解的标记清除垃圾回收算法。

• 大多数主流虚拟机采用可达性分析算法来判断对象是否存活，在标记阶段，会遍历所有 GC ROOTS，将所有 GC ROOTS 可达的对象标记为存活。只有当标记工作完成后，清理工作才会开始。
• 不足：1.效率问题。标记和清理效率都不高，但是当知道只有少量垃圾产生时会很高效。2.空间问题。会产生不连续的内存空间碎片。

前面我们讲到一维数组的内存寻址公式，那你可以思考一下，类比一下，二维数组的内存寻址公式是怎样的呢？

• 对于 m * n 的数组，a [ i ][ j ] (i < m,j < n)的地址为：address = base_address + ( i * n + j) * type_size