图解算法

评论:本书图文并茂,适合温故知新。

第1章:算法简介

二分查找

第3章:递归

确定基线条件和递归条件

第4章:快速排序:

欧几里得算法:欧几里德算法的思想基于辗转相除法的原理,辗转相除法是欧几里德算法的核心思想,欧几里德算法说白了其实就是辗转相除法的计算机算法的实现而已。下面我们先说说辗转相除法,辗转相除法的内容:如果用gcd(a,b)来表示a和b的最大公约数,那么根据辗转相除法的原理,有gcd(a,b)=gcd(b,a mod (b)),其中mod()表示模运算,并且不妨让a>b,这样方便于模运算。

证明:设a=kb+r,则r=a mod (b),r=a-kb。假设c=gcd(a,b),即b/c和a/c都为整数,则(a-kb)/c也为整数,即gcd(a,b)=gcd(b,a mod (b))。

快速排序:
1.选择基准值
2.将数组分为大于基准值的元素和小于基准值的元素
3.对这两个子数组进行快速排序
这里用到了归纳证明
最糟情况O(n^2)
平均时间O(n*logn)

python代码:
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[1:] if i > pivot]
        return quicksort(less) + [pivot] + quicksort(greater)

第5章:散列表

适用场景:仿真映射关系、防止重复、缓存/记住数据,以免服务器再通过处理来生成它们。

第6章:广度优先搜索

广度优先搜索适合于:从A到B有没有路?从A到B哪条路最短?
用图和散列表实现广度优先:

graph = {
    "you":["alice","bob","claire"],
    "bob":["anuj","peggy"],
    "alice":["peggy"],
    "claire":["thom","jonny"],
    "anuj":[],
    "peggy":[],
    "thom":[],
    "jonny":[]
}
def bfs():
    search_deque = deque()
    search_deque += graph["you"]
    searchd = []
    while search_deque:
        person = search_deque.popleft()
        if person not in searchd:
            if is_seller(person):
                print person + " is a seller"
                return True
            else:
                search_deque += graph[person]
                searchd.append(person)
    return False

队列FIFO,栈LIFO。

第7章:狄克斯特拉算法(Dijkstra’s algorithm)

算法思想:找出图中最便宜的节点,并确保没有到该节点的更便宜的路径。
假设:对于处理过的节点,没有前往该节点的更短路径。
不适用于有负权边的图,负权边需要用Bellman-Ford algorithm。

#graph
graph_dijkstra = {
    "start":{"a":6,"b":2},
    "a":{"fin":1},
    "b":{"a":3,"fin":5},
    "fin":{}
}
infinity = float("inf")
#graph_dijkstra["start"] = {}
#cost table
costs = {
    "a":6,
    "b":2,
    "fin":infinity
}
#parents table
parents = {
    "a":"start",
    "b":"start",
    "fin":None
}
#node already visited
processed = []

def dijkstra():
    node = find_lowest_cost_node(costs)#在未处理的节点中找出开销最小的节点
    while node is not None:
        cost = costs[node]
        neighbors = graph_dijkstra[node]
        for neighbor in neighbors.keys():
            new_cost = cost + neighbors[neighbor]
            if costs[neighbor] > new_cost:
                costs[neighbor] = new_cost
                parents[neighbor] = node
        processed.append(node)
        node = find_lowest_cost_node(costs)


def find_lowest_cost_node(costs):
    lowest_cost = float("inf")
    lowest_cost_node = None
    for node in costs:
        cost = costs[node]
        if cost < lowest_cost and node not in processed:
            lowest_cost = cost
            lowest_cost_node = node
    return lowest_cost_node

第8章:贪婪算法

NP完全问题:没有快速算法的问题
P类问题:所有可以在多项式时间内求解的判定问题构成P类问题。判定问题:判断是否有一种能够解决某一类问题的能行算法的研究课题。
NP类问题:所有的非确定性多项式时间可解的判定问题构成NP类问题。非确定性算法:非确定性算法将问题分解成猜测和验证两个阶段。算法的猜测阶段是非确定性的,算法的验证阶段是确定性的,它验证猜测阶段给出解的正确性。设算法A是解一个判定问题Q的非确定性算法,如果A的验证阶段能在多项式时间内完成,则称A是一个多项式时间非确定性算法。有些计算问题是确定性的,例如加减乘除,只要按照公式推导,按部就班一步步来,就可以得到结果。但是,有些问题是无法按部就班直接地计算出来。比如,找大质数的问题。有没有一个公式能推出下一个质数是多少呢?这种问题的答案,是无法直接计算得到的,只能通过间接的“猜算”来得到结果。这也就是非确定性问题。而这些问题的通常有个算法,它不能直接告诉你答案是什么,但可以告诉你,某个可能的结果是正确的答案还是错误的。这个可以告诉你“猜算”的答案正确与否的算法,假如可以在多项式(polynomial)时间内算出来,就叫做多项式非确定性问题。
贪婪算法:每一步都采取最优
如何识别NP完全问题:
元素较少时运行快,元素增加后变的非常慢;设计“所有组合”的问题;问题涉及序列/集合且难以解决;
如果问题可以转换为集合覆盖问题或者旅行商问题,则肯定是NP完全问题。
面临NP完全问题时,最佳的做法是近似算法。

第9章:动态规划

给定约束条件下找到最优解。在问题可以分解为彼此独立且离散的子问题时,就可使用动态规划来解决。
每种动态规划解决方案都涉及方格。
单元格中的值就是你要优化的值。
每个单元格就是一个子问题,因此你需要考虑如何将问题分解为子问题。
最长公共序列。
编辑距离:两个字符串的相似程度。
摘抄:http://blog.csdn.net/baidu_28312631/article/details/47418773

递归到动规的一般转化方法

递归函数有n个参数,就定义一个n维的数组,数组的下标是递归函数参数的取值范围,数组元素的值是递归函数的返回值,这样就可以从边界值开始, 逐步填充数组,相当于计算递归函数值的逆过程。

动规解题的一般思路

1. 将原问题分解为子问题

把原问题分解为若干个子问题,子问题和原问题形式相同或类似,只不过规模变小了。子问题都解决,原问题即解决(数字三角形例)。
子问题的解一旦求出就会被保存,所以每个子问题只需求 解一次。
2.确定状态

在用动态规划解题时,我们往往将和子问题相关的各个变量的一组取值,称之为一个“状 态”。一个“状态”对应于一个或多个子问题, 所谓某个“状态”下的“值”,就是这个“状 态”所对应的子问题的解。
所有“状态”的集合,构成问题的“状态空间”。“状态空间”的大小,与用动态规划解决问题的时间复杂度直接相关。 在数字三角形的例子里,一共有N×(N+1)/2个数字,所以这个问题的状态空间里一共就有N×(N+1)/2个状态。

整个问题的时间复杂度是状态数目乘以计算每个状态所需时间。在数字三角形里每个“状态”只需要经过一次,且在每个状态上作计算所花的时间都是和N无关的常数。

3.确定一些初始状态(边界状态)的值

以“数字三角形”为例,初始状态就是底边数字,值就是底边数字值。

4. 确定状态转移方程

定义出什么是“状态”,以及在该“状态”下的“值”后,就要找出不同的状态之间如何迁移――即如何从一个或多个“值”已知的 “状态”,求出另一个“状态”的“值”(递推型)。状态的迁移可以用递推公式表示,此递推公式也可被称作“状态转移方程”。

数字三角形的状态转移方程:
20150811160833998

能用动规解决的问题的特点
  1. 问题具有最优子结构性质。如果问题的最优解所包含的 子问题的解也是最优的,我们就称该问题具有最优子结 构性质。
  2. 无后效性。当前的若干个状态值一旦确定,则此后过程的演变就只和这若干个状态的值有关,和之前是采取哪种手段或经过哪条路径演变到当前的这若干个状态,没有关系。

第10章:k最近邻算法

KNN:分类和回归。
分类就是编组,回归就是预测结果。
朴素贝叶斯

第11章:接下来如何做

反向索引

用于创建搜索发动机

傅里叶变换

并行算法

并行性管理开销和负载均衡

MapReduce

映射:将一个数组转换为另一个数组

归并:将很多项归并为一项

布隆过滤器和HyperLogLog

面对海量数据且只要求答案八九不离十,可考虑以下概率形算法:

布隆过滤器:

如果想判断一个元素是不是在一个集合里,一般想到的是将集合中所有元素保存起来,然后通过比较确定。链表、树、散列表(又叫哈希表,Hash table)等等数据结构都是这种思路。但是随着集合中元素的增加,我们需要的存储空间越来越大。同时检索速度也越来越慢。

Bloom Filter 是一种空间效率很高的随机数据结构,Bloom filter 可以看做是对 bit-map 的扩展, 它的原理是:

当一个元素被加入集合时,通过 K 个 Hash 函数将这个元素映射成一个位阵列(Bit array)中的 K 个点,把它们置为 1。检索时,我们只要看看这些点是不是都是 1 就(大约)知道集合中有没有它了:

如果这些点有任何一个 0,则被检索元素一定不在;
如果都是 1,则被检索元素很可能在。

HyperLogLog:

计算基数。什么是基数?比如数据集 {1, 3, 5, 7, 5, 7, 8}, 那么这个数据集的基数集为 {1, 3, 5 ,7, 8}, 基数(不重复元素)为5。 基数估计就是在误差可接受的范围内,快速计算基数。

todo

SHA算法

SHA是一个散列函数。

用于创建散列表的散列函数根据字符串生成数组索引,而SHA根据字符串生成另一个字符串。

局部敏感的散列算法

Simhash,细微修改之后其hash值只有细微差别。

todo

Diffie-Hellman密钥交换

替代者RSA。公钥私钥。

总结一下结论:
1,用公钥加密数据,用私钥来解密数据
2,用私钥加密数据(数字签名),用公钥来验证数字签名。

线性规划

用于在给定约束条件下最大限度地改善指定的指标。

Simplex算法。

todo

comments powered by Disqus