算法图解阅读笔记

二分查找：针对有序的元素列表

运行时间：O表示

几种运行时间：
O(log n)：对数时间
O(n)：线性时间
O(n*log n)：快速排序
O(n*n)：选择排序
O(n!)：旅行商算法

大O表示法：省略法，O(nn)实际上可能是O(1/2nn)，只是省略了常数而已

运行时间，并非指时间，而是增速，随着元素的增多，速度增快。

操作数：O(log n)，其中log n是操作数。

O(n)中的n中的n指的是c*n ，c指的是算法所需固定时间量，比如：休眠时间，通常不考虑这个常量。

练习：
使用大O表示法时，下面各种操作都需要多长时间？

1 　打印数组中每个元素的值。

2 　将数组中每个元素的值都乘以2。

3 　只将数组中第一个元素的值乘以2。

4 　根据数组包含的元素创建一个乘法表，即如果数组为[2, 3, 7, 8, 10]，首先将每个元素 都乘以2，再将每个元素都乘以3，然后将每个元素都乘以7，以此类推。

快速排序
内存中存储一些元素，选择方式：数组、链表

数组、链表的优缺点：
1.数组位置紧密相连，插入数据的同时需要移动其他元素。链表的位置并非紧密相连，采用位置预留的方式，上一个元素中记录下一个元素的位置。
2.数组支持随机访问，读取速度快。链表需要上一个元素找到下一个元素的位置，读取速度慢。

所以从读取、写入、删除的表现来看：

随机访问、顺序访问

递归：递归只是让解决方案更加清晰，实际上性能方面不一定会有优势

基线条件：跳出递归的条件

递归条件：调用自己本身的条件

调用栈：所有的函数调用都进入调用栈，调用栈占内存

调用栈两个操作：压入、弹出
1.调用函数1，分配一块内存，记录函数名称、函数变量、变量值等
2.调用函数1，还未返回结果的同时，调用函数2，函数1处于暂停并处于未完成状态
3.函数2返回结果之后被弹出（也就是删除并查看）
以上的内存块也就是调用栈。

递归调用栈

栈使用很方便，但每次调用函数，都占内存，存储的数据越详尽，调用函数越多，占用的内存也越多。

栈很长了咋办？1.转而选择使用循环；2.尾递归

题目：
1.编写一个递归函数来计算列表包含的元素数。

2.找出列表中最大的数字。

3.还记得第1章介绍的二分查找吗？它也是一种分而治之算法。你能找出二分查找算法的基线条件和递归条件吗？

快速排序
基准条件：数组为空或者数组只有一个元素的情况下，不需要排序，也就是返回自己即可。

基准值：可以以arr[0]为基准，大于该值放入LArr数组，小于该值放入SArr数组

递归条件：不满足基准条件的条件。返回sArr数组+基准值+lArr数组

基准值的选择决定运行时间：若基准值恰好是中位数，运行时间最短，即平均情况或者最优情况O(nlog n)；若基准值恰好是边界情况，则是最糟情况（O(n*n)）

最优情况也就是平均情况，每次随机找到一个元素作为基准值，即为平均情况。

合并排序：O(nlogn)

总结 ：合并排序与快速排序：大O表示法中的常量有时候影响很大，这就是快速排序比合并排序快的原因所在。

散列表
散列表可以实现O(1)，比二分查找效率更高。
散列表：本质是散列函数+数组
散列函数：将输入映射到数组。1.每次相同的输入有相同的结果；2.将不同的输入映射到不同的数字。
实现：用于查找；防止重复；用作缓存

冲突：运行时间是O(1)是正常情况下比如：1.将键均匀分布在散列表的不同位置；2.散列表存储的链表没有很长。

但是，如果出现上述两种情况相反的情况，比如：键多，位置少，不同的键不得不放在同一位置；相同键对应的存储链表很长，导致在查找的时候运行时间过长。

所以避免冲突可以尽量：1.较低的填装因子；2.良好的散列函数
填装因子是：分布的键/总位置数，也就是被占用的位置数的比例。

总结：
散列表的查找、插入、删除速度都很快
散列表适合用于仿真映射关系
一旦填装因子超过0.7，就该调整散列表的长度

广度优先搜索
问题：1.A–>B的路径是否存在；2.A–>B的最短路径

解决方案：用图创建模型，使用广度优先搜索

图的概念：有向图、无向图。有向图是单方向箭头；无向图是双向的。

广度优先搜索借助一种数据结构：队列
队列：先进先出 First In First Out
栈：后进先出 Last In First Out
类似栈有压入、弹出的操作，队列有入队、出队的操作。

广度优先搜索怎么借助队列的？
1.将A、B…的关系用散列表的数据结构表示.“A”,[B,C,D]；“B”,[E,F,G]
2.根据A，将A所有邻居找出来，放在队列中。比如B、C、D
3.判断B是否是终点，否，B的键找出来，放在队列里。依次直到队列为空或者找到了终点。
4.需要在判断之前，加一层是否已经检查过的判断，检查过的数据，跳过。

需要按照加入顺序检查搜索列表的人，否则找到的的就不是最短路径，因此搜索列表必须是队列。

对于检查过的人，务必不要再去检查，否则可能导致无限循环

运行时间：O(V+E)，其中V是节点数，E是边数，也就是，访问每个节点的时间O(1) 与将检查节点对应的每个键加入队列的时间O(1)

拓扑排序：A依赖于B，所以A在B后面。

树：没有往后指的边。

狄克斯特拉算法：加权重计算最短路径

实现过程：
1.从起点开始找便宜节点、记录该节点对应的父节点，并且找到该节点的所有邻居，计算该节点所有邻居的花销；
2.如果有更短路径，更新邻居节点的开销与其父节点；
3.当前节点标记为已处理；
4.重复上述操作，直到完成所有节点的邻居开销与父节点录入；
5.计算最短路径，也就是最短路径的花销与各个节点与节点的顺序。

创建三个散列表，分别记录：每个节点与下一个节点的花销【已知条件】；节点花销散列表；父节点散列表
其中花销与父节点散列表，根据路径长度比较，确认是否更新、新增等操作。

创建数组：用于记录已处理的节点，对于同一节点不用处理多次。

特殊情况：权重为负的情况，不适用于狄克斯特拉算法

总结：
广度优先搜索用于非加权图中查找最短路径；
狄克斯特拉算法用于在加权图中查找最短路径；仅当权重为正时狄克斯特拉算法才管用
如果途中包含负权边，使用贝尔曼-福德算法。

贪婪算法
NP完全问题：不可能完成的任务。

近似算法：可以得到NP完成问题的近似解。

识别NP完全问题：元素较少的情况下算法运行速度快，随着元素增多，运行速度变慢。设计“所有组合”的问题通常是NP完全问题，不能将问题分解成小问题。

贪婪算法：找到局部最优解，最终得到全局最优解。

有几类问题：
集合覆盖问题
1.记录所有需要覆盖的点到集合
2.遍历当前存在的所有未选择的点，最大范围覆盖未覆盖的区域的节点，作为下一个点，直到步骤一种的集合为空。

旅行商问题
1.随机找到一个出发点；2.遍历距离当前节点最近的地点，作为下一个目的地，直到处理完所有的地点，结束。

动态规划
先解决子问题，在逐步解决大问题。

每种动态规划解决方案都设计网格

背包问题：背包载重固定，向背包中放入物品，使其价值最大。（不考虑商品可以重复选择的情况）
1.分解问题，将载重分为归为1,2，3,4磅；
2.针对不同的物品，列网格，当前格支持该行物品与该行以上物品可供选择，找到满足载重的最优解；

背包问题，一些注意点
1.行排列顺序变化不影响结果；
2.商品的单位变小，可以通过改变粒度，调整网格；
3.如果商品可以多选，挑选价值最大的商品先放，直到拿完，再选择剩余商品中价值最大的商品，直到拿完。

旅游行程最优解：变相的背包问题
1.列出每段行程的耗时与价值；
2.形成网格，填充，找到固定天数中，价值最大的几段行程。

但是，这里没有考虑景点之间的距离，相互依赖的关系，也就是说对于这几段旅程，路上的时间是微不足道的。
如果几段行程之间存在依赖关系，比如A–>B需要1天时间，C–>B需要1.5天时间。这种情况，动态规划是无法解决的。

最长公共子串问题
两种情况：1.得到最相似的两个字符串，也就是相同位的字符相同，数量越多，越相似。2.得到最长公共子串，相同位上的连续字符相同，数量越多，成为最长公共子串的可能性越大。

两者相似，只是处理方式不同。
前者，判断，若字符相同，则网格左上方邻居+1；若字符不同，则取网格上方或左方大值
后者，判断，若字符相同，则网格左上方邻居+1；若字符不同，则为0

小结：
1.在给定约束条件下优化某种指标时，动态规划很有用；
2.问题可分解为离散子问题时，可使用动态规划来解决；
3.单元格中的值，通常就是要优化的值；
4.每个单元格都是一个子问题，因此，需要考虑如何将问题分解为子问题；
5.没有放之四海皆准的计算动态规划解决方案的公式。

应用：
DNA链相似性，两种动物或疾病的相似性；寻找多发性硬化症状治疗方案；git diff

K最近邻算法
KNN算法
分类系统、特征提取、预测数值（回归）

最后

以上就是忧伤招牌为你收集整理的算法图解阅读笔记的全部内容，希望文章能够帮你解决算法图解阅读笔记所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。