算法图解学习笔记

た入场券 2022-09-07 12:28 24阅读 0赞

### **算法** ###

*  一组完成任务的指令
 *  任何代码片段

### **算法小结** ###

<table> 
 <thead> 
 <tr> 
 <th>序号</th> 
 <th>算法</th> 
 <th>说明</th> 
 <th>大O表示</th> 
 <th>举例说明</th> 
 <th>注意事项</th> 
 </tr> 
 </thead> 
 <tbody> 
 <tr> 
 <td style="border-color:#cccccc;">1</td> 
 <td style="border-color:#cccccc;">二分查找</td> 
 <td style="border-color:#cccccc;">输入：有序元素列表; 运行：找中间值和目标值比较，小于目标值的话将开始值置为中间值的后一个，大于目标值的话将结束值置为中间值的前一个，一次类推，直到找到目标值</td> 
 <td style="border-color:#cccccc;">O(log2n)</td> 
 <td style="border-color:#cccccc;">100个元素10次； 40亿个元素32次；</td> 
 <td style="border-color:#cccccc;"></td> 
 </tr> 
 <tr> 
 <td style="border-color:#cccccc;">2</td> 
 <td style="border-color:#cccccc;">选择排序</td> 
 <td style="border-color:#cccccc;">每次遍历O(n),遍历n次 (注：随着排序的进行，每次需要检查的次数在逐渐减少，最后一次需要检查的元素都只有一个，平均每次检查的次数为1/2n,及O（n1/2 *n）---大O表示法省略常数，简答的写做O（n2）)</td> 
 <td style="border-color:#cccccc;">O(n2)</td> 
 <td style="border-color:#cccccc;"></td> 
 <td style="border-color:#cccccc;"></td> 
 </tr> 
 <tr> 
 <td style="border-color:#cccccc;">3</td> 
 <td style="border-color:#cccccc;">递归</td> 
 <td style="border-color:#cccccc;">递归实现：函数的自调用【注：使用循环也可以有此效果且程序的性能可能更高，但是使用递归更容易理解】 基线条件：函数不在调用自己，从而避免死循环 递归条件：函数调用自己 栈在递归中扮演重要的角色</td> 
 <td style="border-color:#cccccc;"></td> 
 <td style="border-color:#cccccc;"></td> 
 <td style="border-color:#cccccc;"></td> 
 </tr> 
 <tr> 
 <td style="border-color:#cccccc;">4</td> 
 <td style="border-color:#cccccc;">快速排序</td> 
 <td style="border-color:#cccccc;">使用分而治之的策略 1.找出简答的基线条件 2.确定如何缩小问题的规模，使其符合基线条件 找出基准值，左右分区，然后依次类推下去</td> 
 <td style="border-color:#cccccc;">O(nlogn)，糟糕情况下O(n2 分为logn层，每层n遍历)</td> 
 <td style="border-color:#cccccc;"></td> 
 <td style="border-color:#cccccc;"></td> 
 </tr> 
 <tr> 
 <td style="border-color:#cccccc;">5</td> 
 <td style="border-color:#cccccc;">散列表</td> 
 <td style="border-color:#cccccc;">散列函数总是将相同的输入映射到相同的索引，使用散列函数确认元素的存储位置。 由键值组成 应用：模拟映射关系；防止重复；缓存； 散列表：散列函数+数组</td> 
 <td style="border-color:#cccccc;">O(1)</td> 
 <td style="border-color:#cccccc;">网站缓存</td> 
 <td style="border-color:#cccccc;"></td> 
 </tr> 
 <tr> 
 <td style="border-color:#cccccc;">6</td> 
 <td style="border-color:#cccccc;">广度优先搜索（BFS）</td> 
 <td style="border-color:#cccccc;">解决： 1.节点A是否可以到节点B 2.节点A到节点B最近的路径 算法核心：一层一层的寻找，直到找到目标或者找不到</td> 
 <td style="border-color:#cccccc;">O(V+E) V:顶点 E；边</td> 
 <td style="border-color:#cccccc;">添加队列的时间O(1),顶点和边的总数即时间的总数</td> 
 <td style="border-color:#cccccc;">无加权的图</td> 
 </tr> 
 <tr> 
 <td style="border-color:#cccccc;">7</td> 
 <td style="border-color:#cccccc;">迪克斯特拉算法</td> 
 <td style="border-color:#cccccc;">在图的边加入权重（最快的路径），找出图中最便宜的节点，并确保到该节点没有更便宜的路径 （注：迪克斯特拉算法必须权重为正数。权重中有负数的使用“贝尔曼福德算法”来求解）</td> 
 <td style="border-color:#cccccc;">O(n2)</td> 
 <td style="border-color:#cccccc;"></td> 
 <td style="border-color:#cccccc;">加权的图，且权重必须为整数；有负数的图用“贝尔曼-福德”算法</td> 
 </tr> 
 <tr> 
 <td style="border-color:#cccccc;">8</td> 
 <td style="border-color:#cccccc;">贪婪算法</td> 
 <td style="border-color:#cccccc;">每步选择局部的最优解，最终得到的就是全局最优解</td> 
 <td style="border-color:#cccccc;"></td> 
 <td style="border-color:#cccccc;"></td> 
 <td style="border-color:#cccccc;">对于NP完全问题，还没有找到快速解决方案，最佳的做法是使用近似算法</td> 
 </tr> 
 <tr> 
 <td style="border-color:#cccccc;">9</td> 
 <td style="border-color:#cccccc;">动态规划</td> 
 <td style="border-color:#cccccc;">将棘手的问题分成小问题，并先解决这些小问题，小问题的粒度根据分解问题的最小单元来定</td> 
 <td style="border-color:#cccccc;"></td> 
 <td style="border-color:#cccccc;"></td> 
 <td style="border-color:#cccccc;">使用动态规划时，要么考虑拿走整件商品，要么考虑不拿，而没法判断该不该拿走商品的一部分；仅当问题是离散的，不依赖其他的子问题时，动态规划才管用</td> 
 </tr> 
 <tr> 
 <td style="border-color:#cccccc;">10</td> 
 <td style="border-color:#cccccc;">K最近邻（KNN）</td> 
 <td style="border-color:#cccccc;"></td> 
 <td style="border-color:#cccccc;"></td> 
 <td style="border-color:#cccccc;"></td> 
 <td style="border-color:#cccccc;">可以用在分类上，特征提取，抽象的问题具体化（例：水果对比--颜色、个头），用在回归；分类就是编组，回归就是预测结果</td> 
 </tr> 
 <tr> 
 <td style="border-color:#cccccc;">11</td> 
 <td style="border-color:#cccccc;">树</td> 
 <td style="border-color:#cccccc;">二叉树：对于其中的每个节点，左子节点的值都比他小，右子节点的值都比他大；插入和删除快，不能随机访问</td> 
 <td style="border-color:#cccccc;"></td> 
 <td style="border-color:#cccccc;"></td> 
 <td style="border-color:#cccccc;">平衡状态的特殊二叉树--红黑树；特殊的二叉树，存储数据--B树</td> 
 </tr> 
 <tr> 
 <td style="border-color:#cccccc;">12</td> 
 <td style="border-color:#cccccc;">反向索引</td> 
 <td style="border-color:#cccccc;">常用于搜索引擎：一个散列表，例-内容的部分为键，主题为值</td> 
 <td style="border-color:#cccccc;"></td> 
 <td style="border-color:#cccccc;"></td> 
 <td style="border-color:#cccccc;"></td> 
 </tr> 
 <tr> 
 <td style="border-color:#cccccc;">13</td> 
 <td style="border-color:#cccccc;">傅里叶变换</td> 
 <td style="border-color:#cccccc;">“给它一杯冰沙，它能告诉你其中包含哪些成分”</td> 
 <td style="border-color:#cccccc;"></td> 
 <td style="border-color:#cccccc;"></td> 
 <td style="border-color:#cccccc;">非常适合处理信号；地震预测；DNA分析</td> 
 </tr> 
 <tr> 
 <td style="border-color:#cccccc;">14</td> 
 <td style="border-color:#cccccc;">并行算法</td> 
 <td style="border-color:#cccccc;">可扩展性和海量数据，改善性能和可扩展性</td> 
 <td style="border-color:#cccccc;"></td> 
 <td style="border-color:#cccccc;"></td> 
 <td style="border-color:#cccccc;"></td> 
 </tr> 
 <tr> 
 <td style="border-color:#cccccc;">15</td> 
 <td style="border-color:#cccccc;">MapReduce</td> 
 <td style="border-color:#cccccc;">分布式算法</td> 
 <td style="border-color:#cccccc;"></td> 
 <td style="border-color:#cccccc;"></td> 
 <td style="border-color:#cccccc;">Hadoop中使用；映射函数；归并函数；</td> 
 </tr> 
 <tr> 
 <td style="border-color:#cccccc;">16</td> 
 <td style="border-color:#cccccc;">布隆过滤器和HyperLogLog</td> 
 <td style="border-color:#cccccc;">布隆过滤器是一种概率型数据结构--答案很可能是正确的，但是可能不正确</td> 
 <td style="border-color:#cccccc;"></td> 
 <td style="border-color:#cccccc;"></td> 
 <td style="border-color:#cccccc;">布隆过滤器：占用的存储空间少；HyperLogLog：类似布隆器的算法，给出的答案八九不离十</td> 
 </tr> 
 <tr> 
 <td style="border-color:#cccccc;">17</td> 
 <td style="border-color:#cccccc;">SHA算法（安全散列算法）</td> 
 <td style="border-color:#cccccc;">对于输入，对应唯一一个输出，是一个散列函数，根据字符串生成另一个字符串；单向的无法复原</td> 
 <td style="border-color:#cccccc;">O(1)</td> 
 <td style="border-color:#cccccc;"></td> 
 <td style="border-color:#cccccc;">检查文件，检查密码</td> 
 </tr> 
 <tr> 
 <td style="border-color:#cccccc;">18</td> 
 <td style="border-color:#cccccc;">局部敏感的散列算法</td> 
 <td style="border-color:#cccccc;">Simhash</td> 
 <td style="border-color:#cccccc;"></td> 
 <td style="border-color:#cccccc;"></td> 
 <td style="border-color:#cccccc;">网页是否收集；检查论文；版权</td> 
 </tr> 
 <tr> 
 <td style="border-color:#cccccc;">19</td> 
 <td style="border-color:#cccccc;">Diffe-Hellman秘钥交换</td> 
 <td style="border-color:#cccccc;">加密消息，公钥和私钥</td> 
 <td style="border-color:#cccccc;"></td> 
 <td style="border-color:#cccccc;"></td> 
 <td style="border-color:#cccccc;">双方无需知道加密算法，要破解加密的消息比登天还难</td> 
 </tr> 
 <tr> 
 <td style="border-color:#cccccc;">20</td> 
 <td style="border-color:#cccccc;">线性规划</td> 
 <td style="border-color:#cccccc;">给定约束条件下最大限度的改善指定的指标</td> 
 <td style="border-color:#cccccc;"></td> 
 <td style="border-color:#cccccc;"></td> 
 <td style="border-color:#cccccc;">simples算法</td> 
 </tr> 
 </tbody> 
</table>

### **知识补充** ###

*  幂运算
    
     *  问将多少个10相乘可以得到100
        
         *  102=100
            
             *  2个10相乘可以得到100
 *  对数运算
    
     *  对数运算是幂的逆运算
        
         *  log10100=2
            
             *  以10为底100的对数是2
 *  大O表示法
    
     *  并非运行算法的运行时间
     *  指出了算法的速度有多快
     *  指的是运行时间的增速
     *  算法的最糟糕的运行时间
 *  数组
    
     *  内存中连续
     *  优势：读取特定位置的元素【读取O(1)】；可以随机访问；
     *  缺点：删除，增加麻烦【插入O(n)】【删除O(n)】
 *  链表
    
     *  内存中不连续，链表中的每一个元素都指向了下一个元素的地址，从而使一系列随机的内存地址串在一起。
     *  优势:插入、删除元素方便【插入O(1)】【删除O(1)】
     *  缺点：读取特定位置的元素【读取O(n)】
 *  阶乘
    
     *  n!=1\*2\*3\*...\*n
 *  内存工作原理
    
     *  需要将数据存储到内存时，请求计算机提供存储空间，计算机给一个存储地址，这个地址是个存放数据的容器的标识；计算机内存犹如一大堆抽屉；
 *  栈
    
     *  后进先出
     *  压栈、弹栈
     *  调用栈：用于存储多个函数的变量【函数中使用:用到函数放入栈，函数结束立即弹出】
        
         *  所有的函数调用都进入调用栈
     *  缺点：可能占用大量的内存，可用循环来解决
 *  函数式编程
    
     *  函数式编程语言学习更容易，例Haskell
 *  归纳证明
    
     *  基线条件和归纳条件
        
         *  证明我能爬到梯子的最上面
            
             *  “如果我站在一个横档上，就能将脚放到下一个横档上，换言之，我站在第二个横档上，就能爬到第三个横档上，这就是归纳条件。基线条件是：我已经站到了第一个横档上。因此，通过每次爬一个横档，我就能爬到梯子的最顶端”
 *  平均情况和最糟情况
    
     *  平均情况
        
         *  最优的步骤将结果输出
     *  最糟情况
        
         *  全部的步骤结束后才将结果输出
 *  散列函数
    
     *  无论输入是什么，输出的都是一个数字
     *  输入和输出是对应的，每次的输出的结果一致
     *  问题：冲突
     *  实现
        
         *  装填因子（散列包含的元素/位置总数）
         *  调整长度（装填因子大于1后进行扩增--经验规则装填因子0.7时进行扩增）
 *  图相关
    
     *  图
        
         *  由节点（node）和边组成（edge），一个节点可能与众多的节点直接相连，这些节点称为邻居
            
             *  实现
                
                 *  散列表的表示
                    
                    #  #
                    
                        graph = {} graph["you"] = ["alice", "bob", "claire"] graph["bob"] = ["anuj", "peggy"] graph["alice"] = ["peggy"] graph["claire"] = ["thom", "jonny"] graph["anuj"] = [] graph["peggy"] = [] graph["thom"] = [] graph["jonny"] = []
     *  有向图
        
         *  有出发和终点的图（箭头指向）
         *  边为箭头，箭头的方向指定了关系的方向
     *  无向图
        
         *  没有箭头，之间连接邻居节点的图
         *  关系是双向的
         *  每条边都是环
     *  加权图
        
         *  带权重的图称为加权图（即边上面加入了权重）
            
             *  父节点
             *  负权边：权重为负
 *  树
    
     *  树是一种特殊的图，其中没有往后指的边
 *  队列
    
     *  先进先出，只有入队和出队
 *  NP完全问题
    
     *  以难解著称，如旅行商问题和集合覆盖问题
     *  元素较少时算法的运行速度非常快，随着元素的增加，速度会变得非常慢
     *  涉及“所有组合”的问题通常是NP完全问题
     *  不能将问题分成小问题，必须考虑各种可能的情况
     *  涉及序列且难以解决
     *  涉及集合且男以解决
     *  问题可转换或为集合覆盖问题
 *  回归
    
     *  平均值？
 *  余弦相似度
    
     *  余弦相似度不计算两个矢量的距离，而是比较他们的角度
     *  余弦值的范围在\[-1,1\]之间，值越趋近于1，代表两个向量的方向越接近；越趋近于-1，他们的方向越相反；接近于0，表示两个向量近乎于正交。
 *  机器学习
    
     *  大量的数据并提取特征--训练
     *  优化指正
     *  新的场景输出结果
 *  OCR
    
     *  光学字符识别，计算机将自动识别印刷页面的照片【线段、点、曲线特征】