遇见1995

《算法图解》

算法

这是对《算法图解》这本书的阅读总结。

第 01 章——算法简介

二分查找(有序序列)

大O表示法:表示最坏条件下,操作数的增速

常见大O运行时间(快到慢)

时间 说明
O(logn) 对数时间,二分查找
O(n) 线性时间,简单查找
O(n*logn) 快速排序
O(n^2) 选择排序
O(n!) 旅行商问题

实例

旅行商问题:前往n个地点,总旅程的最短路线。

第 02 章——选择排序

  • 数组:内存连续,查询快,增删元素慢
  • 链表:内存不连续,查询慢,增删元素快
  • 链表数组:查询,增删元素介于数组和链表
  • 选择排序:(1/2)n^2 #大O表示法忽略常数

实例

Facebook创建用户时,用链表数组:26个数组元素里面存放链表

第 03 章——递归

  • 递归:调用自己
  • 基准条件(base)
  • 递归条件(recursive)
  • 调用栈(call stack):先进后出,只有压入和弹出操作,内存占用可能很大

调用另外一个函数时,当前函数暂停,处于未完成状态

递归也调用了栈,当不为基准条件时,压入,为基准条件时,弹出

第 04 章——快速排序

  • 分而治之(divide and conquer,D&C)
  1. 找出基准条件,尽量简单
  2. 不断分解问题(或缩小规模),直到符合基准条件

欧几里得算法

函数式编程

快速排序

  1. 选择一个元素,作为基准值(pivot)
  2. 按<、>基准值,进行分区(partitioning)
  3. 对<、>基准值得子数组,进行快速排序,最后合并。
  • 最糟糕情况:O(n^2)
  • 平均情况(最佳情况):O(n log n)
1
2
3
4
5
6
7
8
9
10
def quicksort ( 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[i: ] if i > pivot ]
return quicksort( less ) + [pivot] +quicksort( greater )

归纳证明

合并排序(merge sort)

最糟糕情况:O(n log n)
最佳情况(平均情况)

大O时间表示法:O(n) = C * n

常量C:算法所需的固定时间

第 05 章——散列表

散列函数:将输入映射为数字(作为数组的索引)

  1. 将同样的输入映射到相同的索引
  2. 尽量将不同的输入映射到不同的索引
  3. 如果映射到同一个索引上,就在这个位置创建一个存储链表
  4. 不超过数组长度,只返回有效的索引

散列表(hashmap):也叫,字典,映射,关联数组,通过散列函数,把value值存放到对应数组索引

  • 平均情况下:O( 1)

  • 最糟糕情况下:O( n )

  • 较低的装填因子:包含的元素/总位置数(通常为3/4),大于就调整长度为原来的1倍

  • 良好的散列函数:SHA函数

作用

  • 用于查找、删除、插入:DNS解析、DNS resolution(网站映射到ip地址)
  • 防止重复:投票
  • 用于缓存:保存用户数据,下次直接返回数据

第 06 章——广度优先搜索

  • 图:由节点(node)和边(edge)组成。
  • 邻居:相连的俩个节点、
  • 有向图(directed graph):有方向
  • 无向图(undirected graph):无方向

广度优先搜索(breadth-first search,BFS)

用图来建立问题模型
使用广度优先搜索(先一度关系,再二度关系)
使用队列添加顺序检查(检查过的人不必再检查
运行时间:O( V + E ) , V是顶点数(vertice),E为边数

  • 队列(queue):先进先出(First in First out,FIFO)
  • 拓扑排序:A依赖与B,A必须在B任务后面。

作用:解决最短路径问题:shortest-path problem

  1. 从A出发,是否有路径到B
  2. 从A出发,到B那条路径最短

第 07 章——狄克斯特拉算法

  • 加权图(weighted graph):每条边都有固定关联数字(权重),有权重的图。
  • 非加权图(unweighted graph):没有权重的图
  • 负权边:权重为负

狄克斯特拉算法(Dijkstra‘s algorithm):找出最快的路径

  1. 找出最便宜的节点
  2. 更新该节点邻居的开销(权重)
  3. 重复这个步骤,直到所有节点都做了
  4. 计算最终路径

只适合有向无环图(directed acyclic graph,DAG)
有负权边则不可使用(可使用,贝尔曼-福德算法)

第 08 章——贪婪算法

  • 贪婪算法:每步都选择局部最优解。
  • 只能接近最优解,有时候并不是最优解

集合覆盖问题

  • 幂集(power set):每个可能的子集。2^n个
  • 并集:集合合并
  • 交集:都有的元素集合
  • 差集:除去另外一个集合有的元素

近似算法(approximation algrithm):解决NP完全问题

  • 速度有多快
  • 得到近似解与最优解的接近程度

NP完全问题:为了解决集合覆盖问题,必须计算每个可能的集合 O( n! )

  • 必须考虑各种情况
  • 阶乘函数(factorial function)

第 09 章——动态规划

  • 动态规划:将问题分成小问题,并先着手解决这些小问题。

  • 最长子公共字串

  • 最长公共子序列

第 10 章——K最近邻算法

K最近邻算法(K-nearest neighbours,KNN):通过最接近的对象,判断本物体是什么?(或者喜欢什么)

  • 毕达哥拉斯公式:(计算俩点距离)a^2+b^2=c^2
  • 特征抽取:选出紧密相关,不偏不倚的特征,进行对比判断。(转换为数字)
  • 余弦相识度(cosine similarity)
  • 分类:是编组
  • 回归(regression):预测结果

应用

  • 分类系统

  • 推荐系统

  • 机器学习:

    • OCR,光学字符识别(optical character recognition):拍摄印刷页面的照片,识别出其中的文字。
    • 训练(training):浏览大量的数字图像,提取数字特征(曲线,点,线段)
    • 遇到新图像时,提取该特征,找出最近的邻居是谁
  • 垃圾邮件过滤器:

朴素贝叶斯分类器(Naive Bayes classifier):对特定数据进行训练,然后判断是垃圾邮件的概率。

第 11 章——接下来如何做

二叉查找树(binary search tree):
每个节点:左子节点比它小,右子节点比它大。

  • 先检查根节点。

优点:

  • 效率,跟二分查找一致。
  • 删除和插入的效率要快。

缺点:

  • 不能随机访问
  • 红黑树:处于平衡状态的特殊二叉查找树
  • B树:一种特殊的二叉树,数据库用它于存储数据
  • 堆:
  • 伸展树:

搜索引擎的原理

  • 反向索引:创建一个散列表,将键为单词,值为包含指定单词的页面,一个散列表,将单词映射到包含它的页面。

  • 傅里叶变换:强化你关心的部分,用于处理信号。

  • 并行算法:多个内核中并行的处理。

并行性管理开销
负载均衡
分布式算法:一种特殊的并行算法,MapReduce。用于短时间内完成,海量工作。

  • 映射(map)函数:接受一个数组,对每个元素执行同样的处理。
  • 归并(reduce)函数:将很多项归并为一项。一个数组转换为一个元素。
  • 布隆过滤器:一种概率型数据结构,提供的答案可能对,也可能不对。很可能正确。占用存储空间很少。

HyperLogLog:一种类似布隆过滤器算法,答案比较接近准确,占用内存少。

SHA算法(安全散列算法):给定一个字符串,返回其散列值。局部不敏感。

  • 可以用于判断俩个文件是否相同。
  • 检查密码,存储哈希值。
  • 局部不敏感。simhash。
  • Diffie-Hellman密钥交换。

公钥:用于加密消息
私钥:用于解密消息
RSA算法

线性规划:最优化,在给定约束条件下最大限度地改善指定的指标。

Simplex算法。


专题:

本文发表于 2018-08-25,最后修改于 2020-03-14。

本站永久域名yujian95.cn,也可搜索「 遇见1995 」找到我。

期待关注我的微信公众号「 编程图解 」 ,查看最近的文章和动态。


下一篇 » 微信开发者工具代码管理

赞赏支持

请我吃包子 =^_^=

i ali

支付宝

i wechat

微信

推荐阅读

Big Image