算法图解

Tags
科普
数学
经济学
科幻
悬疑
传记
技术
小说
Author
Aditya Bhargava
Cover
https://img9.doubanio.com/view/subject/s/public/s29358625.jpg
Date
Apr 7, 2021 → Apr 30, 2021
Summary
数据结构与算法的入门读物。过于简单了，信息密度较低
Times
1
URL
Status
Not Started
Show
Show
第一章 算法简介第二章 选择排序第三章 递归第四章 快速排序第五章 散列表第六章 广度优先搜索第七章 迪克斯特拉算法第八章 贪婪算法

第一章 算法简介

二分查找
class BinarySearch():
    def search(self, list, item):
        '''
        数据需要是从小到大排列
        '''
        low = 0
        high = len(list)-1  
        while (low <= high):
            mid = (low + high)//2 
            if(list[mid]>item):
                high = mid-1      # 注意要 - 1
            if(list[mid]<item):
                low = mid+1       # 注意要 + 1
            if(list[mid] == item):
                return mid   
        return None
        

if __name__ == '__main__':
    list = [53,56]
    item = 56
    S = BinarySearch()
    idx = S.search(list, item)
    print(idx)
查找数据，当列表包含10亿个元素时，二分查找所需时间为简单查找的3300万倍。有鉴于此，仅知道算法需要多长时间才能运行完毕还不够，还需知道运行时间如何随列表增长而增加。这正是大O表示法的用武之地。
  • 大O表示法让你能够比较操作数，它指出了算法运行时间的增速
  • 大O表示法指出了最糟情况下的运行时间
notion imagenotion image
  • 算法的速度指的并非时间，而是操作数的增速。
  • 谈论算法的速度时，我们说的是随着输入的增加，其运行时间将以什么样的速度增加。
  • 算法的运行时间用大O表示法表示。
  • O(log n)比O(n)快，当需要搜索的元素越多时，前者比后者快得越多。

第二章 选择排序

选择排序 思想 每次选择最大（最小）的添加到新的数组，然后把原数组中该元素删掉，再次选择。。
操作：
  1. 新建一个数组
  1. 找到原数组中最大（最小）的放到新数组中
  1. 把原数组中该元素删掉
  1. 循环2，3 循环的依据是 数组的 长度
选择排序关键在选择，先选择最大（或最小）的，再将将其放到上一个选择的元素后面。所以一共要选择n次，插入n次。一共是
所以时间复杂度为

第三章 递归

恨它的、爱它的以及恨了几年后又爱上它的
如果使用循环，程序的性能可能更高；
如果使用递归，程序可能更容易理解
 
编写递归函数时，必须告诉它何时停止递归。正因为如此，每个递归函数都有两部分：基线条件（base case）和递归条件（recursive case）。
  • 递归条件指的是函数调用自己
  • 基线条件则指的是函数不再调用自己，从而避免形成无限循环。
例子：输出大于1小于i的值
def countdown(i):
		if i <=1:            # 基线条件
				return
		else:                # 递归条件
				countdown(i-1)
notion imagenotion image
# 用递归 来求列表之和
def quick_sum(arr):
		if len(arr) == 1    # 基线条件
				return arr[0]
		else:               # 递归条件
				return arr[0] + quick_sum(arr[1:])    # 分而治之的思想！！！

第四章 快速排序

采用了分而治之的思想，其实就是递归的引用
from typing import List

def quick_sort(arr:List):
		if len(arr) <= 1:   # 基线条件 
				return arr
		else:               # 递归条件
				mid = arr[0]  
				less_arr = [i for i in arr[1:] if i <= mid]
				great_arr = [i for i in arr[1:] if i >mid]
				return quick_sort(less_arr) + [mid] + quick_sort(great_arr)

第五章 散列表

散列表， python中字典的实现就是散列表。搜索复杂度为O(1)

第六章 广度优先搜索

notion imagenotion image

# 构建图
graph = dict()
graph['you'] = ['alice', 'bob', 'claire']
graph['alice'] = ['peggy']
graph['bob'] = ["anuj", "peggy"]
graph["claire"] = ["thom", "jonny"]
graph["anuj"] = []
graph["peggy"] = []
graph["thom"] = []
graph["jonny"] = []

def Is_target(x:str):
    return x[-1] == 'k'

def breadth_search(x:str):
    searching = deque()     # 维护一个队列 ，里面存放待搜索节点
    searching += graph[x]   # 初始时，将起始节点的子节点存进去
    searched = []   # 维护一个列表， 存放已经搜索过的节点

    while searching: 
        person = searching.popleft()  # 将当前搜索过的直接pop出来，以为大循环是 while 
        if person not in searched:
            if Is_target(person):
                print(f"{person} is the target")
                return True
            else:
                searched.append(person)    
                searching += graph[person]
    print('Not find')
    return False
核心：用队列来存放待搜索节点，因为队列是先进先出的

第七章 迪克斯特拉算法

用于查找有权图代价最小路径
notion imagenotion image
# 定义图 graph 字典
# 定义cost 字典 初始只存放当前节点可以到达的cost，其他节点均为 float('inf')
# parents 存放父节点， 初始为空

# the graph
graph = {}
graph["start"] = {}
graph["start"]["a"] = 5
graph["start"]["b"] = 2

graph["a"] = {}
graph["a"]["c"] = 4
graph["a"]["d"] = 2

graph["b"] = {}
graph["b"]["a"] = 8
graph["b"]["d"] = 7

graph["c"] = {}
graph["c"]["fin"] = 3
graph["c"]["d"] = 6

graph["d"] = {}
graph["d"]["fin"] = 1

graph["fin"] = {}


# the costs table
infinity = float("inf")
costs = {}
costs["a"] = 5
costs["b"] = 2
costs["c"] = infinity
costs["d"] = infinity
costs["fin"] = infinity

# the parents table
parents = {}
parents["a"] = "start"
parents["b"] = "start"
parents["fin"] = None

processed = []# the parents table
def dijkstras_algorithm():
    node = find_low_cost()  # 每次都从costs里面的最小代价找起
    while node:
        neighbor = graph[node]
        for n in neighbor.keys():
            if neighbor[n] + costs[node] < costs[n]:   # 找到代价更小的路径，就更新costs和parents
                costs[n] = neighbor[n] + costs[node]
                parents[n] = node
        processed.append(node)   # 将该节点存放到已处理的列表里面，再开始寻找下一个节点
        node = find_low_cost()

# 在costs里面查找cost最小的节点
def find_low_cost():
    low_cost = float('inf')
    low_cost_node = None
    for n in costs:
        if n not in processed and costs[n] < low_cost:
            low_cost = costs[n]
            low_cost_node = n
    return low_cost_node



dijkstras_algorithm()
print(costs)

{'a': 5, 'b': 2, 'c': 9, 'd': 7, 'fin': 8}

第八章 贪婪算法

每次都选择对当前而言最佳的策略，即只考虑当前最优，而不考虑全局最优。
问题：有如下四个广播，还有八个州。选择最少的广播使其覆盖八个州
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_station = set()

def greedy_algorithms(states_needed):
    while states_needed: 
    '''   
		查找 最经典的算法：
         1:初始化两个值 ，一个是 查找指标的最佳值，一个是找到的最佳目标对象
				 2：开始遍历数组查找。
				 3：比较当前对象的指标和之前最佳指标值的大小，即判断是否需要更新最佳指标值及最佳对象
         4：(如有必要)更新最佳指标值和对象
				 5：继续第2步 遍历查找（有时需要设置一个已经查找过的对象集合，保证查找不重复）
		'''
        best_station = None
        best_station_cover = set()
        for station, state_coverd in stations.items():
            coverd = state_coverd & states_needed
            if len(coverd) > len(best_station_cover):
                best_station_cover = coverd
                best_station = station

        final_station.add(best_station)
        states_needed -= best_station_cover
    

greedy_algorithms(states_needed)
print(final_station)
# 输出
{'kthree', 'ktwo', 'kone', 'kfive'}