《漫画算法：小灰的算法之旅》
整体还可以，先了解计算机内存物理结构会好一点。了解算法对开阔思路很有帮助。
egg：少年高斯1+50，等差数列求和，高斯算法
基本概念
算法衡量维度
- 时间复杂度
- 空间复杂度(space complexity)
多数情况下，时间度更重要一些，我们愿意多分配一些内存空间，也要提升程序的执行速度。
算法应用
- 运算
- 查找
- 排序
- 最优决策
数据结构组成方式
- 线性结构，包括数组、链表、栈、队列、哈希表
- 树，如二叉树、二叉堆
- 图
- 其他由基本数据结构变形而来，用来解决某些特定问题，如跳表、哈希链表、位图等
对数：若a的x次方等于N（a>0，且a不等于1），那么数x叫做以a为底N的对数（logarithm）。记做x=logaN）。其中a叫做对数的底数，N叫做真数。
常见复杂度
- T(n) = 3n
- T(n) = 5logn
- T(n) = 2
- T(n) = 0.5n2+0.5n
渐进时间复杂度（asymptotic time complexity）用大写O表示，也称为大O表示法
原则
- 如果运行时间是常数量级，则用常数1表示
- 只保留时间函数中的最高阶项
- 如果最高阶存在，则省去最高阶项前面的系数
例子： T(n)=2 写作 T(n)=O(1) T(n)=3n 写作 T(n)=O(n) T(n)=5logn 写作 T(n)=O(logn) T(n)=0.5n2 + 0.5n 写作 T(n)=O(n2)
当n足够大时，4种时间复杂度用时
O(n) < O(logn) < O(n) < O(n2)
常见空间复杂度情形
- 常量空间 O(1)
- 线性空间 O(n)
- 二维空间 O(n2)
- 递归空间 O(n)
数据结构
数组（array）是有限个相同类型的变量所组成的有序集合，数组中的每一个变量被称为元素。
- 数组是最为简单、最为常用的数据结构
- 数组在内存中是顺序存储，因此可以很好实现逻辑上的顺序表
- 适合读操作多，写操作少的场景
数组的优缺点
- 数组拥有高效的随机访问能力，只要给出下标，就可以用常量时间找到对应元素。二分查找就利用了这点
- 插入和删除元素会导致大量元素被迫移动，影响效率
链表（linked list）是一种在物理上非连续、非顺序的数据结构，由若干节点（node）所组成。
- 若说数组在内存中是顺序存储，那么链表在内存中存储方式是随机存储
- 单向链表的每个节点包含两部分
- 存放数据的变量data
- 下一个节点的指针next
- 双向链表
- 指向前置节点的prev指针
- 存放数据的data
- next指针
垃圾回收机制（GC），如java，就是当内存中的变量没有外部引用指向它们，这时就会被自动回收
可以这么理解 数据分物理结构和逻辑结构，数组链表属于物理结构，而基于物理结构实现的机构如，顺序表、栈、队列、树、图属于逻辑结构
栈（stact）是一种线性数据机构，栈中的元素遵循（FILO First in last out）。最早进入的元素放的位置叫做栈底（bottom），最后进入的元素放的位置叫做栈顶（top）。
- 栈通常用于对”历史“的回溯，如面包屑导航，浏览页面可以轻松返回上一级或者更上一级
队列（queue）也是一种线性数据机构，队列的出口端叫做队头（front），入口段叫做队尾（rear）。
- 队列常用于对”历史“的回放，如多线程中争夺公平锁的等待队列
栈和队列都是既可以用数组实现，也可以用链表实现。
双端队列，综合了栈和队列的优点，可以从队头的一段入队或出队，也可以从队尾一段入队或出队 优先队列，不遵循先入先出，而是谁优先级高谁先出队，不属于线性结构，是基于二叉堆来实现的。
- 最大优先队列，最大元素优先出队
- 最小优先队列
散列表也叫哈希表（hash table），这种数据结构提供了键（key）和值（value）的映射关系，时间复杂度接近于O（1）。
- 散列表本质上也是一个数组。通过一个”中转站“对数组下标和key进行转换，这个中转站就叫做哈希函数。
- 哈希冲突无法避免，主要有两种解决方法
- 开放寻址法
- 链表法
- 散列表的读操作就是通过给定的key，在散列表中查找对应的value
树（tree）是n个节点的有限集。
- 当n=0时，称为空树
- 有且仅有一个特点的称为根节点
- 当n>1时，其余节点可分为m个互不相交的有限集，每个集合本身又是一个树，称为根的子树
二叉树（binary tree）是树的一种特殊形式。即每个节点最多有2个子节点
- 满二叉树（每个分支都是慢的）
- 完全二叉树（最后一个节点之前的节点都齐全即可）
二叉树主要用于
- 查找
- 维持相对顺序
二叉查找树又叫做二叉排序树（binary sort tree）
- 若左子树不为空，则左子树所有及诶点需小于根节点的值
- 右子树需大于根节点的值
- 左右子树也都是二叉查找树
二叉树的自平衡方式
- 红黑树
- AVL树
- 树堆
- …
二叉树的遍历方式（2大类4种）
- 深度遍历优先
- 前序遍历(root–>left–>right)（可以用栈，利用栈的回溯特性）
- 中序遍历(left–>root–>right)
- 后序遍历(left–>right–>root)
- 广度遍历优先
- 层序遍历(可以用队列）
二叉堆。本质上是一种完全二叉树，分为两个类型
- 最大堆
- 最小堆
二叉堆基于堆的自我调整，就是把一个不符合堆的完全二叉树，调整成一个堆。本质就是让所有非叶子节点依次下沉。
- 二叉堆虽然是完全二叉树，但存储方式并不是链式存储，而是顺序存储，即二叉堆的所有节点都存储在数组中
- 二叉堆是实现堆排序和优先队列的基础
排序算法
常见排序算法（按时间复杂度分大体分3类）
- 时间复杂度O（n2）
- 冒泡排序
- 选择排序
- 插入排序
- 希尔排序（性能略优于O(n2),但大于O(logn))
- 时间复杂度O(nlogn)
- 快速排序
- 归并排序
- 堆排序
- 时间复杂度线性
- 计数排序（利用数组下标来确认元素的正确位置）
- 桶排序
- 基数排序
稳定排序与不稳定排序：衡量标准为值相同的元素排序后是否保持排序前的顺序
冒泡排序（bubble sort），这是一种基础的交换排序。
- 就是比较右边元素的大小，如果比右边大就交换位置。
- 鸡尾酒排序可以看做是冒泡排序的升级排序法（鸡尾酒排序的比较和交换是双向的）
快速排序，快速排序跟冒泡一样也属于交换排序，不同的是，冒泡排序在每一轮只是把1个元素冒泡到数列的一段，而快速排序则在每一轮挑选一个基准元素，并让其他比它大的元素移到数列一遍，比它小的元素移动到数列另一边。这种思路叫做分治法。
绝大多数的递归逻辑，都可以用栈的方法来替代
堆排序和快速排序都是不稳定排序
计数排序局限性
- 不适合最大和最小值差距太大
- 数列元素不是整数时，也不适合计数排序
桶排序，每个桶（bucket）代表一个区间范围，里面可以有一个或多个元素
常见算法
Q&A
Q1: 如何判断链表有环
- 遍历，每遍历一个新节点就从头检查新节点之前的所有节点和新节点对比，相同则说明这个节点被遍历过两次
- Hash,先创建一个以节点ID为key的hashset集合，用来存储遍历过的节点。然后从头节点遍历，每遍历一个新节点，都用新节点和hashset集合中存储的节点比较，如果存在与之相同的接地那ID，说明有环，如果不存在就把这个新节点ID存入hashset中
- 指针，两个指针，指针p1每次向后移动1个节点，指针p2每次向后移动2个节点，然后比较两个指针指向的节点是否相同。
Q2：实现一个最小栈
- 采用额外一个栈存储最小值,（存储栈中曾经的最小值）
Q3：求最大公约数
- 辗转相除法又名欧几里得算法（Euclidean algorithm）。定理：两个正整数a和b（a>b）,他们的最大公约数等于a除以b的余数c和b之间的最大公约数。
- 更相减损术，出自中国古代《九章算术》。原理：两个正整数a和b（a>b）,他们的最大公约数等于a减去b的差值c和b之间的最大公约数。
- 辗转相除法结合更相减损术
Q4：判断一个数是否是2的整数次幂
- 利用2进制，除了高位有1就不是
Q5：无序数组排序后的最大相邻差
- 利用计数排序思想
Q6：用栈实现队列
- 两个栈
算法实际应用
Bitmap（位图）
- 主要用于对大量证书做去重和查询操作
LRU（Least Recently Used）是一种内存管理算法，LRU使用了哈希链表
A星寻路算法（A* search algorithm）是一种用于寻找有效路径的算法。