读书笔记：图解算法
算法简介
二分查找 O(log n)
大O表示法
大O表示法 让你能够比较操作数，它指出了算法运行时间的增速
大O表示法 指出了最糟糕情况下的运行时间
下面按从快到慢的顺序列出了你经常会遇到的5种大O运行时间。
O(log n)，也叫对数时间，这样的算法包括二分查找。
O(n)，也叫线性时间，这样的算法包括简单查找。
O(n * log n)，这样的算法包括第4章将介绍的快速排序——一种速度较>快的排序算法。
O(n 2 )，这样的算法包括第2章将介绍的选择排序——一种速度较慢的排序算法。
O(n!)，这样的算法包括接下来将介绍的旅行商问题的解决方案——一种非常慢的算法
算法的速度指的并非时间，而是操作数的增速。
选择排序 O( n^2 )
先找最大，再找第二大...
数组和链表
数组： 内存中连续
链表： 随机
快速排序
O(n log n)
递归
两部分：基线条件（不在调用自己）、递归条件（调用自己）
栈
快速排序
分而治之（divide and conquer，D&C）
这里重申一下D&C的工作原理：
(1) 找出简单的基线条件；
(2) 确定如何缩小问题的规模，使其符合基线条件。
[图片上传失败...(image-7e1b17-1515037467104)]
[图片上传失败...(image-46af14-1515037467104)]
散列表
散列函数
冲突
较低的填装因子；散列包含的元素数/位置总数
良好的散列函数。
广度优先搜索
breadth-first search，BFS 广度优先搜索：一种图算法
图由节点（node）和边（edge）组成。
第一类问题：从节点A出发，有前往节点B的路径吗？
第二类问题：从节点A出发，前往节点B的哪条路径最短？
队列
队列是一种先进先出（First In First Out，FIFO）的数据结构，而栈是一种后进先出（Last In
First Out，LIFO）的数据结构。
有向图（directed graph），其中的关系是单向的。
无向图（undirected graph）没有箭头，直接相连的节点互为邻居
如果任务A依赖于任务B，在列表中任务A就必须在任务B后面。这被称为拓扑排序，使用它可根据图创建一个有序列表。
树是一种特殊的图，其中没有往后指的边。
狄克斯特拉算法
狄克斯特拉算法包含4个步骤。
(1) 找出“最便宜”的节点，即可在最短时间内到达的节点。
(2) 更新该节点的邻居的开销，其含义将稍后介绍。
(3) 重复这个过程，直到对图中的每个节点都这样做了。
(4) 计算最终路径。
边 有权
带权重的图称为加权图（weighted graph），不带权重的图称为非加权图（unweighted graph）
狄克斯特拉算法只适用于有向无环图（directed acyclic graph，DAG）。
不能将狄克斯特拉算法用于包含负权边的图
在包含负权边的图中，要找出最短路径，可使用另一种算法——贝尔曼福德算法（Bellman-Ford algorithm）
贪婪算法
旅行商问题和集合覆盖问题有一些共同之处：你需要计算所有的解，并从中选出最小/最短
的那个。这两个问题都属于NP完全问题。
NP完全问题特点
元素较少时算法的运行速度非常快，但随着元素数量的增加，速度会变得非常慢。
涉及“所有组合”的问题通常是NP完全问题。
不能将问题分成小问题，必须考虑各种可能的情况。这可能是NP完全问题。
如果问题涉及序列（如旅行商问题中的城市序列）且难以解决，它可能就是NP完全问题。
如果问题涉及集合（如广播台集合）且难以解决，它可能就是NP完全问题。
如果问题可转换为集合覆盖问题或旅行商问题，那它肯定是NP完全问题。
动态规划
但仅当每个子问题都是离散的，即不依赖于其他子问题时，动态规划才管用
最长公共子序列：两个单词中都有的序列包含的字母数
K最近邻算法
使用KNN来做两项基本工作——分类和回归：
分类就是编组；
回归就是预测结果（如一个数字）
总结
KNN用于分类和回归，需要考虑最近的邻居。
分类就是编组。
回归就是预测结果（如数字）。
特征抽取意味着将物品（如水果或用户）转换为一系列可比较的数字。
能否挑选合适的特征事关KNN算法的成败
MapReduce
映射（ map ）函数和归并（ reduce ）函数
布隆过滤器：
可能出现错报的情况，即Google可能指出“这个网站已搜集”，但实际上并没有搜集。
不可能出现漏报的情况，即如果布隆过滤器说“这个网站未搜集”，就肯定未搜集。
局部不敏感 SHA 局部改变整体改变（不会区分是否是局部的变化）
局部敏感 Simhash 局部改变整体细微变化（会区分是否是局部的变化）
Diffie-Hellman算法及其替代者RSA
网友评论