算法图解
1.算法基础
算法是⼀组完成任务的指令，任何代码⽚段都可以视为算法。
⼆分查
⼆分查是⼀种算法，其输⼊是⼀个有序的元素列表。如果要查的元素到，返回其位置，否则返回None.
如果是顺序查，取决于有序列表中的元素数量n；如果是⼆分查，则取决于有序列表数量n的公式 $log2^n$.
⼆分查的python代码类似下⾯：
def binary_search(list, item):
low = 0
high = len(list)
while low <= high:
mid = (low + high) / 2
guess = list[mid]
if guess == item :
return mid
if guess > item :
high = mid - 1
else :
low = mid + 1
return None
⼤O表⽰法
⼤O表⽰法是⼀种特殊的表⽰法，指出了算法的运⾏速度有多快，它并⾮以时间(例如秒、毫秒)为单位的速度，⽽是让你能够⽐较操作数，它指出了算法运⾏时间的增速。快速排序python实现
使⽤⼤O表⽰法，会指出最糟糕情况下的运⾏时间，下⾯是⼀些蟾宫的⼤O时间：
⼤O时间解释举例
$O(log2^n)$对数时间⼆分查
$O(n)$线性时间简单查
$O(nlog2^n)$快速排序
$O(n^2)$选择排序
$O(n!)$旅⾏商问题，⾮常慢的算法
将其进⾏从快到慢的依次排序：
通过⼤O表⽰法和上⾯的图，我们可以得到以下结论：
算法的速度指的并⾮时间，⽽是操作数的增速。
谈论算法的速度时，我们说的是随着输⼊的增加，其运⾏时间将以什么样的速度增加。
算法的运⾏时间⽤⼤O表⽰法表⽰。
$O(log2^n)$⽐$O(n)$快，当需要搜索的元素越多时，前者⽐后者快得越多。
2.选择排序
内存的⼯作原理
当你需要将数据存储到内存中时，请求计算机提供存储空间，计算机会给你⼀个存储地址。需要存储多项数据时，有两种基本⽅式——数据和链表。但它们不都适⽤于所有的情形，因此知道他们之间的差别很重要。
内存与硬盘的⼯作原理是有着巨⼤差别的，因此其排序⽅式也会有所不同，如果排序的⽂件处于磁盘上，且并不能⼀次性加载到内存中（往往内存较⼩），则需要考虑使⽤外排序。
数组和链表
对于数组和链表这两种⾮常简单的数据结构，可参考 Java数据结构与算法⼀篇⽂章。
⼆者常⽤的操作事件可以参考下⾯的表格：
3.递归
递归描述的问题，通常是⼀类组合性质的问题，⽐如下⾯这种盒⼦套盒⼦，⼦盒⼦其中还可能发⽣嵌套的问题。
虽然这类问题可以⽤⾮递归的⽅式来实现（while或者⽆限的for循环），但更加清晰、易理解的⽅式其实是使⽤递归 —— ⽆限调⽤⾃⼰。StackOverflow上有⼀句话：
如果使⽤循环，程序的性能可能会更⾼；如果使⽤递归，程序可能更容易理解。如何选择要看什么对你更加重要”。
递归的要素：基线条件和递归条件
在递归中，为了避免调⽤⾃⼰时会发⽣⽆限死循环，程序必须要知道什么时候该停⽌，因此每个递归程序都包含两部分：
基线条件(base case)：函数不再调⽤⾃⼰，从⽽避免形成⽆限循环；
递归条件(recursive case): 函数调⽤⾃⼰；
数据结构：栈
栈是⼀种简单的数据结构，存在着限定的访问数据⽅式：LIFO（Last In First Out）。
计算机在内部使⽤被称为调⽤栈的栈，在进⾏⽅法调⽤时，计算机会将函数调⽤所涉及到的所有变量的值存储到内存中（当然也会涉及到内存分配），在调⽤另⼀个函数时，当前函数暂停并处于未完成状态，所有变量值都还在内存中，直到另⼀个函数执⾏完成再回到上层的函数。
栈在递归调⽤中扮演着重要的⾓⾊，就像是⽅法调⽤⼀样。
使⽤栈虽然简单，但是也要付出代价：存储详尽的信息可能占⽤⼤量的内存，每个函数调⽤都要占⽤⼀定的内存，如果栈很⾼，就意味着计算机存储了⼤量函数调⽤的信息（StackOverflowError风险），有两种选择⽅案可以解决这个问题：
重新编写代码，转⽽使⽤循环，尽管这可能造成⼀定的复杂性；
使⽤尾递归（但不是所有的编程语⾔都⽀持尾递归）；
4.快速排序：分治
分⽽治之 - Divide & Conquer，是⼀种著名的递归式解决问题的⽅法，引⼊快速排序的⽬的，就是说明⼀下如何对问题进⾏分治处理，在这⾥分治是策略，递归是⼿段。
D&C的⼯作原理：
出简单的基线条件；
确定如何缩⼩问题的规模，使其符合基线条件；
D&C并⾮可⽤于解决问题的算法，⽽是⼀种解决问题的思路，举个例⼦，为了要计算 SUM(2,4,6) 的结果，可以使⽤递归的⽅式将问题进⾏分解，并确定基线条件:
注意：编写涉及数组的递归函数时，基线条件通常是数组为空或只包含⼀个元素，陷⼊困境时，请检查基线条件是不是这样。
快速排序
快速排序是⼀种常见的排序算法，要⽐前⾯介绍的选择排序快得多，C语⾔中的排序函数qsort()使⽤的就是快速排序。
其基本算法结构为：
选择基准值；
将数组分成两个⼦数组：⼩于基准值的元素和⼤于基准值的元素；
对这两个⼦数组进⾏快速排序；
快速排序算法实现的正确性取决于归纳证明原理，这是⼀种证明算法⾏之有效的⽅式，分为两步：基线条件和归纳条件。
假如，我要证明我能够爬到梯⼦的最上⾯：
基线条件中，我已经站在了第⼀个横档上；
归纳条件中，如果我站在⼀个横档上，就能将脚放在第⼆个横档上；
下⾯就是快速排序的算法实现：
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(...)
既然快速排序在最糟糕的情况下，算法复杂度退化到$O(N^2)$, 为什么不采⽤时间复杂度同样为$O(Nlog2^N)$的归并排序（merge sort）呢？
原因就在于算法复杂度的常量表⽰会有所不同，快速排序的常量要⽐归并排序的常量⼩得多，⽽且如果它们的运⾏速度都是
$O(Nlog2^N)$，那么快速查就会⽐归并排序快得多。
5.散列表
散列表是最有⽤的数据结构之⼀，⽤途⾮常⼴泛。
散列函数
散列函数是这样的函数，⽆论你给他什么样的数据，都会直接返回给你⼀个数字，必须满⾜下⾯的要求：
必须是⼀致的：每次计算返回的结果都⼀样；
应该将不同的输⼊映射到不同的数字上，这是最理想的情况；
散列表适合的场景：
模拟映射关系；
防⽌重复；
缓存/记住数据，以免服务器再通过处理来⽣成它们；
冲突和性能
散列表存放的数据量是有限的，尤其是当数据量⽐较⼤的情况，会发现散列后对应的数据块已经被占⽤，这就称为冲突:
散列函数很重要，理想情况下将键均匀地映射到散列表的不同位置；
如果链表存储很长，速度/性能将会下降地⾮常明显；
平均情况下，散列表执⾏各种操作的时间均为$O(1)$；但在最糟糕的情况下，散列表的所有操作运⾏时间为$O(N)$，在使⽤散列表时，避开最糟情况⾄关重要，要避免冲突需要：
较低的装填因⼦，装填因⼦ = 散列表中包含的元素数/位置总数
良好的散列函数，可以参考 SHA函数
6.⼴度优先搜索
如下图，为出换乘最少的路径，你该使⽤什么算法？
这种类型问题被称为最短路径问题（shortest-path problem），解决最短路径问题的算法被称为⼴度优先算法，⼀般此类问题需要两个步骤：
使⽤图来建⽴问题模型；
使⽤⼴度优先搜索来解决问题；
图
图模拟⼀组连接，由节点和边组成，⼀个节点可能会与众多节点直接相连，这些节点被称为邻居，所以图⼀般是⽤来模拟不同的东西是如何相连的。
⼴度优先搜索
⼴度优先搜索是⼀种⽤于图的查，⽅便解决下⾯的两类问题：
从节点A出发，有到节点B的路径吗？
从节点A出发到节点B的最短路径是什么？
队列：与现实⽣活中的队列原理类似，与栈⽐较相近，你不能随机地访问队列中的元素，它只⽀持两种操作：⼊队和出队；
队列是⼀种先进先出（FIFO）的数据结构，⽽栈是⼀种后进先出（LIFO）的数据结构。
假设你经营着⼀个芒果农场，需要寻芒果销售商，以便将芒果卖给他。在Facebook，你与芒果销售商有联系吗?为此，你可在朋友中查。
借助队列实现的算法思路为:
def search(name):
search_queue = deque()
search_queue += graph[name]
searched = []
while search_queue:
person = search_queue.popleft()
if not person in searched:
if person_is_seller(person):
print person + " is a mongo seller!"
return True
else
search_queue += graph[person]
searched.append(person)
return False
这个算法将不断执⾏，直到满⾜以下条件之⼀：
到⼀位芒果销售商；
队列为空；
7.迪克斯特拉算法
前⼀章中的图是否存在路径，采⽤的是⼴度优先搜索算法，它出的是段数最少的路径。如果你想要到最快的路径，可以考虑使⽤另外⼀种算法 —— 迪克斯特拉算法。
这种带有权重边的图被称为加权图（不带权重的图被称为⾮加权图），其中包含4个主要步骤：
出最便宜的节点，即可在最短时间内到达的节点；
更新该节点的邻居的开销，其含义稍后介绍；
重复这个过程，直到对图中的所有节点都这么做了；
计算最终路径；
要计算加权图的最短路径，使⽤⼴度优先搜索；要计算⾮加权图的最短路径，使⽤迪克斯特拉算法。当然，迪克斯特拉只适⽤于有向⽆环图。
总体算法如下：
以伪代码⽅式：
node = find_lowest_cost_node(costs)
while node is not None: //结束条件：所有节点都被处理过
cost = costs[node]
neighbours = graph[node]
for n in neighbours.keys():
new_cost = cost + neighbours[n]
if costs[n] > new_cost:
costs[n] = new_cost
parents[n] = n
proceeded.append(node)
node = find_lowest_code_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_code and node not in processed: //如果当前节点成本更低且没有被使⽤过
lowest_cost = cost  //将其设置成开销最低的节点
lowest_cost_node = node
return lowest_cost_node
8.贪婪算法
教室调度问题
假如有如下问题，你希望将尽可能多的课程安排在某间教室，如何选出尽可能多且时间不冲突的课程呢？
具体做法可能⽐较简单：
1.选出最早结束的课，这就是在这间教室上的第⼀节课；
2.接下来，选择第⼀节课结束后开始的最早结束的课，这是第⼆节课，以此类推；
从算法实现和原理上来看，贪婪算法太容易、太显⽽易见，这正是贪婪算法的优点：简单易⾏！贪婪算法很简单：每步都采⽤最优的做法，⽤专业术语来说，就是每步都选择局部最优解，最终得到的就是全局最优解。
显然，贪婪算法并不是在所有情况下都⾏之有效，但它简单易⾏！
背包问题
对于不可切分物品的背包问题，贪婪算法显然不能获得最优解，但⾮常接近。这给我们⼀个启⽰：在有些情况下，完美是优秀的敌⼈，有时候你只需要到⼀个能够⼤致解决的算法，此时，贪婪算法就可以派上⽤场了，因为他们实现起来很容易，得到的结果⼜与正确结果⼤致接近。
集合覆盖问题
⼜假设你办了个⼴播节⽬，想让全美50个州的听众都能够收听地到，为此你决定要在哪些⼴播台中播出。因为每个⼴播台都需要费⽤，你需要⼒图在尽可能少的⼴播台播出。
每个⼴播台都有其覆盖的区域，不同⼴播台之间可能会有所交叉。
简单的⽅案可能如下：
1. 列出所有可能的⼴播台集合，这被称为幂集，可能的⼦集会有$2^N$个；
2. 在这些集合中，选出覆盖全美50个州的最⼩集合；
由于可能的⼦集会有$2N$个，所以运⾏时间为$O(2N)$，这个部分的⼯作量⾮常⼤，有没有合适的算法来解决这个问题呢？借助于近似算法。
使⽤下⾯的贪婪算法可以得到⾮常接近的解：
1. 选出这样的⼀个⼴播台，即它覆盖了最多的未覆盖州，即便有冲突也没有关系；
2. 重复第⼀步，直到覆盖了所有的州；
这就是⼀种近似算法，在获得精确解需要的时间太长时，可使⽤近似算法，判断其优劣的标准为：
速度有多快；
得到的近似解与最优解的接近程度；
在这⾥例⼦中，贪婪算法的运⾏时间为$O(N^2)$.
NP完全问题
旅⾏商问题，所有可能的路线，被称为阶乘函数，其复杂度为$O(N!)$，涉及到的城市⾮常多的时候，根本没有办法解决。
对于旅⾏商问题，什么样的近似算法是不错的呢？能到较短路径的算法就不错。NP完全问题的简单定义是，以难解著称的问题，很多聪明⼈都认为，根本不可能写出可以快速解决这些问题的⽅法。
但要判断出某⼀问题属于NP完全问题就⽐较难，易于解决的问题和NP完全问题的差别通常很⼩。虽然很难，但还是有⼀些蛛丝马迹可循的：
元素较少时运⾏速度⾮常快，但随着元素数量的增加，速度会变得很慢；
涉及“所有组合”的问题通常是NP完全问题；
不能将问题分解成⼩问题，必须可能考虑所有的情况，这些都属于NP完全问题；
问题涉及到序列（如旅⾏商问题中的城市序列）且难以解决；
问题涉及到集合（如⼴播集合）且难以解决；
⼩结
贪婪算法寻局部最优解，企图⽤这种⽅式来获得全局最优解；

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。