快速入门算法
百科：
推荐链接：
前言
为什么要学习算法和数据结构？
- 解决特定问题。
- 深度优化程序性能的基础。
- 学习一种思想：如何把现实问题转化为计算机语言表示。
业务开发要掌握到程度？
- 了解常见数据结构和算法，沟通没有障碍。
- 活学活用：遇到问题时知道要用什么数据结构和算法去优化。
算法基础
什么是算法
数学：算法是用于解决某一类问题的公式和思想。
计算机：一系列程序指令，用于解决特定的运算和逻辑问题。
如何衡量算法好坏
- 时间复杂度：运行时间长短。
- 空间复杂度：占用内存大小。
怎么计算时间复杂度
大O表示法（渐进时间复杂度）：把程序的相对执行时间函数T(n)简化为一个数量级，这个数量级可以是n、n^2、logN等。
推导时间复杂度的几个原则：
- 如果运行时间是常数量级，则用常数1表示。
- 只保留时间函数中的最高阶项。
- 如果最高阶项存在，则省去最高项前面的系数。
时间复杂度对比：O(1) > O(logn) > O(n) > O(nlogn) > O(n^2)。
不同时间复杂度算法运行次数对比：
怎么计算空间复杂度
常量空间 O(1)：存储空间大小固定，和输入规模没有直接的关系。
线性空间 O(n)：分配的空间是一个线性的集合，并且集合大小和输入规模n成正比。
二维空间 O(n^2)：分配的空间是一个二维数组集合，并且集合的长度和宽度都与输入规模n成正比。
递归空间 O(logn)：递归是一个比较特殊的场景。虽然递归代码中并没有显式的声明变量或集合，但是计算机在执行程序时，会专门分配一块内存空间，用来存储“方法调用栈”。执行递归操作所需要的内存空间和递归的深度成正比。
如何定义算法稳定性
稳定：如果a原本在b前面，而a=b，排序之后a仍然在b的前面。
不稳定：如果a原本在b的前面，而a=b，排序之后 a 可能会出现在 b 的后面。
常见算法
首先要明确：特定算法解决特定问题。
- 字符串：暴力匹配、BM、KMP、Trie等。
- 查找：二分查找、遍历查找等。
- 排序：冒泡排序、快排、计数排序、堆排序等。
- 搜索：TFIDF、PageRank等。
- 聚类分析：期望最大化、k-meanings、k-数位等。
- 深度学习：深度信念网络、深度卷积神经网络、生成式对抗等。
- 异常检测：k最近邻、局部异常因子等。
- ……
其中，字符串、查找、排序算法是最基础的算法。