《漫画算法》笔记-上篇

漫画算法-小灰的算法之旅

魏梦舒（@程序员小灰）著

小灰用漫画（可爱的手绘小仓鼠）的形式，给算法这颗“炮弹”包上了“糖衣”，让算法的为力潜藏于内，外表不再吓人，变得萌萌哒，Q弹可爱。

本书通过主人公小灰，用漫画的形式讲述了算法与数据结构的基础知识、复杂多变的算法面试及算法的实际应用。

• 第一章：讲述什么是算法、数据结构，有什么用。如何计算时间复杂度、空间复杂度。
• 第二章：讲述基本的数据结构：数组、链表、栈、队列、哈希。
• 第三章：讲述了树、二叉树相关知识。
• 第四章：讲述了经典的排序算法：冒泡、快速、堆、计数、桶排序。
• 第五章：讲述了10多道职场上流行的算法面试题及详细的解题思路。
• 第六章：讲述了算法在职场上的实际应用。

“学习算法，我们不需要死记硬背那些冗长复杂的背景知识、底层原理、指令语法......需要做的是领悟算法思想、理解算法对内存空间和性能的影响，以及开动脑筋去寻求解决问题的最佳方案。相比编程领域的其他技术，算法更纯粹，更接近数学，也更具有趣味性。” -- 作者说

1. 算法和数据结构

算法

algorithm。始于计算出1+2+3+4...+10000的结果。首先把从1到10000这10000个数字两两分组相加，如下：

1 + 10000 = 10001
2 + 9999 = 10001
3 + 9998 = 10001
......

一共有多少组这样结果相同的和呢？有10000/2即5000组，即结果：(1 + 10000) * 10000 / 2 = 50005000。

在数学上称这种等差数列求和的方法为：高斯算法。

在数学领域：算法是用于解决一类问题的公式和思想。

在计算机领域：算法本质是一序列程序指令，用于解决特定的运算和逻辑问题。衡量算法好坏的重要标准有两个：

• 空间复杂度：占用内存空间的大小
• 时间复杂度：运行时间的长短

应用：运算、查找、排序、寻找最优路线、面试等。

数据结构

数据结构是算法的基石。如果把算法比喻成美丽灵动的舞者，那么数据结构就是舞者脚下广阔而坚实的舞台。

data structure，是数据的组织、管理和存储格式，其使用的目的是为了高效地访问和修改数据。

数据结构组成方式：

• 线性结构：最简单的数据结构。包括数组、链表，及衍生的栈、队列、哈希表。
• 树：相对复杂的数据结构，有代表性的是二叉树。
• 图：更为复杂的数据结构，因为在图中会呈现出多对多的关联关系。

时间复杂度

是对一个算法运行时间长短的量度，用大O表示，记作T(n) = O(f(n))

直白地讲，时间复杂度就是把程序的相对执行时间函数T(n)简化为一个数量级，这个数量级可以是n、n2、n3等。

推导出时间复杂度，有如下几个原则：

• 如果运行时间是常数量级，则用常数1表示
• 只保留时间函数中的最高阶项
• 如果最高阶项存在，则省去最高阶项前面的系数

比如：

执行次数是T(n) = 3n，最高阶项为3n，省去系数3，转化的时间复杂度为T(n) = O(n)

执行次数是T(n) = 5logn，最高阶项为5logn，省去系数5，转化的时间复杂度为T(n) = O(logn)。5logn，数学中的对数。

执行次数是T(n) = 2，只有常数量级，转化的时间复杂度为T(n)=O(1)

执行次数是T(n) = 0.5n2 + 0.5n，最高阶项为0.5n2，省去系数0.5，转化的时间复杂度为T(n) = O(n2)

谁更节省时间呢？结论如下：
O(1) < O(logn) < O(n) < O(n2)

空间复杂度

space complexity。是对一个算法在运行过程中临时占用存储空间大小的度量，用大O表示，记作S(n) = O(f(n))

• 常量空间：O(1)，存储空间大小固定，和输入规模没有直接关系
• 线性空间：O(n)，空间是一个线性的集合（比如数组），并且集合大小和输入规模n成正比
• 二维空间：O(n2)空间是一个二维数组集合，并且集合的长度和宽度都与输入规模n成正比
• 递归空间：执行递归操作所需的内存空间和递归的深度成正比。纯粹的递归操作的空间复杂度也是线性的，如果递归的深度是n，那么空间复杂度就是O(n)

2. 数据结构基础

数组

有限个，在内存中顺序存储。

内存是由一个个连续的内存单元组成的，每一个内存单元都有自己的地址。

数组中的每一个元素，都存储在小小的内存单元中，并且元素直接紧密排列，既不能打乱元素的存储顺序，也不能跳过某个存储单元进行存储。

操作：

• 读取、更新：利用索引，比较容易，直接操作
• 插入：末尾插入简单，直接在最后插入即可。非末尾插入，由于数组的每一个元素都有其固定下标，所以需要先把插入位置及后面的元素向后移动，挪出地方，再把要插入的元素放到对应的数组位置上。
• 删除：和插入过程相反，若删除的元素不是位于末尾，其后的元素都要向前移动。

插入、删除的时间复杂度都是O(n)

优势：非常高效的访问能力，只要给出下标，就能找到对应元素。
劣势：插入、删除效率低下。数组元素连续紧密地存储在内存中，插入、删除元素都会导致大量元素被迫移动，影响效率。

数组适合读操作多、写操作少的场景。链表和数组正好相反。

链表

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

单向链表的每一个节点包含两部分，存放数据的变量data，指向下一个节点的指针next。

链表的第一个节点被称为头结点，最后一个节点被称为尾节点。尾结点的下一个节点指向空。

双向链表，每一个节点除了拥有 data 和 next，还拥有指向前置节点的 prev 指针。

数组在内存中的存储方式是顺序存储，链表 在内存中的存储顺序是随机存储。

数组在内存中占用了连续完整的存储空间，而链表采用了见缝插针的方式，链表的没一个节点分布在内存的不同位置，依靠next指针关联起来。这样可以灵活有效地利用零散的碎片空间。

链表操作：

• 查找节点：只能从头结点开始向后一个一个节点逐一查找。
• 更新：查找到了，替换数据就好
• 插入、删除：分三种情况：尾部、头部、中间，需要处理对应的next指针。具体看书中的图会更直观呢，文字描述太晦涩了。

；链表的插入和删除的时间复杂度：如果不考虑插入、删除操作之前查找元素的过程，只考虑纯粹的插入、删除操作，时间复杂度为O(1)

数组 vs 链表：数组能够利用下标快速定位元素，对于读操作多、写操作少的场景非常使用。而链表的有事在于能灵活的进行插入和删除操作，适用于读操作少、写操作多的场景。

栈和队列

数据存储的物理结构和逻辑结构：

• 物理结构：物质层面，实实在在的，看得见，摸得着。
  • 顺序存储结构：数组
  • 链式存储结构：链表
• 逻辑结构：精神层面，抽象的概念，依赖于物理结构而存在。
  • 线性结构：顺序表、栈、队列
  • 非线性结构：树、图

栈：stack。一种线性数据结构，栈中的元素只能先进后出(FILO，First In Last Out)。最早进入的元素存放的位置叫作栈底，最后进入的元素存放的位置叫作栈顶。用数组、链表均可以实现。

栈的基本操作：

• 入栈：只能从栈顶放入元素，新元素成为新栈顶。
• 出栈：只能从栈顶弹出元素，出栈元素的前一个元素成为新栈顶。

入栈、出栈的时间复杂度：O(1)，因为只会影响到最后一个元素。

队列：queue。一种线性数据结构，队列中的元素只能先进先出(FIFO，First In First Out)。队列的出口端叫作队头(front)，队列的入口端叫作队尾(rear)。用数组、链表均可以实现。

队列的基本操作：

• 入队：enqueue，只能在队尾的位置放入元素，新元素成为新队尾。
• 出队：dequeue，只能在队头的位置移出元素，出队元素的后一个元素成为新队头。

额外：循环队列、双端队列、优先队列。

散列表

散列表：也称哈希表，hash table。是存储 key-value 映射的集合，时间复杂度接近于O(1)。本质上也是一个数组。

哈希函数：通过某种方式，把 key 和数组下标进行转换的函数。

散列表的读写操作：

• 写操作(put)：在散列表中插入新的键值对。
  • 通过哈希函数，把 key 转换成数组下标。如果数组下标的位置没有元素，就放到该位置，如果该位置有值，这种情况为哈希冲突。
  • 解决哈希冲突：开放寻址法和链表法。
• 读操作(get)：通过给定的key，在散列表中查找对应的value。
  • 通过哈希函数，把 key 转换成数组下标，然后根据下标找value.

3.树

树

tree，是n个节点的有限集。有如下特点：

• 有且仅有一个特定的称为根的节点。
• 当n>1时，其余节点可分为m(m>0)个互不相交的有限集，每一个集合本身又是一个树，并称为根的子树。

树的最大层级树，被称为树的高度或深度。

相关节点

• 根节点(root)
• 叶子节点(leaf):没有孩子的节点
• 父节点
• 孩子节点
• 兄弟节点

二叉树

树的一种特殊形式。树的每个节点最多有2个孩子节点。

二叉树的两个孩子节点，一个被称为左孩子，一个被称为右节点。

二叉树有两种特殊形式：满二叉树、完全二叉树。

满二叉树：一个二叉树的所有非叶子节点都存在左右孩子，并且所有叶子节点都在同一层接上。简言之，满二叉树的每一个分支都是满的。

完全二叉树：对一个有n个节点的二叉树，按层级顺序编号，则所有节点的编号为从1到n。如果这个树所有节点和同样深度的满二叉树的编号为从1到n的节点位置相同，则这个二叉树为满二叉树。

一棵树，若为满二叉树，那么一定是完全二叉树。反之，不一定。

在内存中存储：

• 链式存储结构：一个节点含数据data，指向左孩子的节点，指向右孩子的节点。
• 数组：按照层级顺序把二叉树的节点放到数组中对应的位置上。如果某一个节点的孩子为空，则数组的相应位置也空出来。
  • 为什么这么设计？可以更方便的定位孩子节点、父节点。
  • 若父节点的下标是parent，那么左孩子节点下标是2parent+1，右孩子节点下标是2parent+2。
  • 反之，若左孩子节点下标是leftChild,那么父节点下标是(leftChild - 1)/2。
  • 稀疏二叉树，用数组表示会很浪费空间。

二叉树的应用：查找操作、维持相对顺序。

• 查找：二叉查找树。左子树上所有节点都小于根节点，右子树上所有节点都大于根节点。左右子树也都是二叉查找树。
• 维持相对顺序：二叉排序树

二叉树的遍历：
从节点之间位置关系的角度：

• 前序遍历：输出顺序：根节点、左子树、右子树
• 中序遍历：输出顺序：左子树、根节点、右子树
• 后序遍历：输出顺序：左子树、右子树、根节点
• 层序遍历：按照从根节点到叶子节点的层级关系，一层一层横向遍历各个节点。

从更宏观的角度:

• 深度优先遍历(前、中、后序遍历，前中后是相对根节点)
• 广度优先遍历(层序遍历)

二叉堆：本质上是一种完全二叉树。

• 最大堆：任何一个父节点的值，都大于或等于它左、右孩子节点的值。
• 最小堆：任何一个父节点的值，都小于或等于它左、右孩子节点的值。

二叉堆的根节点，叫作堆顶。最大堆的堆顶是整个堆中最大元素，最小堆的堆顶是整个堆中最小元素。

优先队列：基于二叉堆实现：

• 最大优先队列：无论入队顺序如何，当前最大元素都会优先出队，基于最大堆实现
• 最小优先队列：无论出队顺序如何，当前最小元素都会优先出队，基于最小堆实现

观后感：回想起了很多大学学习时的场景与概念（专业：软件工程）

《漫画算法》笔记-上篇

原文：https://www.cnblogs.com/EnSnail/p/11037209.html