程序员必备算法基础

一.复杂度

1. 复杂度是什么

复杂度是衡量代码运行效率的重要的度量因素。
先看一下复杂度和计算机实际任务处理效率的关系，从而了解降低复杂度的必要性。

计算机通过一个个程序去执行计算任务，也就是对输入数据进行加工处理，并最终得到结果的过程。每个程序都是由代码构成的。可见，编写代码的核心就是要完成计算。但对于同一个计算任务，不同计算方法得到结果的过程复杂程度是不一样的，这对你实际的任务处理效率就有了非常大的影响。
举个例子，你要在一个在线系统中实时处理数据。假设这个系统平均每分钟会新增 300M 的数据量。如果你的代码不能在 1 分钟内完成对这 300M 数据的处理，那么这个系统就会发生时间爆炸和空间爆炸。表现就是，电脑执行越来越慢，直到死机。因此，我们需要讲究合理的计算方法，去通过尽可能低复杂程度的代码完成计算任务。

那如何降低复杂程度呢，我们首先需要知道怎么衡量复杂度。而在实际衡量时，我们通常会围绕以下2 个维度进行。
首先，这段代码消耗的资源是什么。一般而言，代码执行过程中会消耗计算时间和计算空间，那需要衡量的就是

• 时间复杂度
• 空间复杂度。

其次，这段代码对于资源的消耗是多少。不能只看当前资源消耗了多少，因为不管是时间还是空间，它们的消耗都和输入量有很大关系。为了更客观地衡量消耗程度，我们通常会关注时间或者空间消耗量与输入数据量之间的关系。

复杂度是一个关于输入数据量 n 的函数。假设你的代码复杂度是 f(n)，即 O(f(n))。例如，O(n) 表示的是，复杂度与计算实例的个数 n 线性相关；O(logn) 表示的是，复杂度与计算实例的个数 n 对数相关。

通常，复杂度的计算方法遵循以下几个原则：

• 首先，复杂度与具体的常系数无关，例如 O(n) 和 O(2n) 表示的是同样的复杂度。我们详细分析下，O(2n) 等于 O(n+n)，也等于 O(n) + O(n)。也就是说，一段 O(n) 复杂度的代码只是先后执行两遍 O(n)，其复杂度是一致的。
• 其次，多项式级的复杂度相加的时候，选择高者作为结果，例如 O(n²)+O(n) 和 O(n²) 表示的是同样的复杂度。具体分析一下就是，O(n²)+O(n) = O(n²+n)。随着 n 越来越大，二阶多项式的变化率是要比一阶多项式更大的。因此，只需要通过更大变化率的二阶多项式来表征复杂度就可以了。

O(1) 也是表示一个特殊复杂度，含义为某个任务通过有限可数的资源即可完成。此处有限可数的具体意义是:数据量多少和资源消耗无关。

2.时间复杂度与代码结构的关系

代码的时间复杂度，与代码的结构有非常强的关系。举个栗子：

function getMaxVal(arr) {
    let max_val = -1;
    for (let i = 0; i < arr.length; i++) {
        if (arr[i] > max_val) {
            max_val = a[i];
        }
    }
    return max_val
}

暂存当前最大值并把所有元素遍历一遍即可。因为代码的结构上需要使用一个 for 循环，对数组所有元素处理一遍，所以时间复杂度为 O(n)。

下面的代码定义了一个数组 a = [1, 3, 4, 3, 4, 1, 3]，并会在这个数组中查找出现次数最多的那个数字

function getMostVal(arr = [1, 3, 4, 3, 4, 1, 3 ] ) {
    let val_max = -1;
    let time_max = 0;
    let time_tmp = 0;
    for (int i = 0; i < arr.length; i++) {
        time_tmp = 0;
        for (let j = 0; j < arr.length; j++) {
            if (arr[i] == arr[j]) {
            time_tmp += 1;
        }
        if (time_tmp > time_max) {
            time_max = time_tmp;
            val_max = arr[i];
        }
        }
    }
   return val_max;
}

这段代码中，我们采用了两重循环的方式计算：第一层循环，对数组中每个元素进行遍历；第二层循环，对于每个元素计算出现的次数，并且通过当前元素次数 time_tmp 和全局最大次数变量 time_max 的大小关系，保存出现次数最多的那个元素及其出现次数。由于是两重循环，这段代码在时间复杂度是 n*n，也就是 O(n²)。

通过一些经验，我们可以得出一些结论：

• 一个顺序结构的代码，时间复杂度是 O(1)。
• 二分查找（分而治之的二分策略），时间复杂度都是 O(logn)。
• 一个简单的 for 循环，时间复杂度是 O(n)。
• 两个顺序执行的 for 循环，时间复杂度是 O(n)+O(n)=O(2n)，其实也是 O(n)。
• 两个嵌套的 for 循环，时间复杂度是 O(n²)。

3.降低时间复杂度的必要性

假设某个计算任务需要处理 10万 条数据。你编写的代码：

• 如果是 O(n²) 的时间复杂度，那么计算的次数就大概是 100 亿次左右。
• 如果是 O(n)，那么计算的次数就是 10万 次左右。
• 如果这个工程师再厉害一些，能在 O(log n) 的复杂度下完成任务，那么计算的次数就是 17 次左右。

通常在小数据量的计算上，时间复杂度的降低在绝对处理时间上没有太多体现。但在当今的大数据环境下，时间复杂度的优化将会带来巨大的系统收益。

二.学会将时间复杂度转换成空间复杂度

在两全其美的情况下，要采用尽可能低的时间复杂度和空间复杂度，去完成一段代码的开发。但有时候只能选择牺牲一部分来找到最佳编码方法。

要诀：时间昂贵、空间廉价

一段代码会消耗计算时间、资源空间，从而产生时间复杂度和空间复杂度。
假设一段代码经过优化后，虽然降低了时间复杂度，但依然需要消耗非常高的空间复杂度。 例如，对于固定数据量的输入，这段代码需要消耗几十 G 的内存空间，很显然普通计算机根本无法完成这样的计算。如果一定要解决的话，一个最简单粗暴的办法就是，购买大量的高性能计算机，来弥补空间性能的不足。
这告诉我们一个什么样的现实问题呢？代码效率的瓶颈可能发生在时间或者空间两个方面。如果是缺少计算空间，花钱买服务器就可以了。这是个花钱就能解决的问题。相反，如果是缺少计算时间，只能投入宝贵的人生去跑程序。即使你有再多的钱、再多的服务器，也是毫无用处。相比于空间复杂度，时间复杂度的降低就显得更加重要了。因此，你会发现这样的结论：空间是廉价的，而时间是昂贵的。

程序优化的具体思路：

• 第一步，暴力解法。在没有任何时间、空间约束下，完成代码任务的开发。

• 第二步，无效操作处理。将代码中的无效计算、无效存储剔除，降低时间或空间复杂度。

• 第三步，时空转换。设计合理数据结构，完成时间复杂度向空间复杂度的转移。

举个栗子：
查找出一个数组中，出现次数最多的那个元素的数值。

// 暴力解法：
function getMostVal( arr = [1, 3, 4, 3, 4, 1, 3 ]) {
    let val_max = -1;
    let time_max = 0;
    let time_tmp = 0;
    for (int i = 0; i < arr.length; i++) {
        time_tmp = 0;
        for (let j = 0; j < arr.length; j++) {
            if (arr[i] == arr[j]) {
            time_tmp += 1;
        }
        if (time_tmp > time_max) {
            time_max = time_tmp;
            val_max = arr[i];
        }
        }
    }
   return val_max;
}

采用了两层的 for 循环，很显然时间复杂度就是 O(n²)。而且代码中，几乎没有冗余的无效计算。如果还需要再去优化，就要考虑采用一些数据结构方面的手段，来把时间复杂度转移到空间复杂度了。

function getMostVal( arr = [1, 3, 4, 3, 4, 1, 3 ]) {
    let d = new Map();
    for (let i = 0; i < a.length; i++) {
        if (d.has(a[i])) {
            d.set(a[i], d.get(a[i]) + 1);
        } else {
            d.set(a[i], 1);
        }
    }
    let val_max = -1;
    let time_max = 0;
    for(let key in d){
        if (d.get(key) > time_max) {
            time_max = d.get(key);
            val_max = key;
        }
    }
    return val_max;
}

代码结构上，有两个 for 循环。不过，这两个循环不是嵌套关系，而是顺序执行关系。其中，第一个循环实现了数组转map的过程，也就是 O(n) 的复杂度。第二个循环再次遍历map找到出现次数最多的那个元素，也是一个 O(n) 的时间复杂度。

分析过程 – 3个步骤

• 首先，这段代码对数据进行了哪些操作？（增删查）
• 其次，这些操作中，哪个操作最影响效率，对时间复杂度的损耗最大？
• 最后，哪种数据结构最能提高数据操作的使用效率？

三.线性表结构的增删查

1.线性表

大概是这样的东西：|￣1￣|–>|￣2￣|–>…

在链表的最前面，通常会有个头指针用来指向第一个结点。对于链表的最后一个结点，由于在它之后没有下一个结点，因此它的指针是个空指针。链表结构，和小朋友手拉手站成一排的场景是非常相似的。
从单链表又衍生出了循环链表、双向链表等

2.线性表对于数据的增删查

1. 单链表

• 增 ：只需要把待插入结点的指针指向原指针的目标，把原来的指针指向待插入的结点
• 删 ：如果待删除的结点为 b，那么只需要把指向 b 的指针 （p.next），指向 b 的指针指向的结点（p.next.next）
• 查 ：一个个指向去查找

2. 栈（后进先出 ）
3. 队列
4. 二叉树
5. 哈希表

3.算法思维基础

1. 递归
2. 分而治之（二分法）
3. 排序算法
4. 动态规划

• 分阶段 -> 找状态 -> 做决策 -> 状态转移方程 -> 定目标 -> 寻找终止条件
  例：输入两个字符串，用动态规划的方法，求解出最大公共子串。

  例如，输入 a = “13452439”， b = “123456”。由于字符串”345”同时在 a 和 b 中出现，且是同时出现在 a 和 b 中的最长的子串。因此输出”345”。
  具体分析一下动态规划的步骤:

  • 对于一个可能的起点，它后面的每个字符都是一个阶段。
  • 状态就是当前寻找到的相匹配的字符。
  • 决策就是当前找到的字符是否相等（相等则进入到公共子串中）。
  • 状态转移方程可以写作 sk+1 = uk(sk)。可以理解为，如果 sk = “123”是公共子串，且在 a 字符串和 b 字符串中，”123”后面的字符相等，假设为”4”，则决策要进入到公共子串中，sk+1 = “1234”。
  • 目标自然就是公共子串最长。
  • 终止条件就是决策到了不相等的结果