1.大O表示法是一种特殊的表示法，指出了算法的速度有多快。O（n）
小结：
二分查找的速度比简单查找快得多。
O (log n )比O (n )快。需要搜索的元素越多，前者比后者就快得越多。
算法运行时间并不以秒为单位。
算法运行时间是从其增速的角度度量的。
算法运行时间用大O表示法表示。
2.链表和数组
链表中的元素可存储在内存的任何地方。
数组和链表哪个用得更多呢？显然要看情况。但数组用得很多，因为它
支持随机访问。有两种访问方式：随机访问 和顺序访问 。顺序访问意
味着从第一个元素开始逐个地读取元素。链表只能顺序访问：要读取链
表的第十个元素，得先读取前九个元素，并沿链接找到第十个元素。随
机访问意味着可直接跳到第十个元素。本书经常说数组的读取速度更
快，这是因为它们支持随机访问。很多情况都要求能够随机访问，因此
数组用得很多。
小结：
计算机内存犹如一大堆抽屉。
需要存储多个元素时，可使用数组或链表。
数组的元素都在一起。
链表的元素是分开的，其中每个元素都存储了下一个元素的地址。
数组的读取速度很快。
链表的插入和删除速度很快。
在同一个数组中，所有元素的类型都必须相同（都为int、double等）。
def binary_search(list,item):
'''二分查找'''
low=0
high=len(list)-1
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
my_list=[1,3,5,7,9]
print(binary_search(my_list,3))
def findsmallest(arr):
'''排序算法'''
smallest=arr[0] #存储最小的值
smallest_index=0 #存储最小元素的索引
for i in range(1,len(arr)):
if arr[i]<smallest:
smallest=arr[i]
smallest_index=i
return smallest_index
def selectionsort(arr):
newarr=[]
for i in range(len(arr)):
smallest=findsmallest(arr)
newarr.append(arr.pop(smallest))
return newarr
print(selectionsort([5,3,6,2,10]))
def countdown(i):
'''递归'''
print(i)
if i <=0: #基线条件
return
else: #递归条件
countdown(i-1)
print(countdown(5))
3.递归指的是调用自己的函数。
每个递归函数都有两个条件：基线条件和递归条件。
栈有两种操作：压入和弹出。
所有函数调用都进入调用栈。
调用栈可能很长，这将占用大量的内存。
4.排序
D&C将问题逐步分解。使用D&C处理列表时，基线条件很可能是空数组或只包含一个元素的数组。
实现快速排序时，请随机地选择用作基准值的元素。快速排序的平均运行时间为O (n log n )。
大O表示法中的常量有时候事关重大，这就是快速排序比合并排序快的原因所在。
比较简单查找和二分查找时，常量几乎无关紧要，因为列表很长
时，O (log n )的速度比O (n )快得多。
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]))
5.散列表在python中就是字典
无论你访问哪个网站，其网址都必须转换为IP地址。这不是将网址映射到IP地址吗？好像非常适合使用散列表啰！这个过程被称为DNS解析 （DNS resolution），散列表是提供这种功能的方式之一。（google.com-74.123.139.3）
散列表适合用于：
仿真映射关系；
防止重复；
缓存/记住数据，以免服务器再通过处理来生成它们。
如果两个键映射到了同一个位置，就在这个位置存储一个链表。
散列函数很重要 。前面的散列函数将所有的键都映射到一个位置，而最理想的情况是，散列函数将键均匀地映射到散列表的不同位置。
如果散列表存储的链表很长，散列表的速度将急剧下降。然而，如果使用的散列函数很好 ，这些链表就不会很长！
你可以结合散列函数和数组来创建散列表。
冲突很糟糕，你应使用可以最大限度减少冲突的散列函数。
散列表的查找、插入和删除速度都非常快。
散列表适合用于仿真映射关系。
一旦填装因子超过0.7，就该调整散列表的长度。
散列表可用于缓存数据（例如，在Web服务器上）。
散列表非常适合用于防止重复。
6.广度优先搜索指出是否有从A到B的路径。
如果有，广度优先搜索将找出最短路径。
面临类似于寻找最短路径的问题时，可尝试使用图来创建模型，再使用广度优先搜索来解决问题。
有向图中的边为箭头，箭头的方向指定了关系的方向，例如，rama→adit表示rama欠adit钱。
无向图中的边不带箭头，其中的关系是双向的，例如，ross - rachel表示“ross与rachel约会，而rachel也与ross约会”。
队列是先进先出（FIFO）的。
栈是后进先出（LIFO）的。
你需要按加入顺序检查搜索列表中的人，否则找到的就不是最短路径，因此搜索列表必须是队列。
对于检查过的人，务必不要再去检查，否则可能导致无限循环。
from collections import deque
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"] = []
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+"id a mango seller!")
return True
else:
search_queue += graph[person]
searched.append(person)
return False
def person_is_seller(name):
return name[-1] == 'm'
print(search("bob"))
graph = {}
graph["you"] = ["alice", "bob", "claire"]
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"] = {} #终点没有任何邻居
infinity = float("inf")#无穷大
costs = {}#创建开销列表
costs["a"] = 6
costs["b"] = 2
costs["fin"] = infinity
parents = {}#父点散列表
parents["a"] = "start"
parents["b"] = "start"
parents["fin"] = None
processed = []#记录处理过的节点
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
node = find_lowest_cost_node(costs) #在未处理的节点中找出开销最小的节点
while node is not None:#这个while循环在所有节点都被处理过后结束
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) #将当前节点标记为处理过
node = find_lowest_cost_node(costs)#找出接下来要处理的节点，并循环
print(find_lowest_cost_node[6])
广度优先搜索用于在非加权图中查找最短路径。
狄克斯特拉算法用于在加权图中查找最短路径。
仅当权重为正时狄克斯特拉算法才管用。
如果图中包含负权边，请使用贝尔曼-福德算法。
states_needed = set(["mt", "wa", "or", "id", "nv", "ut","ca", "az"]) #你传入一个数组，它被转换为集合
stations = {}
stations["kone"] = set(["id", "nv", "ut"])
stations["ktwo"] = set(["wa", "id", "mt"])
stations["kthree"] = set(["or", "nv", "ca"])
stations["kfour"] = set(["nv", "ut"])
stations["kfive"] = set(["ca", "az"])
final_stations = set()
best_station = None
states_covered = set()
for station, states_for_station in stations.items():
covered = states_needed & states_for_station #它计算交集
if len(covered) > len(states_covered):
best_station = station
states_covered = covered
states_needed -= states_covered
final_stations.add(best_station)
print(final_stations)
贪婪算法寻找局部最优解，企图以这种方式获得全局最优解。
对于NP完全问题，还没有找到快速解决方案。
面临NP完全问题时，最佳的做法是使用近似算法。
贪婪算法易于实现、运行速度快，是不错的近似算法。
