咸糖记录编程的地方

念念不忘,必有回响。

目录
算法图解4.5-7章笔记(qsort,Dijkstra)
/  

算法图解4.5-7章笔记(qsort,Dijkstra)

qsort 时间复杂度

  • 最糟糕(头)
    1. 以头为基准,需要涉及整个列表
    2. 因为要遍历两边的数组,而且O(n)不受常量影响
  • 最优(中间)
    1. 以中间为基准(类似二分log n)
    2. 每层O(n)
      最佳的就是平均的情况
      TODO: 随机的选择用作基准的元素
array = [5,7,2,4,3,1,8,6]
from random import randint
def qsort(array):
    if len(array)<=1:
        return array
    ran=randint(0,len(array)-1)

    mid = array[ran]
    array.pop(ran)
    smaller = [ i for i in array   if i<=mid]
    bigger = [i for i in array  if i>mid ]
    return  qsort(smaller) + [mid] +qsort(bigger)

print(qsort(array))

散列表

DNS 解析
域名->ip地址

广度优先遍历

from collections import deque

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

def person_is_seller(name):
    return name[-1] == 'm'
# deque

def find():
    search_queue = deque()
    search_queue += graph["you"]
    while search_queue:
        person = search_queue.popleft()
        if person_is_seller(person):
            print(person +"is seller")
            return True
        else:
            search_queue +=graph[person]
    return False
find()

使用一个队列 从右侧加入一个节点的所有的下个节点
然后从左侧读取一个节点 往返直到队列为空

from collections import deque
def person_is_seller(name):
    return name[-1] == 'm'
graph = {}
graph['you'] = ["alice","bob","claire"]
graph['bob'] = ["anuj","peggy"]
graph["alice"] = ["peggy"]
graph["claire"] = ["thom","jooy"]
graph["anuj"] = []
graph["peggy"] = []
graph["thom"] = []
graph["jonny"] = []
search_queue = deque()

def find2(search_queue):
    if search_queue:
        person = search_queue.popleft()
        if person_is_seller(person):
            print(person +"is seller")
            return True
        else:
            search_queue +=graph[person]
        return find2(search_queue)
    else:
        return None

search_queue += graph["you"]
print(find2(search_queue))
  • 广度优先遍历是找到是否A-B的
  • 有就可以找到最短路径
  • 有向图可以指定方向
  • 无向图关系双向
  • 按照顺序放入队列就可以找到最短路径,检查过的人需要放入去重列表

迪杰斯特拉算法

graph = {}
graph['start'] = {}
graph['start']['a'] = 5
graph['start']['b'] = 0
graph['a'] = {}
graph['a']['c'] = 15
graph['a']['d'] = 20
graph['b'] = {}
graph['b']['c'] = 30
graph['b']['d'] = 25
graph['c'] = {}
graph['c']['fin'] = 20
graph['d'] = {}
graph['d']['fin'] = 10
graph['fin'] = {}
costs = {}



costs['a'] = 5
costs['b'] = 0
costs['c'] = float("inf")
costs['d'] = float("inf")
costs['fin'] = float("inf")
parents = {}
parents['a'] = 'start'
parents['b'] = 'start'
parents['c'] = 'start'
parents['d'] = 'start'
parents['fin'] = None
processed = []
def find_lowst(costs):
    low_cost = float("inf")
    low_cost_node = None
    for node in costs:
        cost = costs[node]
        if cost < low_cost and node not in processed:
            low_cost = cost
            low_cost_node = node
    return low_cost_node

node = find_lowst(costs)
while node is not  None:
    cost = costs[node]
    friends = graph[node]
    for friend in friends.keys():
        new_cost = friends[friend]+cost
        # if new_cost <
        if new_cost < costs[friend]:
            costs[friend] = new_cost
            parents[friend] = node
    processed.append(node)
    node = find_lowst(costs)
print(costs)

简洁版本

graph = {}
graph['start'] = {}
graph['start']['a'] = 5
graph['start']['b'] = 0
graph['a'] = {}
graph['a']['c'] = 15
graph['a']['d'] = 20
graph['b'] = {}
graph['b']['c'] = 30
graph['b']['d'] = 25
graph['c'] = {}
graph['c']['fin'] = 20
graph['d'] = {}
graph['d']['fin'] = 10
graph['fin'] = {}
def get_costs_parent(graph):
    costs = {}
    parents = {}
    for node in graph.keys():
        if node in graph['start'].keys():
            costs[node] = graph['start'][node]
            parents[node] = 'start'
        else:
            costs[node] = float('inf')
            parents[node] = None
    return costs,parents
costs ,parents= get_costs_parent(graph)

processed = []
def find_lowst(costs):
    low_cost = float("inf")
    low_cost_node = None
    for node in costs:
        cost = costs[node]
        if cost < low_cost and node not in processed:
            low_cost = cost
            low_cost_node = node
    return low_cost_node
node = find_lowst(costs)
while node is not  None:
    cost = costs[node]
    friends = graph[node]
    for friend in friends.keys():
        new_cost = friends[friend]+cost
        # if new_cost <
        if new_cost < costs[friend]:
            costs[friend] = new_cost
            parents[friend] = node
    processed.append(node)
    node = find_lowst(costs)
print(costs['fin'])
graph = {}
graph['start'] = {}
graph['start']['a'] = 5
graph['start']['b'] = 0
graph['a'] = {}
graph['a']['c'] = 15
graph['a']['d'] = 20
graph['b'] = {}
graph['b']['c'] = 30
graph['b']['d'] = 25
graph['c'] = {}
graph['c']['fin'] = 20
graph['d'] = {}
graph['d']['fin'] = 10
graph['fin'] = {}
def get_costs_parent(graph):
    costs = {}
    parents = {}
    for node in graph.keys():
        if node in graph['start'].keys():
            costs[node] = graph['start'][node]
            parents[node] = 'start'
        else:
            costs[node] = float('inf')
            parents[node] = None
    return costs,parents
costs ,parents= get_costs_parent(graph)

def find_lowst(costs):
    low_cost = float("inf")
    low_cost_node = None
    for node in costs:
        cost = costs[node]
        if cost < low_cost and node not in processed:
            low_cost = cost
            low_cost_node = node
    return low_cost_node
def find_short_path(costs,processed,parents):
    node = find_lowst(costs)
    if node is not None:
        cost = costs[node]
        neighbors = graph[node]
        for n in neighbors.keys():
            new_cost = neighbors[n] + cost
            if new_cost < costs[n]:
                costs[n] = new_cost
                parents[n] = node
        processed.append(node)
        return find_short_path(costs,processed,parents)

    else:
        return costs['fin']
processed = []

fastst = find_short_path(costs,processed,parents)

递归实现:
* 基准条件:找到的最小节点为空
* 递归条件:还有节点没有处理

####主要思路:
1. 找到一个节点然后取找他的所有相邻节点
2. 将相邻节点到本节点的距离与本节点到起点的距离相加
3. 判断是否比相邻结点原来的距离短
4. 如果更短直接更新,并且加入去重列表
5. 如何取找一个节点:我们选取的是最小的节点,如果这个节点不在去重队列
并且是最小的,就以他为节点更新他的相邻节点,至于我们要选择最小的,是因为
要是选择最大的化会遇到无限大的情况(没有找到到达线路)


标题:算法图解4.5-7章笔记(qsort,Dijkstra)
作者:xiantang
地址:http://xiantang.info/articles/2019/06/03/1559551096404.html

评论