基础算法

最近打算学习一些算法，这里先对一些基础算法只是进行重温，对算法的知识点进行一些总结，毕竟有文字输出效果会更好。

概论

选择排序

递归

递归是一种非常优雅的解决问题的方式。它可以把复杂的问题逐步分解成简单的问题，逐步得到结果。
递归就是在函数中，满足递归条件，就调用函数自身，直到满足基线条件，递归返回。
每个递归函数都有两部分：

基线条件：函数不再调用自己，避免形成无限循环。
递归条件：函数调用自己。

栈
栈是计算机中一种非常常见的数据结构，可以进行数据的压入（插入）和弹出（删除并读取）。

调用栈
当函数调用时，计算机首先会为该函数调用分配一块内存，存储函数调用设计的所有变量值。当函数内部调用其他函数时，计算机就会为内部调用函数也分配一块内存，第二块内存位于第一块内存的上面，当函数调用返回，第二块内存就会从栈顶弹出。这就被称为调用栈。

递归调用栈
递归调用栈中包含所有未完成的函数调用。在递归中，在最终返回结果前，每个函数都还未完成，所以栈中会存储每个调用函数的信息，每个函数调用都要占用一定的内存。所以如果栈很高，就会占用非常多的内存资源。解决方法如下：

重新编写代码，使用循环。
使用尾递归，这个貌似比较高级，待深究。

快速排序

这里要用到一种分而治之的思想（divide and conquer, D&C），即递归式问题解决方法。

D&C原理

D&C的工作原理：

找出简单的基线条件；
确定如何缩小问题的规模，使其符合基线条件。

这里有一个好玩的问题：

假设你是一个农场主，有一块168*64的土地。
现在要你均匀分成正方形土地，且分的方块要尽可能大，你会怎样分？

这里涉及到一个欧几里得算法的问题：又称辗转相除法，是指用于计算两个正整数a，b的最大公约数。

我们可以先从这块地中划出两个最大的方块，然后对剩下的一小块地再次划出最大的方块，就这样递归，直到没有剩下地块为止。这样我们就使用的递归的方式来解决问题。

快速排序

工作原理：

从数组中选择一个元素，这个元素成为基准值（pivot）；
找出比基准值小的元素以及比基准值大的元素，这被称为分区。分区后得到一个由所有小于基准值的数组成的子数组，一个由所有大于基准值的数组成的子数组，两个子数组是无序的；
然后对两个子数组进行快速排序。

下面是快速排序的代码：

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)
    
print quicksort([10,5,2,3])

时间复杂度
快速排序的性能高度依赖你选择的基准值。

最糟情况：始终选择第一个值作为基准值，则调用栈的高度为n；
最佳情况：始终将中间值作为基准值，则调用栈的高度为log n。

因为每层栈需要的时间为O(n)，所以时间复杂度方面：

最佳情况：O(n) * O(log n) = O(n log n)
最糟情况：O(n) * O(n) = O(n2)

最佳情况也是平均情况，只要每次都随机选择一个数组元素作为基准值，快速排序的平均运行时间将为O(n log n)。快速排序是最快的排序算法质疑，也是D&C典范。

散列表

散列表我们非常熟悉，在Python中就是字典，在JavaScript中就是对象，等。每一种语言中都有自己对于散列表的实现。这里简单总结一下散列表的实现原理。

散列表平均情况下的时间复杂度是个常量：O(1)

实现原理：
将输入通过散列函数输出一个数组的索引，在数组的该索引位置上存储一个值，这样就可以快速得出我们想要的结果。

避免冲突：
不够理想的散列函数可能会将不同的键映射到数组的同一个位置，这样就需要在这个位置上存储一个链表，就会导致性能下降。

要提升散列表的性能，需要：

较低的装填因子；
良好的散列函数。

装填因子就是 散列表包含的元素数/数组位置总数。所以装填因子越小，冲突的可能性就越小，装填因子过大，我们可以调整数组长度，通常将数组增加一倍。一个不错的经验规则是：一旦装填因子大于0.7，就调整散列表的长度。

良好的散列函数可以让数组中的值呈均匀分布。

广度优先搜索（宽度优先搜索）

什么是图？
图由节点和边组成，一个节点可能和众多节点相连接，这些节点称为邻居。

广度优先搜索是一种用于图的查找算法，帮助回答两个问题：

从节点A出发，有前往节点B的路径吗？
从节点A出发，前往节点B的哪条路径最短？

广度优先搜索的基本思路就是现在一级节点中搜索，如果找到目标，则完成，如果没有找到目标，继续在二级节点中搜索，依次是三级、四级…直到返回搜索结果。

在检查的过程中要按照添加顺序进行，所以我们要用到队列。队列是一种先进先出（FIFO）的数据结构，而栈是一种后进先出（LIFO）的数据结构。

关于图的代码实现，我们可以使用散列表来实现，例如下图：

我们可以用如下代码实现：

graph = {} 
graph["you"] = ["alice", "bob", "claire"] 
graph["bob"] = ["anuj", "peggy"]
graph["alice"] = ["peggy"]
graph["claire"] = ["thom", "jonny"] 
graph["anuj"] = [] 
graph["peggy"] = [] 
graph["thom"] = [] 
graph["jonny"] = []

算法实现原理：

算法代码实现：

from collections import deque

def search(name):
    search_queue = deque()
    search_queue += graph[name]
    searched = [] //用于记录检查过的人
    
    while search_queue:
        person = search_queue.popleft()
        if person not in searched:
            if person_is_seller(person):
                print person + 'is seller'
                return True
            else: 
                search_queue += graph[person]
        searched.append(person)
        
    return False

def person_is_seller(name):
    //随意定义一个判断函数
    return name[-1] == 'm'
    
search('you')

小结

面对寻找最短路径的问题，可以先用图来建立模型，再使用广度优先搜索来解决问题。
有向图中的边有箭头，箭头的方向指定了关系的方向。
无向图中的边没有箭头，其中的关系是双向的。
你需要按照加入顺序进行检查，否则找到的可能就不是最短路径，因此搜索列表必须是队列。
对于检查过的人务必不要再去检查，否则可能导致无限循环，例如一个无向图。

狄克斯特拉算法（Dijkstra）

前一章中使用广度优先搜索来查找两点之间的最短路径，那是的最短路径的意思是段数最少。在狄克斯特拉算法中，给每段都分配了数字或权重，因此狄克斯特拉算法找出的是总权重最小的路径。

狄克斯特拉算法只适用于有向无环图。
狄克斯特拉算法不能用于包括负权边的图。

实现
我们以下图中的例子来进行实现：

首先，我们需要定义三个散列表来记录图的相关信息。
graph:

// graph用来记录图的信息，包括节点的邻居和前往邻居的开销
graph = {}

graph['start'] = {}
graph['start']['a'] = 6
graph['start']['b'] = 2

graph['a'] = {}
graph['a']['fin'] = 1

graph['b'] = {}
graph['b']['a'] = 3
graph['b']['fin'] = 5

graph['fin'] = {}

costs：

//costs用于存储每个节点的开销
infinity = float('inf')
costs = {}
costs['a'] = 6
costs['b'] = 2
costs['fin'] = infinity

parents:

// parents用于存储父节点
parents = {}
parents['a'] = 'start'
parents['b'] = 'start'
parents['fin'] = None

还需要一个数组用于存储已处理过的节点

1	processed = []

完成了各种数据结构的创建，接下来我们开始算法。

代码实现

// 未处理的节点中找到开销最小的节点
node = find_lowest_cost_node(costs)

while node is not None:
    cost = costs[node]
    neighbors = graph[node]
    for n in neighbors.keys():
        new_cost = cost + neighbors[n]
        if costs[n] > new_cost:
            costs[n] = new_cost
            parents[n] = node
        
    processed.append(node)


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

以上就是代码实现的全部内容。

小结

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

贪婪算法

贪婪算法是指，在对问题求解时，总是做出在当前看来是最好的选择。就是说，你每步都选择局部最优解，不从整体最优上加以考虑。贪婪算法不能得出最优解，但非常接近最优解。

集合覆盖问题
举个例子：
你要办一个广播节目，让全美50个州都能收听得到。为此，你需要决定在哪些广播台播出。每个广播台都需要支付费用，因此你力图在尽可能少的广播台播出。

算法：

选出这样一个广播台，即它覆盖了最多的未覆盖州。即使已覆盖一些州，也没关系；
重复上一步，知道覆盖了所有州。

这就是一种近似算法，因为获得精确解需要的时间太长。判断近似算法优劣的标准如下：

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

代码实现
出于简化考虑，智力要覆盖州、广播台没有那么多。

构建原始数据结构

// 创建一个集合，包含要覆盖的州
states_needed = set(['mt', 'wa', 'or', 'id', 'nv']) 

// 键为广播站名，值为广播站覆盖的州
stations = {}
stations['kone'] = set(['id', 'nv'])
stations['ktwo'] = set(['wa', 'id', 'mt'])
stations['kthree'] = set(['or', 'nv'])
stations['kfour'] = set(['nv'])

// 存储最终选择的广播台
final_stations = set()

逻辑代码

while states_needed: // 只要需要覆盖的州不为空，一直循环

   // 每一次循环都是通过遍历所有广播台，找出覆盖剩余需要覆盖州最多的电台
    best_station = None // 覆盖州最多的广播台
    states_covered = set()  // 覆盖州的集合
    
    for station, states in stations.items():    // 遍历所有广播台
        covered = states_needed & states    //  当前广播台覆盖州和需要覆盖州的交集
        if len(covered) > len(states_covered): // 判断当前广播台覆盖的州是否是最多的
            states_covered = covered    
            best_station = station
    
    states_needed -= states_covered // 需要覆盖州与当前广播台所覆盖的州取差集
    final_stations.add(best_station)    // 添加当前广播台

NP完全问题
NP完全问题定义为，以难解著称的问题，根本不可能编写出可快速解决这些问题的算法。

例如，要找出A、B两点之间的最短路径是很容易得出，但如果要找出指定几个点的最短路径，就是商旅问题，这就是一个NP完全问题。
一般判断一个问题是否为NP问题依据：

元素较少时算法运算速度非常快，但随着元素数量的增加，速度会变得非常慢；
涉及“所有组合”的问题通常是NP完全问题；
不能将问题分成小问题，必须考虑各种可能的情况；
问题涉及序列且难以解决，如商旅问题；
问题涉及集合且难以解决，如广播台集合。

动态规划

K最近邻算法

K-nearest neighbor，简称KNN算法。堪称你进入机器学习领域的领路人。

K最近邻算法可以用于创建分类系统，通过特征值的计算，找出最接近的邻居数据，就可归为相同类别。

通过这样的算法，可以构建一个推荐系统。

挑选正确的特征值对于算法的准确性非常重要。

朴素贝叶斯分类器应用领域与KNN算法相似，通过计算概率来做预测。

小结

KNN算法用于分类和回归，需要考虑最近的邻居；
分类就是编组；回归就是预测结果；
特征抽取意味着将物品转化为一系列可比较的数字；
能否挑选合适的特征事关KNN算法的成败。

概论