算法图解(C语言)

第一章 算法简介

一些常见的大O运行时间（以排序算法举例）

O(log n), 也叫对数时间，这样的算法包括二分查找。

O(n) , 也叫线性时间，这样的算法包括简单查找。

O(n*log n),快速排序——一种较快的排序算法。

O(n^2), 选择排序——一种较慢的排序算法。

O(n!), 旅行商问题解决方案—一种非常慢的算法。

一些小启示

1.算法的速度指的并非时间，而是操作数的增速。

2.谈论算法的速度时，我们说的是随着输入的增加，其运行时间将以什么样的速度增加。

3.算法的运行时间用大O表示法表示。

4.O(log n)比O(n)快，当需要搜索的元素越多时，前者比后者快的越多。

小结

1.二分查找的速度比简单查找快的多。

2.O(log n) 比 O(n)快，需要搜索的元素越多，前者比后者快的就越多。

3.算法运行时间并不以秒为单位。

4.算法的运行时间是从其增速的角度度量的。

5.算法运行时间用大O表示。

第二章 选择排序

数组与链表

数组：所有元素所在内存相连。

访问方式：随机访问。

优点：可以快速查找到任何一个元素。

缺点：1.申请内存过多容易浪费，2.需要内存超过申请内存时需要转移。

链表：所有元素可存储在内存的任何地方。

访问方式：顺序访问。

优点：有内存就能插入元素。

缺点：不能进行随机查找，需要一个一个顺序查找。

小结

1.计算机内存犹如一大堆抽屉。

2.需要储存多个元素时，可使用数组或链表。

3.数组的元素都在一起。

4.链表的元素是分开的，其中每个元素都存储了下一个元素的地址。

5.数组的读取速度很快。

6.链表的插入和删除速度很快。

7.在同一个数组中，所有的元素类型都必须相同（都为int，double等）。

第三章 递归

套娃问题

循环：程序的性能更高

递归：程序性能更容易理解

递归函数两大组成部分：基线条件和递归条件

递归条件：函数调用自己

基线条件：函数不再调用自己，从而避免无限循环

栈过高的处理方法

1.重新编写代码，转而使用循环。

2.使用尾递归(注意：并非所有语言都支持尾递归)。

小结

1.递归指的是调用自己的函数。

2.每个递归都有两个条件：基线条件和递归条件。

3.栈有两种操作：压入和弹出。

4.所有函数都进入调用栈。

5.调用栈可能很长，这将占用大量内存。

第四章 快速排序

土地均分问题

**D&C算法(递归)**解决问题的两个步骤：

1.找出基线条件，这个条件必须尽可能简单。

2.不断将问题分解(或者说缩小规模)，直到符合基线条件。

（注：D&C并非可用于解决问题的算法，而是一种解决问题的思路）。

温馨提示：编写涉及数组的递归函数时，基线条件通常是数组为空或只包含一个元素。陷入困境时，请检查基线条件是不是这样的。

欧几里得算法：https://blog.csdn.net/m0_46108436/article/details/104227056?ops_request_misc

快速排序（全）：https://blog.csdn.net/f_zyj/article/details/51484751

（D&C典范，最快排序算法之一 平均情况O(nlog n),最坏O(n^2)）

小结

1.D&C将问题逐步分解。使用D&C处理列表时，基线条件很可能是空数组或只包含一个元素的数组。

2.实现快速排序时，请随机地选择用作基准值的元素，快速排序的平均运行时间为O(nlog n)。

3.大O表示法中的常量有时候事关重大，这就是快速排序比合并排序快的原因所在。

4.比较简单查找和g二分查找时，常量几乎无关重要，因为列表很长时,O(nlog n)的速度比O(n)快的多。

第五章 散列表

散列函数的必须要求

1.它必须是一致的。例如，假设你输入apple时得到的是4，那么每次输入apple时，得到的都必须是4。如果不是这样，散列表将毫无用处。

2.他应将不同的输入映射到不同的数字。例如，如果一个散列表函数不管输入是什么都返回1，它就不是好的散列函数。最理想的情况是，将不同的输入映射到不同的数字。

散列函数的特点

1.散列函数总是将同样的输入映射到相同的索引。每次你输入avocado，得到的都是同一个数字。因此，你可以首先使用它来确定将鳄梨的价格存储在什么地方，并在以后使用它来确定鳄梨的价格存储在什么地方。

2.散列函数将不同的输入映射到不同的索引。avocado映射到索引4，milk映射到索引10.每种商品都映射到数组的不同位置，让你能够将其价格存储到这里。

3.散列函数知道数组有多大，只返回有效索引。如果数组包含5个元素，散列函数就不会返回无效索引100。

散列表简单实现流程：https://blog.csdn.net/DFGOMC/article/details/110083711

“冲突解决方法”

尽力避免冲突方法

散列表适合于

1.模拟映射关系。

2.防止重复。

3.缓存记住数据，以免服务器再通过处理来生成它们。

第六章 广度优先搜索

广度优先搜索适用问题

第一类问题：从节点A出发，有前往节点B的路径吗？

第二类问题：从节点A出发，前往节点B的哪条路径最近？

解决方案：https://www.cnblogs.com/skywang12345/p/3711512.html#anchor2

队列

队列是一种先进先出的数据结构，而栈是一种先进后出的数据结构。

小结

1.广度优先搜索指出是否有从A到B的路径。

2.如果有，广度优先搜索将找出最短路径。

3.面临类似于寻找最短路径的问题时，可尝试使用图来建立模型，再使用广度优先搜索来解决问题。

4.有向图中的边为箭头，箭头的方向指定了关系的方向，例如：rama—>adit表示rama欠adit钱。

5.无向图中的边不带箭头，其中的关系时双向的，例如：ross—rachel表示“ross与rachel约会，而rachel也与ross约会”。

6.队列是先进先出(FIFO)的。

7.栈是后进先出(LIFO)的。

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

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

第七章 狄克斯特拉算法

狄克斯特拉算法背后的关键理念：

找出图中最便宜的点，并确保没有到该节点的更便宜的路径。

狄克斯特拉算法四个步骤：

1.找出最便宜/短的点，即可在最短时间内前往的点。

2.对于该点的邻居，检查是否有前往他们的更短路径，如果有，就更新其开销。

3.重复这个过程，直到对图中的每个节点都这样做。

4.计算最终路径。

狄克斯特拉算法的缺陷：

不能将狄克斯特拉算法用于包含负权边的图。

解决方案：

在包含负权边的图中要找出最短路径，可使用另外一种算法—贝尔曼福德算法。

小结

1.广度优先搜索用于在于非加权图中查找最短路径。

2.狄克斯特拉算法用于在加权图中查找最短路径。

3.仅当权重为正时狄克斯特拉算法才管用。

4.如果图中包含负权边，请使用贝尔曼—福德算法。

第八章 贪婪算法

贪婪算法：

每一步都选择局部最优解，最终得到的就是全局最优解。

NP问题一些解决思路 近似求解：

运用贪婪算法先处理占比最大的，再逐渐处理小的。

NP问题判断的蛛丝马迹：

1.元素较少时算法运行速度非常快，但随着元素数量的增加，速度会变得非常慢。

2.涉及"所有组合"的问题通常都是NP问题。

3.不能将问题分成小问题，必须考虑各种可能的情况。这可能是NP问题。

4.如果问题涉及序列(如旅行商问题中的城市序列)且难以解决，它可能就是NP完全问题。

5.如果问题涉及集合(如广播集合)且难以解决，它可能就是NP完全问题。

6.如果问题可转换为集合覆盖问题或旅行商问题，它就肯定是NP完全问题。

小结：

1.贪婪算法寻找局部最优解，企图以这种方式获得全局最优解。

2.对于NP完全问题，还没有找到快速解决方案。

3.面临NP完全问题时，最佳的做法是使用近似算法。

4.贪婪算法易于实现，运行速度快，是不错的近似算法。

第九章 动态规划

动态规划应用前提:

但仅当每个子问题都是离散的，即不依赖其他子问题时动态规划才管用。

动态规划优点：

1.动态规划可帮助你在给定的约束条件下找到最优解。在背包问题中，你必须在背包容量给定的情况下，偷到价值最高的商品。

2.在问题可分解为彼此独立且离散的子问题时，就可以使用动态规划来解决。

3.每种动态规划解决方案都涉及网格。

4.单元格中的值通常就是你要优化的值。例如：背包问题中，单元格的值为商品的价值。

5.每个单元格都是一个子问题，因此你应该考虑如何将问题分成子问题，这有助于你找出网格的坐标轴。

网格参数：

1.单元格中的值是什么？
2.如何将这个问题划分为子问题？

3.网格的坐标轴是什么？

背包问题关键：

最终答案在最后的单元格中。

最长公共子串问题关键：

最终答案为网格中的最大数字。

动态规划的实际应用：

1.生物学家根据最长公共序列来确定DNA链的相似性，进而判断两种动物或疾病有多相似。最长公共序列还被用来寻找多发性硬化症治疗方案。

2.诸如git diff等命令，它们指出两个文件的差异，也是使用动态规划实现的。（文件差异基于最长公共子序列之解决方案）。

3.编辑距离指出了两个字符串的相似程度，也是用动态规划计算得到的。编辑距离算法的用途很多，从拼写检查到判断用户上传的资料是否为盗版，都在其中。

4.诸如Microsoft Word等具有断字功能的应用程序，他们如何确定在什么地方断字以确保行长一致呢？使用动态规划！

小结

1.需要在给定约束条件下优化某种指标时，动态规划很管用。

2.问题可分解为离散子问题时，可使用动态规划来解决。

3.每种动态规划方案都涉及网格。

4.单元格中的值通常就是你要优化的值。

5.每个单元格都是一个子问题，因此你需要考虑如何将问题分解为子问题。

6.没有放之皆准的计算动态规划的解决方案的公式。

第十章 K最近邻算法

KNN两项基本工作：分类和回归

1.分类就是编组。

2.回归就是预测结果(如一个数字)。

使用KNN时特征挑选：以电影为例

1.与要推荐的电影紧密相关的特征。

2.不偏不倚的特征（例如如果只给喜剧片打分，就无法判断他们是否喜欢动作片）。

OCR：光学字符识别

1.浏览大量的数字图像，将这些数字的特征提取出来。

2.遇到新的图像时，你就提取该图像的特征，再找出它最近的邻居都是谁。

朴素贝叶斯分类器：

能计算出邮件为垃圾邮件的概率，其应用领域与KNN相似。

小结

1.KNN用于分类和回归，需要考虑最近的邻居。

2.分类就是编组。

3.回归就是预测结果(如数字)。

4.特征抽取意味着将物品(如水果或用户)转换为一系列可比较的数字。

5.能否挑选合适的特征事务事关KNN算法的成败。

第十一章 接下来如何做

反向索引：

一个散列表，将单词映射到包含它的页面(常用于创建搜索引擎)。

两个内核算法速度难以成倍提升的原因：

1.并行性管理开销。假设你要对一个包含1000个元素的数组进行排序，如何在两个内核之间分配这项任务呢？如果让每个内核对其中500个元素进行排序，再将两个排好的数组合并成一个有序数组，那么合并也是需要时间的。

2.负载均衡。假设你要完成10个任务，因此你给每个内核都分配5个任务，但分配给内核A的任务都很容易，10s就完成了，而分配给内核B的任务都很难，1分钟才完成。这意味着有那么50s，B都忙死忙活，而A内核却闲的很！你如何均匀的分配工作，让两个内核都一样忙？

解决方案：

并行算法改善性能和可扩展性。

MapReduce的两个基本原理：映射函数和归并函数

映射函数：映射函数接受一个数组，并对其中的每个元素进行同样的处理。

归并函数：将很多项归并为一项。

布隆过滤器：一种概率型数据结构(类似算法 HyperLogLog)

1.可能出现报错情况，即Google可能指出这个"网站已搜集"，但实际上并没有搜集。

2.不可能出现漏报的情况，即如果布隆过滤器说"这个网站未收集"，就肯定未搜集。

HyperLogLog：一种概率型算法

面对海量数据只要求答案八九不离十，可考虑使用概率型算法。

SHA：

被广泛用于计算法密码的散列值。（SHA-0 SHA-1已被发现存在一些缺陷，如果使用请使用SHA-2，SHA-3。当前最安全的散列函数是bcrypt）。

特征：局部不敏感。

。

局部敏感散列函数Simhash现实应用（用于检查两项内容的相似程度）：

1.Google使用Simhash来判断网页是否已搜集。

2.老师可以使用Simhash来判断学生的论文是否是从网上抄来的。

3.Scribd允许用户上传文档或图书，以便与人分享，但不希望用户上传有版权的内容。这个网站可使用Simhash来检查上传的内容是否与小说《XXXX》类似，如果类似，就自动拒绝。

Diffie-Hellman算法使用两个密匙：公匙和私匙解决加密难题：

1.双方无需知道加密算法，他们不必会面协商要加密使用的加密算法。

2.要破解加密算法比登天还难。

待学习：

KNN使用 ：余弦相似度

数据库和高级数据结构 ： B树 堆 伸展树 红黑树：处于平衡状态的特殊查找树

归并

线性规划

这篇好文章是转载于：学新通技术网