Python算法——《算法图解》笔记

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

算法目录

二分查找
大O表示法
选择排序
递归
快速排序，分而治之（D&C）
散列表——字典
广度优先搜索——BFS
Dijkstra算法
贪婪算法

二分查找

# 要求list是有序表，num是要查找的数字
# 二分查找貌似只能查找数值表
def binary_search(list, num):
low = 0
high = len(list) - 1 # 因为python数组（列表）是从0开始索引的 while low <= high:
mid = (low + high)
guess = list[mid]
if guess == num:
return "found it is " + str(mid)
if guess > num:
high = mid - 1
else:
low = mid + 1
return "not found" # python数组不同于matlab数组，python中间要用逗号隔开，而matlab不用
my_list = [1, 3, 5, 7, 9, 11, 13]
print(binary_search(my_list, 6))
print(binary_search(my_list, 9))

大O表示法

1. 能够比较操作数，表示算法运行时间的增速

2. 给出了一个时间的上限

3. 算法的速度并非时间，而是操作数的增速

4. O(logn)——对数时间（二分查找）

5. O(n)——线性时间（顺序查找）

6. O(n*logn)——快速排序

7. O(n^2)——选择排序

8. O(n!)——旅行商问题的解决办法

9. 常量并不会影响到大O表示法

选择排序

* 计算机内存如同一大堆抽屉

* 需要存储多个元素时可采用链表或数组

* 数组元素都在一起，因此读取速度快

* 链表是分开的，但是插入和删除速度很快

* 链表数组查找比数组慢，比链表快；插入比数组快，与链表相当

* 同一数组元素的类型均相同

寻找数组中的最小值的索引
def find_smallest_index(arr):
smallest = arr[0]
smallest_index = 0;
# python中检查数组长度的函数是len，而matlab中是length
for i in range(1, len(arr)):
if arr[i] < smallest:
smallest = arr[i]
smallest_index = i
return smallest_index # 对数组进行排序
def selection_insort(arr):
# create new array
new_arr = []
for i in range(len(arr)):
smallest_index = find_smallest_index(arr)
# array.pop()只能根据索引值弹出元素，so pop()应传入索引值
new_arr.append(arr.pop(smallest_index))
return new_arr mess_arr = [3, 1, 9, 2, 5, 4]
print("This is uninsort array: " + str(mess_arr))
insorted_arr = selection_insort(mess_arr)
print("This is insorted array: " + str(insorted_arr))

递归

* 使用循环程序性能可能更高，使用递归程序可能更容易理解

* 递归条件——让函数调用自己；基线条件——让函数不再调用自己

* 所有函数调用都进入递归调用栈

# 一个计算数学阶乘的递归调用
def func(x):
if x == 1:
return 1
else:
return x * func(x-1) print(func(3)) #一个计算数组和的递归调用
def func(arr):
if arr == []:
return 0
else:
# 这里不能用arr[0] + func()因为基线条件是arr==[]当arr
# 只有一个元素时python会将arr变为一个int数值，而不会是数组
return arr.pop() + func(arr) arr = [2, 3, 4]
print(func(arr))

快速排序，分而治之（D&C）

* 找出基线条件（很可能是一个空数组或者只包含一个元素的数组）

* 不断将问题分解直至满足基线条件

* 快速排序：

* 选取基准值

* 将数组分为两个子数组：小于基准值的元素和大于基准值的元素

* 对这两个子数组进行快速排序

# 快速排序——by myself
def quickly_sort(arr):
# 两个基线条件
if len(arr) < 2:
return arr
# 直接选取数组元素第一个当作基准值——递归条件
reference_value = arr[0]
larger_arr = []
smaller_arr = []
for i in range(1,len(arr)):
if arr[i] > reference_value:
larger_arr.append(arr[i])
# arr.pop(i)
else:
smaller_arr.append(arr[i])
# arr.pop(i)
return quickly_sort(smaller_arr) + [reference_value] + quickly_sort(larger_arr) mess_arr = [3, 1, 9, 2, 5, 4]
print("This is uninsort array: " + str(mess_arr))
insorted_arr = quickly_sort(mess_arr)
print("This is insorted array: " + str(insorted_arr))

# 快速排序——by others
def quickly_sort(arr):
# 基线条件
if len(arr) < 2:
return arr
else:
# 选取基准值——递归条件
pivot = arr[0] # 简洁明了选出较大数组与较小数组
larger = [i for i in arr[1:] if i > pivot]
smaller = [i for i in arr[1:] if i <= pivot]
# 递归调用
return quickly_sort(smaller) + [pivot] + quickly_sort(larger) mess_arr = [3, 1, 9, 2, 5, 4]
print("This is uninsort array: " + str(mess_arr))
insorted_arr = quickly_sort(mess_arr)
print("This is insorted array: " + str(insorted_arr))

散列表——字典

* 散列函数——将输入映射到数字；同一输入映射一致，不同输入映射到不同的数字

* 良好散列表包括：较低的填装因子0.7以下，良好的散列函数SHA函数

* 散列表查找（O(1)）、删除、插入都非常快

* 散列表适用于模拟映射关系、防止重复以及缓存数据

# 散列表——字典
# 创建字典的两种方案
price_list = dict()
price_list = {} # 添加数据
price_list["apple"] = 0.67
price_list["milk"] = 1.49
price_list["bread"] = 0.49 print(price_list)
print(price_list.keys())
print(price_list.values())
print(price_list.items()) # 判断是否在散列表中
flag = price_list.get("apple")
print(flag)
# 不同大小写诗不同与阿奴
flag = price_list.get("Apple")
print(flag)
flag = price_list.get("banana")
print(flag)

广度优先搜索——BFS

* 用于解决最短路径

* 利用import collection import deque 创建一个双端队列

* 栈是LIFO，队列是FIFO

* 广度优先搜索时，对于检查过的人不能再去检查

# 广度优先搜索示例
from collections import deque # 创建一个关系图（散列表）
graph = {}
# 单引号与双引号基本无使用上的区别，但是三引号可实现跨行输出
graph["you"] = ["alice", 'bob', "claire"]
graph["alice"] = ['peggy']
graph["bob"] = ["anuj", 'peggy']
graph['claire'] = ["thom", 'jonny']
graph["peggy"] = []
graph["anuj"] = []
graph["thom"] = []
graph["jonny"] = [] search_queue = deque()
search_queue += graph["you"] # 判断是否为经销商
def person_is_seller(name):
return (name[-1] == 'o') def search(search_queue):
searched = []
while search_queue: person = search_queue.popleft() #取出队列左边第一个元素
# 检查后不再检查
if person not in searched:
if person_is_seller(person):
print(person + " is a mago seller !")
return True
else:
# 把TA的朋友加入搜索队列
search_queue += graph[person]
searched.append(person)
print("Can't find mago seller in your friends")
return False
search(search_queue)

Dijkstra算法

* 找出目前最便宜的节点

* 更新该节点的邻居的开销

* 重复这个过程，直到对图中所有节点都这么做了

* 计算最终路径

* Dijkstra算法只适用与有向无环图

* 对于包含负权边的图，请使用贝尔曼-福德算法graph

# Dijkstra算法 # 寻找lowest_cost_node
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 # Create a graph
graph = {}
graph['start'] = {}
graph['start']['a'] = 6
graph['start']['b'] = 2
graph['a'] = {}
graph['a']['fin'] = 1
graph['b'] = {}
graph['b']['fin'] = 5
graph['b']['a'] = 3
graph['fin'] = {} # create a cost dict
infinity = float('inf')
costs = {}
costs['a'] = 6
costs['b'] = 2
costs['fin'] = infinity # creata a parent dict
parents = {}
parents['a'] = "start"
parents['b'] = "start"
parents['fin'] = None # record processed nodes
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)
node = find_lowest_cost_node(costs) route = ['fin']
node = parents['fin']
route.append(node)
node = parents[node]
route.append(node)
node = parents[node]
route.append(node) print(route)