算法一：概述

概述

1. 算法

算法algorithm，来自于数学领域。算法的种类也很多，有好有坏。我们用时间复杂度和空间复杂度来衡量一个算法的好坏。
算法在实际开发中主要用在下面：

• 运算：比如超大整数进行运算；
• 查找：搜索引擎搜索内容，以及数据库查找
• 排序：各种排序算法
• 最优决策

2. 数据结构

数据结构是数据的组织、管理和存储格式，其使用目的是为了高效的访问和修改数据。
数据结构的组成有下面几种：

• 线性结构：最简单的结构，包括数据、链表、栈、队列、哈希表等。
• 树：二叉树、二叉堆。
• 图：元素间多对多的关系，更复杂的一种数据结构。

时间复杂度

1. 概念

时间复杂度是用来评估一段算法执行时间的长短。受运行环境和输入规模的影响，代码的绝对执行时间是无法预估的，但我们却可以预估代码的基本操作执行次数。假设输入规模是n，那么会有一个函数T(n)来表示当前算法的执行次数。

2. O(n)官方定义

若存在函数f(n)，使得当n趋近于无穷大时，T(n)/f(n)为不等于0的常数，则称f(n)是T(n)的同量级函数。记作T(n)=O(f(n))。O为算法的渐进时间复杂度。也被称为大O表示法。

3. 举例

• T(n)=3n，那么去掉最高阶系数3之后的渐进时间复杂度就是O(n)。
• T(n)=5logn，去掉最高阶系数5，T(n)=O(logn)
• T(n)=2，去掉最高阶2，T(n)=O(1)
• T(n)=0.5n²+0.5n，还是以最高阶为准，去掉系数之后就是T(n)=O(n²)。

空间复杂度

1. 概念

算法的执行除了上面说的时间成本，还有空间成本。因为算法在执行指令的过程中，需要存储一些中间数据。存储这部分数据的成本，称之为空间成本。因为内存是优先的，所以在时间复杂度相同的情况下，空间复杂度越小越好。

和时间复杂度一样，我们也用O(n)来标示算法在执行过程中占用的内存空间。

2. 常见的空间复杂度

• 常量空间：算法的存储空间和输入规模无关，那么空间复杂度记作O(1)。比如向字典中插入一个数据。

• 线性空间：算法分配的空间是一个线性集合，并且集合大小和输入规模成n成正比。那么空间复杂度记作O(n)。

• 二维空间：比如一个二位数组，集合的长度和宽度都和输入规模n成正比。记作O(n²)

• 递归空间：有一类比较特殊的程序，自己内部会调动自己，我们称之为递归调用。

  1. 计算机在执行程序的时候，会专门分配一块内存，用来存储方法调用栈。

  2. 方法调用栈分为进栈和出栈两个行为：当进入一个新方法时会执行进栈操作，方法执行完再执行出栈操作。

  所以，执行递归操作所需要的内存空间和递归的深度成正比。如果递归的深度是n，那么空间复杂度就是O(n)。

3. 时间和空间复杂度的取舍

在绝大多数时候，时间复杂度更重要，我们宁可多分配一些内存空间，也要提升程序的执行速度。

数组

1. 基本介绍

(1) 对应的英文是array。有限个相同类型变量组成的有序集合。数组中的每一个变量成为元素。

(2) 数组在内存中是连续的。也就是说顺序不能乱，而且也不能跳过某个存储单元。

(3) 数组的下标从0开始，一直到长度-1的位置

2. 基本操作

(1) 读取和更新元素

根据下标index，从数组中拿到该元素，直接取值和赋值就可以了。

(2) 插入元素

根据插入位置的不同，分为中间插入和尾部插入。

• 尾部插入：直接把元素放在数组最后空闲位置即可。
• 中间插入：稍微复杂一些，需要从数组尾部元素开始，一直到插入点index，依次向后挪一位。从而把待插入点的位置空出来，然后把元素插入进去。

(3) 超范围插入（数组扩容）

上面说的插入元素，都是在插入后长度不超过数组原长度的情况下进行。但还有一种情况，就是插入元素后，导致数组长度超出之前的长度。这就需要对数组进行扩容。

扩容的方法很简单，再创建一个新数组，长度是旧数组的2倍。然后把旧数组中的元素全部复制过来，就实现了数组扩容。

(4) 删除元素

这个就简单多了，把要删除index后的元素，依次向前挪动一位就可以了。

3. 时间复杂度

(1) 插入元素：涉及到扩容和挪位两部分，这两部分的时间复杂度都是O(n)，所以插入的时间复杂度也是O(n)。

(2) 删除元素：只有挪位的操作，时间复杂度是O(n)。

(3) 删除时不记顺序：有这么一种骚操作，在删除一个元素的时候，后面的元素不进行挪位。而是直接把最后一个元素复制到被删除的位置上，然后再把最后一个元素删除掉。这样的时间复杂度是O(1)，但代价是数组顺序发生改变。一般不常用。

4. 数组的优势和劣势

(1) 优势：高效的随机访问能力，只要给出下标，就能以常量的时间找到对应的元素。

(2) 劣势：由于数组在内存中是连续存储，所以插入和删除元素，必然会带动大量元素的移动，影响效率。

总结：数组适合读操作多，写操作少的情景。

链表

1. 基本介绍

(1) 物理上一种非顺序，非连续的数据结构，由若干个节点组成。

(2) 第一个节点成为头结点，最后一个节点成为尾节点。

(3) 单向链表：每个节点有两部分构成：存放数据的变量data，指向下一个节点的指针next。单向链表只能通过一个节点找到它的下一个节点，却不能找到上一个节点。

(4) 双向链表：每个节点由三部分组成，除了data和next之外，还有一个指向上一个节点的prev指针。双向链表中，我们可以通过prev来找到上一个节点。

(5) 数组在内存中是占用了一片连续完整的内存空间，而链表则是见缝插针。链表分布在内存中的不同位置，依靠next和prev来关联起来。

2. 基本操作

(1) 查找节点

链表不能快速定位，只能从头节点开始，依次next来查找给定的index。时间复杂度是O(n)

(2) 更新节点

主要还是查找的耗时，更新的过程和数组一样。

(3) 插入节点

因为链表是不连续的，所以不需要像数组那样考虑扩容。只要内存空间足够，可以一直添加。根据插入位置的不同，分为下面三种情况：

• 尾部插入：把最后一个节点的next指向新节点即可。
• 头部插入：把新节点的next指向原头节点，再把新节点变为链表的头结点。
• 中间插入：同样很简单，先把插入点的前置节点的next指向新节点，然后再把新节点的next指向原插入的节点。

(4) 删除节点

同样根据删除节点位置的不同分为下面几种情况：

• 头部删除
• 中间删除
• 尾部删除

3. 时间复杂度

(1) 查找过程的时间复杂度是O(n)。

(2) 插入和删除，如果不考虑查找的过程，那么单纯操作的时间复杂度是O(1)。

4. 数组和链表对比

(1) 数组的优势是快速定位元素，适合读操作多，写操作少的情况。

(2) 链表的优势在于能灵活的插入和删除元素，如果需要在尾部频繁的插入、删除元素，链表更合适。

栈和队列

1. 物理结构和逻辑结构

(1) 物理结构是实实在在的结构。比如上面说的数组和链表都是内存中实实在在的存储结构，所以属于物理结构。

(2) 逻辑结构是抽象的概念，它依赖于物理结构而存在。比如后面说到的栈和队列，他们的实现方式皆可以是数组也可以是链表。

2. 栈的Stack基本介绍

(1) 比如一个羽毛球筒，一端有底，一端有口。我们向里面放入羽毛球。那么就会出现先放入的最后拿出，后放入的先拿出。这就是典型的栈stack。

(2) 栈是一种线性结构，栈中的元素只能先入后出FILO（First In Last Out）。最先进入的元素是栈底，最后进入的是栈顶。

(3) 栈既可以用数组来实现，也可以用链表来实现。

3. 栈的基本操作

就两种：入栈和出栈。

(1) 入栈Push：把一个元素放入栈中。只能从栈顶一侧放入，新入栈的元素会成为新的栈顶。

(2) 出栈Pop：把元素从栈中弹出。只有栈顶的元素才允许出栈。如果要把栈中间的元素出栈，那么必须先让栈顶的元素依次出栈才可以。

4. 队列Queue的基本介绍

(1) 类似于汽车排队过隧道。一端进，一端出，方向不能改变。

(2) 队列遵循的是先入先出FIFO（First In First Out）原则。队列的出口端叫队头，队列的入口端叫队尾。

(3) 队列的实现既可以用数组也可以用链表。

注意：在使用数组来实现的时候，要在数组最后多留一个空位，这个空位是队尾。当新元素入队的时候，直接放到这个队尾就可以了。

5. 队列的基本操作

(1) 入队
如果是用数组实现，那么就把新元素放到队尾空白位上。

(2) 出队
把队头的元素移除队列。只允许队头一侧移除元素。出队元素的后一个元素会成为新的队头。

(3) 循环队列
1) 在用数组实现队列的时候，会有这样的问题：随着出队元素的增多，队头左侧的空间就失去作用，队列的容量也会越来越小。如果出队和入队频繁的发生，一遍是数组开头空出大量空闲位置，另一方面数组还在不断扩容。
2) 这时候循环队列就出现了。在标记好队头和队尾元素的情况下，新插入的元素，优先去占已经移除队列的坑。打破原有的存储顺序。让数组的空间更加合理的利用起来。

6. 栈和队列的应用

(1) 栈的应用
通常用于对“历史”的回溯。比如从浏览网页返回上一级，再返回上上级。

(2) 队列的应用
通常用于对“历史”的回放。比如多线程等等队列，就要根据谁先加进来，谁先执行。

(3) 双端队列
结合栈和队列的特性：既可以先入先出，也可以后入先出。

散列表

1. 基本介绍

散列表也叫做哈希表hash table。这种数据结构提供了键key值value的映射关系。只要给出yigekey，就可以高效查找到它所匹配的value，时间复杂度接近于O(1)。

2. 哈希函数

(1) 在上面介绍的数据结构中，数组的查找效率最高。但是数组只能根据下标index进行查找，而散列表的key是字符串。所以我们需要一个中转站，来将可以转换为数组的index，这个中转站就是哈希函数。

(2) 哈希函数在不同语言中的实现方式不一样。

3. 散列表的写操作

(1) 步骤

先通过哈希函数，把key转换为index。然后看下数组在该下标的元素是否为空。如果为空就直接存入。如果不为空，那就是典型的哈希冲突了。

(2) 哈希冲突

随着数据的增多，哈希冲突不可避免。所以我们必须要有解决方案。常用的有两种：开放寻址法和链表法。
1) 开放寻址法：就是要插入的index被占用了，那么就去寻找其它没被占用的index。比如依次向后查找。
2) 链表法：这是一个重点了，Java的HashMap使用的就是这种。
HashMap数组的元素不仅仅是一个Entry对象，还是一个链表的头结点。每个Entry对象通过next指向她的下一个Entry节点。当新来的Entry映射到与之冲突的数组位置时，只要插入到对应的链表中即可。

4. 散列表的读操作

读操作和写操作差不多。也是通过哈希函数从key得到index。然后去数组中取值。如果对应index元素的key和要查找的key一直，那么直接取值即可。如果不一直，那么就查找该index开头的链表。在该链表中依次查找key相同的就可以了。

5. 散列表的扩容

(1) 散列是基于数组的，既然数组要扩容，那么散列也会遇到扩容的问题。

(2) 什么时候需要扩容
经过多次元素插入，散列表达到一定的饱和度，key映射位置发生冲突的概率会逐渐提高。这样一来，大量元素拥挤在相同的数组下标位置，行成很长的链表。对后续插入操作和查询操作都有很大的影响。这个时候，就需要扩容了。

(3) JDK中HashMap影响扩容的两个因素：

• Capacity：当前HashMap的长度

• LoadFactor：HashMap的负载因子，默认值是0.75f。

  当HashMap满足下面的条件时，就行需要进行扩容：

          HashMap.size >= Capacity * LoadFactor```
          
  

(4) 扩容的过程

新建一个新的Entry数组，长度为原来的2倍。

重新Hash：遍历原Entry数组，把所有的Entry重新hash到新数组中。经过扩容，原本拥挤的散列表又会变得稀疏。以前的那些常常的链表也会小时很多。