提示：这里可以添加系列文章的所有文章的目录，目录需要自己手动添加
TODO:写完再整理
- 系列文章目录
- 前言
- 一、程序的时间和空间复杂度分析
- （1）理解算法时间复杂度的表示法
- （2）线性复杂度的分析
- （3）递归复杂度的分析
- （4）各种数据结构的时间复杂度
- 二、顺序、条件、循环基本结构
- 三、位运算
- （1）总的运算符
- （2）位运算的应用
- 四、字符串算法
- （1）字符串的定义
- （2）字符串的比较
- （3）注意
- 五、数组的排序算法
- （1）各种算法的时间空间复杂度比较
- （2）比较类排序（常用）
- （1）交换排序
- 1）冒泡排序（重要）
- 2）快速排序（重要）
- （2）插入排序
- 1）插入排序（重要）
- 2）希尔排序
- （3）选择排序
- 1）选择排序（重要）
- 2）堆排序
- （4）归并排序
- 1）二路归并排序（重要）
- 2）多路归并排序
- （3）非比较类排序（针对整型的数据类型）
- （1）桶排序
- （2）计数排序
- （3）基数排序
- （4）排序总结
- 六、数组的查找算法
- （1）简单暴力查找（适合元素少的）
- （2）二分查找（适合元素多的，但是要先排序）
- （3）总结
- 七、树/图的查找算法
- （1）搜索遍历的要求
- （2）搜索遍历的方法
- 1）所有节点的循环暴力搜索
- 2）广度优先（breadth first search）搜索【解决无权重图问题】
- 3）深度优先（depth first search ）搜索【解决无权重图问题】
- 4）Dijkstar算法【解决加权图问题】
- 5）启发式搜索（也称优先级搜索A*）【解决加权图问题】
- 6）剪枝搜索
- 7）双向搜索
- （3）搜索遍历顺序
- （1）前序遍历（pre-order）【根-左-右的顺序】
- （2）中序遍历(in-order)【左-根-右的顺序】
- （3）后序遍历(post-order)【左-右-根的顺序】
- （4）相关应用--路径规划搜索
- 八、递归、分治、回溯思想算法
- （1）递归算法【针对同一类问题重复性较高的】
- （2）分治（D&C）算法【针对同几类问题，具有一定重复性的】
- （3）回溯的算法【试错的思想】
- （4）总结
- 九、贪心算法、动态规划算法【处理不能完成的任务-NP完全问题】
- （1）贪心算法【适合单个约束的无解问题求近似解】【子问题局部最优的方向】
- （2）动态规划算法【适合多个约束的无解问题求近似解】【子问题从全局看，先大后小的方向】
- （3）总结
- 十、布隆过滤器（用于概率性系统查询）
- （1）图例
- （2）布隆过滤器的功能
- （3）布隆过滤器的优缺点
- （4）布隆过滤器的python实现
- 十一、k最近邻算法（KNN）
- （1）k最近邻算法（KNN）的核心思想
- （2）k最近邻算法（KNN）的实现步骤
- （3）k最近邻算法（KNN）的应用
- 十二、机器学习（深度学习）的算法
- （1）机器学习（深度学习）的步骤
- （2）机器学习（深度学习）应用
- 总结
前言 认知有限，望大家多多包涵，有什么问题也希望能够与大家多交流，共同成长！
本文先对算法部分做个简单的介绍，具体内容后续再更，其他模块可以参考去我其他文章
提示：以下是本篇文章正文内容
一、程序的时间和空间复杂度分析 （1）理解算法时间复杂度的表示法（1）时间复杂度【按时间复杂度排列】
（1）O(1) 常数复杂度，最佳，比如 Hash 表、缓存等 （2）O(log n) 仅次于常数复杂度，如二分查找、二叉搜索树等 （3）O(n) 线性复杂度，如大多数遍历操作 （4）O(nlogn) （5）O(n^2) 双重 for 循环 （6）O(2^n) 递归的时间复杂度 （7）O(n!) 旅行商问题
.
（2）空间复杂度
（1）O(1) 原地操作 （2）O(n) 开辟线性辅助空间
（3）不同复杂度的迭代次数表示
.
.
（1）方法一：画出递归树状图方法
画出递归函数运行的树状图进行分析，想想能不能进行简化，去除重复计算的部分
（2）方法二：主定理方法
用于分析递归函数迭代次数的理论
（3）优化的方法
中间加一个缓存，把重复的结果放到缓存里面，用的时候再调用，以空间换时间
这么做方法可以减少计算机的计算次数，但是增加人脑的逻辑运算
.
.
.
.
.
.
（1）单运算符
（1）逻辑与 （2）逻辑或 （3）逻辑非 （4）按位与 （5）按位或 （6）按位非
（2）双运算符
（1）异或
需要记忆一些常见的位运算公式
.
.
（1）指定位置的位运算应用
计算机的数字表示方式和存储格式都是二进制
（2）算数移位与逻辑移位
（3）其他常用应用–判断奇偶
.
.
.
（2）字符串的比较.
（3）注意不同语言（CC++、python、java、go）的语法不一样，但是思想是一样的
.
.
通过比较来决定元素间的先对次序，由于其时间复杂度不能突破O(nlogn)，因此也称为非线性时间比较类排序
（1）交换排序 1）冒泡排序（重要）（1）原理
嵌套循环，每次查看相连的元素如果逆序，则交换
（2）代码实现
.
2）快速排序（重要）（1）原理
【分治的思想】数组取标杆元素t,将小元素放在pivo元素t左边，将大元素放在pivot元素右边， 然后依次对右边和 右边的子数组快速排序；以达到整个序列有序的目的
（2）快速排序的步骤
（1）【选杆】从未排序的数组中选择一个基准值（标杆元素t） 【标杆元素t的选取必须在要排序列表的上下界内，它的选取决定了排序的时间复杂度， 一般选择要排序列表的第一个元素】 （2）【分区】在未排序的数组中找出比标杆元素t小的元素，组成一个新的数组； 同理，在未排序的数组中找出比标杆元素t大的元素，组成一个新的数组； （3）【分治】新的两个数组重复步骤（1）（2）步骤，在进行快速排序，直到排序完成 （4）【合并】公式：有序的数组=左边有序的小数组 + 标杆元素t + 右边的大数组
（3）代码实现
def quicksort(array): #array时要排序的数组
if len(array) < 2: #递归退出条件：为空或者只包含一个元素的数组是有序的
return array
else:
pivot = array[0] #递归进入条件：选择要排序数组的第一个元素，第一个元素一定在该数组的上下界内
less = [i for i in array[1:] if i <= pivot] #由所有小于基准值的元素组成子数组
greater = [i for i in array[1:] if i > pivot] #由所有大于基准值的元素组成子数组
return quicksort(less) + [pivot] + quicksort(greater) #开始递归，并合并数组
print quicksort([2,5,8,3,4])
（4）快速排序的特征
（1）快速排序用到了分治（D&C）的思想 （2）快速排序是一种常用的排序算法，比选择排序快的多 （3）C语言标准库中的函数qsort实现的就是快速排序的功能，基本的功能C/C++、python的库都有集成 （4）快速排序的时间复杂度是不唯一的，因为快速排序的性能高度依赖基准值的选取，平均的时间复杂度为O（nlogn）
.
（2）插入排序 1）插入排序（重要）（1）原理
从前到后逐步构建有序序列；对于未排序数据，在已排序序列中从后向前扫描，找到相应的位置并插入【每次只扫描未排序的值】
.
（2）代码实现
.
2）希尔排序.
（3）选择排序 1）选择排序（重要）（1）选择排序原理
每次都遍历整个数组（队列）的每个元素，找出最大或者最小的元素，并将该元素添加到另外一个新的列表起始位置中，每一次循环旧的列表就少一个元素，新的列表就多一个元素
（2）代码实现
def findsmallest(arr): #输入一个无序的数组，寻找他的最小值
smallest = arr[0] #假设数组的第一个元素就是最小值，储存最小的值
smallest_index = 0 # 储存最小值的坐标
for i in range(1 ,len(arr)): #遍历整个无序的数组，寻找最小值
if arr[i] < smallest:
smallest = arr[i]
smallest_index = i
return smallest_index
def selectionSort(arr): #选择排序法
newarr = [] #创建一个新数组，用于储存有序序列
for i in range(len(arr)): #遍历整个数组长度
smallest = findsmallest(arr) #找出数组最小值
newarr.append(arr.pop(smallest)) #把最小值添加到新的数组中
return newarr
print selectionSort([3,65,8,34,3,6,3])
（3）注意
很多语言的库里面丢内置了排序算法的实现
.
2）堆排序.
（4）归并排序 1）二路归并排序（重要）（1）原理
1、把长度为n的输入序列分成两个长度为n/2的子序列 2、对着两个子序列分别采用归并排序 3、将两个排序好的子序列合并成一个最终的排序序列
（2）代码实现
.
2）多路归并排序.
（3）非比较类排序（针对整型的数据类型）不通过比较来决定元素间的相对次序，它可以突破基于比较排序的时间下界，以显示时间运行，因此也称为线性时间非比较类排序
（1）桶排序 （2）计数排序 （3）基数排序.
（4）排序总结归并排序和快速排序具有相似性，但是步骤相反
归并排序：先排序左右子数组，然后合并有序的子数组
快速排序：先调配出左右子数组，然后对于作呕有子数组进行排序
.
.
（1）简单暴力查找原理
使用for循环、或者while循环遍历并判断每个元素，直到找到要查询的元素输出下标
（2）简单暴力查找的特征
（1）把每一个节点元素都遍历一次 （2）简单暴力查找适合节点元素不多的情况 （3）简单暴力查找的时间复杂度是一个正比例函数，当元素较少时，优势差距不大（2）二分查找（适合元素多的，但是要先排序）
（1）二分查找的前提
（1）查找目标是有序的，目标是具有单调性，单调递增或者单调递减 （2）查找的目标具有上下界 （3）能够通过下标或者索引进行查找
（2）二分查找的原理
二分查找输入的是一个有序的元素列表和要查找的元素值， 每次取该有序列表的中间位置的元素和要查找的元素进行对比， 若相等即找到元素的位置，直接输出下标值， 若要查找的目标值大于中间值，则修改下标为中间值下标加一； 若要查找的目标值小于中间值，则修改上标为中间值下标减一；循 环这个过程，直到找到元素为止。
（3）二分查找的程序模板
def binary_search(list,item): #list时要查询的有序单调数组，item是要查询的元素的值
low=0 #标记要查询的列表的下标为0
high=len(list)-1 #标记要查询列表的上标为整个列表的长度
while low <= high: #当列表经过二分查找后不断收敛，知道上下标相等时，证明该列表没有该元素
mid = (low + high)/2 #开始二分查找，寻找有序列表的中间值下标
guess = list[mid] #把中间值下标对应的元素取出来
if guess == item: #若中间元素等于要查询的元素，即完成查询，返回元素的下标
return mid
if guess > item: #若中间元素大于要查询的值，说明元素在列表的前半区间，修改上标
high = mid - 1
if guess < item: #若中间元素小于要查询的值，说明元素在列表的后半区间，修改下标
low = mid + 1
return None
my_list = [1,3,5,7,9]
if __name__ == '__main__':
print binary_search(my_list,3)
（4）二分查找的特征
1、二分查找输入的是一个有序的元素列表，如果要查找列表中的元素，二分查找要么返回该元素的位置下标，要么寻找不到，返回null 2、使用二分查找算法，猜测的是中间的数字，每次都能排除一般以上的数字 3、二分查找的时间复杂度时一个对数函数，要查找的元素越多，优势越明显
.
（3）总结二分查找比简单暴力查找的查询速度快得多，特别在元素数量特别多的时候，但是对于无序的数组列表要应用二分查找前必须进行排序
.
.
（1）每个节点都要访问一次 （2）每个节点最好仅仅访问一次 （3）对于节点是无顺序的，常常使用暴力循环搜索；对于节点是有顺序的，深度优先或者是广度优先搜索（2）搜索遍历的方法 1）所有节点的循环暴力搜索
原理：全部元素遍历一次，无脑操作
.
2）广度优先（breadth first search）搜索【解决无权重图问题】（1）广度优先搜索算法的目的
【解决路径最短问题】：找到起始节点和目标节点两个节点之间的最短距离， 当然，最短距离的含义有很多，进而根据这个最短距离的路径，我们可以大大减小时间复杂度！！【类似于路径规划】
（2）广度优先搜索算法解决的问题
（1）第一类问题：从节点A出发，有前往节点B的路径吗？ （2）第二类问题：从A节点出发，前往节点B的哪条路径最短
（3）广度优先搜索算法部署步骤
（1）使用图的数据结构创建问题模型,包括图模型的节点和图模型的边 【一般来说，节点是对象，边是对象与对象的关系】 （2）使用广度优先搜索算法解决问题 从距离起始节点最近的一层关系开始搜索，直到把所有节点都遍历一遍
（4）广度优先搜索算法图例
（5）广度优先搜索算法代码模板
（6）广度优先搜索算法的特征
广度优先搜索算法是一种思想，要根据图模型进行部署的 当处理树型结构时不需要记录每个节点被访问过的情况，因为不会产生冲突， 但是处理图型结构的时候需要记录每个节点被访问过的情况，因为图有回环，会被无限的访问，增大时间复杂度
（7）广度优先搜索算法的示例
面临类似于寻找最短路径的问题时，可以尝试使用图来建立模型，在通过广度优先搜索算法来解决问题
.
.
（1）图例
（2）代码模板
（1）查找节点 （2）处理当前逻辑 （3）递归到下一层 （4）恢复当前层的状态
.
4）Dijkstar算法【解决加权图问题】（1）路径和轨迹概念的区分
（1）路径的概念 仅仅考虑经过的节点和边的数量关系的路线 （2）轨迹的概念 不仅仅考虑经过节点和边的数量，还要考虑边的权重，问题模型的约束（如时间、成本等等）问题，规划出来的最优路线
（2）Dijkstar算法的部署步骤
（1）找出“最便宜”的节点--即在本节点花费最小代价能到达的第二个节点
（2）先更新第二个节点到邻居节点的代价，后检查前往邻居节点是否存在更短（更低代价）的路径，
若有则更新其代价【基于贪心的思想】
（3）重复上述（1）（2）的过程，直到图中的每个节点都遍历了一次
（4）通过回溯前面的路径，计算出最终的路径
（3）Dijkstar算法的注意点
（1）若遇到带环的图，通过标记访问过的节点，从而避开环的路径 （2）面临类似于寻找最短路径的问题时，可以使用图来建立模型，在通过Dijkstar算法来解决问题 （3）Dijkstar算法不能解决负权边的问题
（4）Dijkstar算法的应用案例
（1）旅行商 （2）换钢琴问题
.
5）启发式搜索（也称优先级搜索A*）【解决加权图问题】.
6）剪枝搜索1）图例
2）例子
例子一：九子棋
例子二：围棋
3）原理
只往前看，不会回溯，走一步选择就少一些，不断减少状态空间，时间复杂度会越来越低 遇到重复问题，引用缓存，避免重复运算 数据结构用剪枝实现，后来发展为深度学习的方法，也是异曲同工的
.
7）双向搜索.
（3）搜索遍历顺序 （1）前序遍历（pre-order）【根-左-右的顺序】 （2）中序遍历(in-order)【左-根-右的顺序】 （3）后序遍历(post-order)【左-右-根的顺序】 （4）相关应用–路径规划搜索具体参考我的博客
【路径生成–图搜索的思想】DFSBFSDFS-ID搜索算法
【路径生成–图搜索的方法】贪心算法、Dijkstra和A*类路径搜索算法【经典】
.
.
（1）递归的原理
函数自己调用自己，解决问题方法的重复性较高时，可以使用递归的算法
（2）递归模板
（1）模板代码 def recursion(输入递归的参数) if （退出递归条件） 退出递归的操作 本层处理 if （进入递归条件） 进入递归的处理 本层状态清理 （2）模板步骤 （1）确定进入递归的条件和退出递归的条件：由于递归函数是自己调用自己的，因此这样编写函数很容易出错，进而导致无限循环，程序无法退出 （2）本层处理 （3）进入递归条件 （4）本层状态清理
（3）递归的例子
（1）阶乘函数的实现 def fact(x): if x == 1: return 1 else: return x * fact(x-1)
（4）递归的特点
（1）递归的原理结构更容易理解和编程实现
（2）递归算法不一定计算的时间复杂度低
（3）递归只是一种问题的解决思路，并不是一种具体的实现方法
（4）递归子函数的不断创建，都会创建子函数空间，每个递归子函数都是独立的，
因此当递归的循环次数较多的时候，会耗费较多的 内存空间
.
.
（1）模板代码
（2）模板步骤
（1）递归退出条件【这个必须越简单越好】 （2）本层处理 1）把大问题拆分成几个小问题，缩小问题规模，直到小问题符合递归退出条件 2）处理小问题 （3）递归进入条件 （4）本层状态清理
（3）分治的核心思想
本质是递归，区别是深入的把一个问题化解成好几个子问题，找子重复问题
.
.
（1）回溯法的核心思想
回溯法采用了试错的思想，尝试分步的去解决一个问题， 在分步解决问题的过程中，当它通过尝试现有分类答案不能得到有效的正确的解答的时候，它将取消上一步甚至上几步的计算， 在通过其他可能的分步解法再次解答，再次寻找问题的答案
（2）回溯法的实现
回溯法通常使用最简单的递归的方法实现
（3）回溯法的结果
要么在没尝试完所有的可能时找到一个存在的正确的答案，要么就尝试所有的可能后宣布无解， 最坏的情况，回溯法会导致一个复杂度为指数的时间计算（4）总结
（1）人肉递归的效率很低、很累，自己画状态树
（2）找到最近最简的方法，将大问题拆解成为可重复解决的子问题，计算机本质是寻找重复性，并生成三种结构（顺序，循环、条件）的计算机指令集
（3）熟练掌握数学归纳法，举例找规律
.
.
（1）贪心算法的核心思想
贪心算法是一种在每一步选择中都采取再当前状态下最优的选择，从而希望结果是全局近似最优的算法
（2）贪心算法的实现步骤
（1）使用列表、树/图等的数据结构创建问题模型 包括图模型的节点和图模型的边 【一般来说，节点是对象，边是对象与对象的关系】 （2）使用贪心算法的核心算法解决问题 （0）把问题分解成为子问题来解决 （1）【解决问题一】找到当前最好的选择的项（尽可能满足所有需求的项） （2）【解决问题二】找到满足剩余需求的第二、第三项 （3）把所有的小问题并集起来，即计算出大问题的近似解
（3）贪心算法的特征
（1）算法简单，易于实现，时间复杂度较低 （2）求出来的近似解通常非常接近最优解 （3）贪心算法仅仅时一个思路，没有具体的实现方法，但是可以参考模板总结经验做部署
（4）贪心算法的应用
（1）全覆盖问题 （2）旅行商问题 （3）适合解决单约束问题【有时候约束和约束之间也会有耦合，要学会简化约束】
（5）贪心算法的效果评价
（1）看看运行速度有多快，满不满足要求 （2）看看得到的近似解和最优解的接近程度，满不满足要求
（6）贪心算法和其他算法的特征对比
贪心算法：当下做出及局部做优的判断 回溯算法：保存当前结果，并可以回退 动态规划算法：最优判度+回退
.
.
（1）最优子结构概念
问题能够分解成为子问题来解决，子问题的最优解能地推到最终问题的最优解。这种子问题最优解成为最优子结构
（2）动态规划的核心思想
当面对多约束的无解问题时，确定目标需求和约束条件，把问题分解成为主要问题和次要来解决， 通过创建表格，最优填表的方式解决好每个子问题，从小问题着手，取并集后逐步解决大问题
（3）动态规划的实现步骤
（0）确定目标需求和约束条件 （1）根据约束建立网格（一般网格是针对两个约束的）[x轴是约束一、y轴是约束二] （2）以当前最优解的方式填充网格 （3）从全局来看，先选择解决主要矛盾的问题（收益最大的问题），在解决完主要矛盾问题后，再根据剩下的资源，解决次要矛盾问题 （4）把大小问题独立解决后，合并多个子问题并解，就得到大问题近似最优解
（4）动态规划的模板
（5）动态规划的注意
（1）建立表格时，行列约束交换不会影响最终结果 （2）建立好表格后，突然要增加一个行元素选择和列元素选择，不用推倒重来，不影响结果的计算过程 （3）表格既可以逐行填充，也可以逐列填充，以不同的角度解决子问题不会影响最终结果 （4）在计算过程中添加新的约束条件，相当于把表格从二维扩展到三维【模型都变了】，必然影响优化的结果 （5）动态仅仅时一个思路，没有具体的实现方法，但是可以参考模板总结经验做部署（3）总结
递归、分治、回溯、动态规划，思想越来越成熟，实现难度越来越大
.
.
.
布隆过滤器是一种概率型数据结构，大概查询一下元素是否在数据库里面，若查询结果显示不在，就肯定不在，若查询结果表示在，实际上是可能在，需要进一步进行判断
（3）布隆过滤器的优缺点（1）优点：查询速度十分快速，消耗时间和内存都比较小，可以做一个数据的与过滤
（2）缺点：判断不存在 100% 准确，判断存在有误差
.
.
k最近邻算法（KNN）是一种简单的机器人学习算法，先把对象按照特征进行分类，根据每个类别的特征相似程度划分邻居，物以类聚，人与群分的思想，我的类别应该和我的邻居的类别相似，从而判断出我时属于哪一类的
.
（2）k最近邻算法（KNN）的实现步骤（1）【特征抽取编组】根据要分类的对象，确定对象的特征，根据特征的数目建立表格（若是两个特征则建立一个二维的表格），并把大量的对象根据特征填写进去表格里面【相当于机器学习的训练过程–整定权重表】
（2）【回归预测数值】根据两个对象的相对位置，计算两个对象的距离（使用空间两点间的距离公式，当然这个公式可以扩展到5维度甚至更高），距离值越小证明相似程度越高
.
（3）k最近邻算法（KNN）的应用（1）分类系统 （2）推荐系统
.
.
（1）【准备数据】进行图像增强，划分数据集和测试集，并进行图像标定 （2）【训练数据】查看大量数字图像并提取特征 （3）得到训练的探测器的权重表（特征分布表） （4）放入测试集，通过回归公式评价训练得到的权重表效果（2）机器学习（深度学习）应用
（1）光学字符识别（OCR） （2）垃圾邮件过滤器
总结
毕竟公司就是既要“优化”计算机性能，也要“优化”人脑编程思考能力，好的算法运行稳定性和成本都十尽可能低的。
