算法的开销
什么是算法
算法就是解决一个问题需要进行的计算步骤，尤其是解决复杂问题时，需要考虑算法的正确率，也要考虑算法的时间和空间成本
算法的时间开销 ```python 例子： 眨眼 0.1s 算加法 2s 烧开水 8分钟 睡觉 7小时 工程 6个月 太空旅行 30年
类似的： 简单算法 O(1) 一层循环 O(n) 两层循环 O(n2)
注意区分概念：
O(1) o是时间的估计，不是精准，1表示简单，相当于一维简单度，即使计算有5步，也是1
O(n) 表示简单的事务要重复执行n次，复杂度为一维简单乘以n
O(logn) 表示单层循环中，每次次数减半，则复杂度低于O(n)
时间复杂度的鄙视链：
O(1) < O(logn) < O(n) < O(nlog(n)<O(n2)
- 算法的空间开销```python类似于时间复杂度O(1) 单个变量O(n) n长的列表O(nm) n*m的二维列表
- 递归算法和复杂度
```python
思路：
把最下面一个盘子看成一个 把除了最下面的n-1看成一个整体
则步骤是： 1，把n-1通过c柱移动到b柱 2，把最下面的一个从a柱移动到c柱 3，把n-1个通过a柱移动到c柱 因为每个柱子都是对等的，所以可以使用递归解决问题：把n-1的移动问题使用同样的方式分解。
count = 0
def hanoi(n, a,b,c):
if n>0:
hanoi(n-1,a,c,b)
count += 1
print(‘第%s步: 把%s移动到%s’ %(count,a,c))
hanoi(n-1,b,a,c)
hanoi(3,’A’,’B’,’C’)
- 顺序查找算法
```python
复杂度 O(n)
- 二分法查找 ```python 时间复杂度： O(logn) 但是列表必须先排序，这个开销是大于O(n)
<a name="qLlAB"></a>
### 排序算法
- 冒泡法
- 选择法
- 快速排序法
```python
"""
快速排序
原理：每次选择一个数，让它归位，确保它后面的数都比他大，前面的数都比他小，这样成功将问题缩小为原来的大约1/2，第二次对左右两部分重复上次步骤
关键是归位的流程：
[2, 3, 6, 18 ,25, 0, 11, 1, 9 ]
low high
a, 需要两个指针low和high， low起始0，hih的起始n-1
b, 9为需要归位的数，将9存为temp，high空位，从低位区寻找比9大的数
c, low指针移动到18，将18移动到high的位置，18处为空位
d, 然后左移high指针，找到比9小的数，把1移动到low指针的位置，
e，到最后low和high指针到重合，把9放到这个位置，实现一次归位
f，然后对左右两边分别进行归位，直到每个部分的长度小于等于1，递归完成整个排序
优点：多数情况下的时间复杂度为 O(nlogn), 极端情况下为O(n*n)
缺点：逻辑稍复杂，需要用到递归
时间复杂度 = O(nlogn) 长度为5万的列表的排序用时: 0.16秒
空间复杂度 = O(n)
"""
import sys
import random
from utils import run_time, read_date
# 把递归深度设置为1万次以内
sys.setrecursionlimit(10000)
li = read_date('1.in.txt')
li = li[:50000]
# li = list(range(50000,0,-1)) #验证倒序的极端情况下的表现
def partition(li, low, high):
"""
归位函数
:param li: 列表
:param low: 低位指针
:param high: 高位指针
:return: 归位后的下标
"""
# 随机从列表中找一个数，与最高位的数互换
if high-low > 2: # 如果列表太短就没必要交换了
t = random.randint(low,high-1) # 在本次partition的范围内选择一个除了最高位的下标
li[high],li[t] = li[t],li[high] # 与最高位进行交换
target = li[high] # 把最高位的数作为要归位的数的临时存储在target
while low < high:
while low < high and li[low] <= target: #高位指针的位置空缺，在低位区寻找比target大的数，如果小，低位指针右移一格
low += 1
else:
if low == high: # 如果高低位指针重合，则归位结束
li[low] = target
return low
else:
li[high] = li[low] # 如果找到了比target大的数，且指针不重合，则把该数移动到高位指针的空缺处，低位指针变为空缺
high -= 1 # 同时高位指针没有必要在比较，可以直接左移一格，这样写，代码稍微麻烦一点，但是效率可能略高一些。
while low < high and li[high] >= target: # 按同样的方法在高位区找到比target小的数放到空缺处
high -= 1
else:
if low == high:
li[low] = target
return low
else:
li[low] = li[high]
low += 1
li[low] = target
return low
@run_time
def quick_sort(li):
# 套个马甲避免计时装饰器在递归中被重复打印
def fast_sort(li, low, high):
# 采用递归的方法，特别的注意递归结束的条件：高低位指针不能交叉
if low < high:
# 不对列表做切片处理，只传待处理部分的首尾下标，避免切片耗费资源
mid = partition(li, low, high)
fast_sort(li, low, mid - 1)
fast_sort(li, mid + 1, high)
fast_sort(li, 0, len(li) - 1)
quick_sort(li)
print(li)
- 堆排序
- 归并排序
- 桶排序
- 希尔排序
- 基数排序
- topk排序 - 找最大的k个数
排序练习题1
字符串排序问题，不一定所有的问题都要用排序法，要考虑排序的成本和开销
二分查找法的前提是数据有序
"""
以尽可能多的方法解决2-sum问题并分析其时间复杂度：
给定一个列表和一个整数，从列表中找到两个数，使得两数之和等于给定的数，返回两个数的下标。
题目保证有且只有一组解
知识点：
1. 对于大数据量二分查找的效率logn还比较高
2. 如果支持字典，查找的效率也不错，通过哈希方法快速计算得到目标值的下标
3. 列表的sort方法 li.sort(key=lambda x:x[0]) key要传入函数, 必须callable
"""
import sys
import random
from utils import run_time, read_date,read_sum_two_date
sys.setrecursionlimit(1000)
data_yield_obj = read_sum_two_date('2-sumtwo.in.txt')
total,li = next(data_yield_obj)
total,li = next(data_yield_obj)
print('total,li:',total,li)
## 方法一，新建一个列表，每个元素是一个元组，每个元组包含原列表元素的值和原列表的下标，然后对此列表排序，然后用二分法进行查找
lis = [(num,i) for i,num in enumerate(li)]
lis.sort(key=lambda x:x[0])
print('original li:',li)
print('original lis:',lis)
@run_time
def two_sum(li,total):
lis = li
# 遍历每个数，计算第二个数的值应为target，然后在的范围内搜索target
for i in lis:
if i[0] < total:
target = total - i[0] # 计算另外一个数应该是target
low = 0
high = len(lis)-1
while low <= high: # 使用二分查找在范围内搜寻target
mid = (low+high)//2
if lis[mid][0] == target:
return sorted((i[1],lis[mid][1]))
elif lis[mid][0] > target:
high = mid-1
else:
low = mid + 1
else:
return False # 如果第一个数都大于total，后面的数肯定也大于total，搜寻失败，返回
return False
res = two_sum(lis,total)
print(res)
print(li[res[0]],li[res[1]])
# 方法二 也是先排序，在缩小的范围内遍历可能的组合
@run_time
def extensive_search(li,total):
for i,val in enumerate(lis):
# j 是 i 前面的元素，往前加
for j in range(i):
if lis[i][0] + lis[j][0] == total:
return sorted([lis[i][1],lis[j][1]])
return False
res = extensive_search(lis,total)
print(res)
## 方法三，使用字典来快速判断target是不是在列表里面
@run_time
def fast_two_sum(li,total):
dic = { num:i for i,num in enumerate(li) }
for val,i in dic.items():
target = total - val
target_index = dic.get(target,None)
if target_index is None:
continue
else:
return sorted([target_index, i])
return False
res = fast_two_sum(li,total)
print(res)
print(li[res[0]],li[res[1]])
# 存在多个结果，所以三个算法都是对的
能用循环就就不用递归，递归的效率和开销都不低 ，而且有层数限制
数据结构
- 列表
- 字典
- 堆栈 单侧进出的列表 ，适用于解决括号配对问题，路径深度搜索等有回溯的问题
- 队列 一侧进，一侧出的列表，采用循环列表节约资源，路劲广度搜索问题
- 链表 双向链表 ```python “””
- 封装一个双链表类，并实现双链表的创建、查找、插入和删除 “””
class Node: “””节点””” def init(self, val=None): self.val = val self.next = None self.prev = None def str(self): return ‘<%s>’ % (self.val)
class ChainTable: “””双向链表””” def init(self, itemlist): self.head = Node(itemlist[0]) self.tail = self.head for item in itemlist[1:]: new_node = Node(item) self.tail.next = new_node new_node.prev = self.tail self.tail = new_node
def find(self,val):
"""按照值查找节点"""
node = self.head
while node:
if node.val == val :
return node
else:
node = node.next
return None
def delete(self,node):
"""删除节点"""
if node == self.head:
self.head = node.next
self.head.prev = None
elif node == self.tail:
self.tail = node.prev
self.tail.next = None
else:
node.prev.next = node.next
node.next.prev = node.prev
print('删除中间节点成功，head,tail',self.head,self.tail)
del node
def insert(self,pre_node,node):
"""插入节点"""
if pre_node==self.tail:
self.append(node)
else:
node.next = pre_node.next
node.prev = pre_node
node.next.prev = node
pre_node.next = node
print('insert node:%s' % node)
def append(self,new_node):
self.tail.next = new_node
new_node.prev = self.tail
self.tail = new_node
self.tail.next = None # 必须把tail的next置为空，否则打印链表可能进入死循环
print('append node: %s' % new_node)
def __str__(self):
li = []
node = self.head
while node:
li.append('(%s:p %s n:%s)' %(node.prev,node,node.next))
node = node.next
return '-'.join(map(str,li))
新建链表，使用列表来初始化
chaintable = ChainTable([20,])
新建节点
node1 = Node(30) node2 = Node(40) node3 = Node(100) node4 = Node(88)
在链表尾部添加节点
chaintable.append(node1) chaintable.append(node2) chaintable.append(node3) print(chaintable)
删除节点
chaintable.delete(node1) print(chaintable)
插入节点
chaintable.insert(node2,node4) print(chaintable)
按照值来查找节点
node = chaintable.find(100) if node: print(‘找到节点：%s’% node) else: print(‘没有找到节点’)
- 哈希表
- 哈希表原理
- 哈希表的应用：字典，集合set
- 哈希函数： 求余数， MD5，SHA-2
- 二叉树 平衡二叉树AVL B树
<a name="UES3F"></a>
## 经典算法
- 斐波那契数列-递归
- 贪心算法
- 字符串拼接
- 动态规划
```python
"""
6. 使用动态规划算法实现最长公共子序列问题
原理：
假设Zk是字符串 Xm, Yn的公共序列， m,n,k表示长度。
如果X[m-1]=Y[n-1], 则Z[k-1]=X[m-1]=Y[n-1], 且Zk-1是Xm-1和Yn-1(即去掉最后一位的序列）的公共序列
如果X[m-1]!=Y[n-1]，则 Zk是 Xm-1和Yn的公共序列或者 Xm和Yn-1的公共序列
所以有如下式子：
C[i,j] 表示Xi和Yj的公共序列的最大长度，则
当i=j=0时， C[i,j]=0
当Xi=Yj时， C[i,j]=C[i-1,j-1]+1
当Xi!=Yj时，C[i,j]= max(C[i-1,j],C[i,j-1])
于是，可以从字符串的起始位开始构造一个计算表，m+1行n+1列，从起始点开始依次计算直到结尾，最后一格就是最大公共子序列的长度。
在这个过程中把Xi=Yj的时刻存下来，就是最长公共子序列了
"""
# 找到公共子序列的长度
# def find_LCS_length(x,y):
# m = len(x)
# n = len(y)
# c = [[0 for each in range(n+1)] for each in range(m+1)] # 构造长度计算列表, 多一列空字符串行和列
# for i in range(1,m+1):
# for j in range(1,n+1):
# if x[i-1] == y[j-1]: # i-1 因为i从1开始，而x的序号从0开始
# c[i][j] = c[i-1][j-1]+1
# else:
# c[i][j] = max(c[i-1][j],c[i][j-1])
# for line in c:
# print(line)
# return c[m][n]
#
# x = 'ABCBDAB'
# y = 'BDCABA'
# 找到最长公共子序列
# 原理是：构建计算表，存储每个数值的来源，然后从结尾处回溯
def find_LCS(x,y):
m = len(x)
n = len(y)
# 构造长度计算列表, 第一个0存储长度，第二个0存储值的来源方向
c = [[[0,0] for each in range(n+1)] for each in range(m+1)]
for i in range(1,m+1):
for j in range(1,n+1):
if x[i-1] == y[j-1]: # i-1 因为i从1开始，而x的序号从0开始
c[i][j][0] = c[i-1][j-1][0]+1
c[i][j][1] = '斜'
else:
if c[i-1][j][0] > c[i][j-1][0]:
c[i][j][0] = c[i-1][j][0]
c[i][j][1] = '上'
else:
c[i][j][0] = c[i][j-1][0]
c[i][j][1] = '左'
# for line in c:
# print(line)
return c
def track_back(x,y):
i = len(x)
j = len(y)
c = find_LCS(x,y)
max_length = c[i][j][0]
route = []
while i>0 and j>0:
if c[i][j][1] == '斜':
route.append(x[i-1])
i -= 1
j -= 1
elif c[i][j][1] == '左':
j -= 1
else:
i -= 1
route.reverse()
print('max_length:',max_length)
print('max_LCS:',''.join(route))
# 使用作业用例，测试程序的效果
with open('5.in_LCS.txt','r') as fp:
for line in fp:
x,y = line.split(' ')
print('-'*40)
print('x:', x)
print('y:', y)
track_back(x, y)
print('-' * 40)
- 迷宫寻路问题-动态规划 ```python “””
- 使用至少一种算法解决迷宫寻路问题
两种基本思路：
- 使用堆栈存储路径并回溯，这是深度优先策略
- 使用队列存储路径并回溯，广度优先策略
“””
maze = [ [1,1,1,1,1,1,1,1,1,1], [1,0,0,1,0,0,0,1,0,1], [1,0,0,1,0,0,0,1,0,1], [1,0,0,0,0,1,1,1,0,1], [1,0,1,1,1,0,0,0,0,1], [1,0,0,0,1,0,0,0,0,1], [1,0,1,0,0,0,1,1,0,1], [1,0,1,1,1,0,1,1,0,1], [1,1,0,0,0,0,0,0,0,1], [1,1,1,1,1,1,1,1,1,1], ]
begin = [1,1] end = [8,8]
dirs = [ lambda x,y: (x-1,y), lambda x,y: (x+1,y), lambda x,y: (x,y-1), lambda x,y: (x,y+1), ]
方法一： 采用栈的方法，把回退的路径存储起来，并把已经走过不通的路标记一下。类似于蚂蚁找路的方法
def find_path(maze,begin,end): stack =[] # 栈，用于存储路径，当栈空的时候也就意味着没有任何可行路径 stack.append(begin) # 起始点压入栈中 while stack: if stack[-1] == end: print(“找到出路”) return stack cur_pos = stack[-1] # 栈顶是当前所在点 for dir in dirs: # 向四个方向寻找可移动点 x,y = dir(*cur_pos) if maze[x][y] == 0: # 如果找到可移动点，则向前移动，把该点压入栈中，并把该点标记为已走过 stack.append((x,y)) maze[x][y] = 2 # 表明已经走过，不能再走，赋值为2是为了和墙壁1做个区分 print(‘next move:(%s,%s)’%(x,y)) break # 找到一个方向的可行点就跳出四个方向的探索，深度优先的方式 else: stack.pop() # 如果四个方向都没有可行点，就回退一步，重复以前的操作 print(‘回退一步’) else: print(‘没有出路’) return False
path = find_path(maze,begin,end)
#
if path:
print(‘路径为：’, path)
#### 方法二，采用队列
“””
原理：在每个方向上每次只走一步，所有的方向同步进行，最先到达的即为最短路径。广度优先策略
实现：
1，用队列存储目前可能发展的方向，将目前可能探索的点都放在队列中
2，用一个列表存储所有走过的点，也就是出队的元素，同时把他的出队编号记录到他后面直接相关的点的信息中，便于找到出路之后回溯
3，每走一步（从队尾pop一个点），存入出列节点列表，记录这个节点的出列顺序号，
4，找到这个节点的所有可行子节点，把父节点的顺序号存到每个子节点信息中，然后把这些子节点都存入队尾
5，重复上述操作，直到某一个出列节点等于出口
6，根据出列节点表回溯路径
“””
from queue import Queue
def extensive_path_find(maze,start,end): qe = Queue() # 队列：存储下一步可走的所有节点 x,y = start qe.put([x,y,-1]) maze[start[0]][start[1]] = 2 #标记已存入 rec = [] # 存储出队的节点 count = -1
while not qe.empty():
curNode = qe.get()
print('current node',curNode)
rec.append(curNode)
count += 1
if curNode[:2] == end:
print("找到出路")
return rec
for dir in dirs:
x,y = dir(*curNode[:2])
if maze[x][y] == 0:
qe.put([x,y,count]) # 让所有可行的节点入队
maze[x][y] = 2 # 同时标记这个节点为已存储
else:
print('没有找到路')
return False
def display_path(rec): lastNode = rec[-1] li = [lastNode,] p = lastNode[2] while True: li.append(rec[p]) p = rec[p][2] if p==-1: break path = [(i[0],i[1]) for i in li[-1::-1]] #倒置列表，也可以直接用reverse方法 print(‘找到最短路径：’) for i, item in enumerate(path): print(‘第%s步：%s’ % (i + 1, item)) return path
result = extensive_path_find(maze,begin,end)
if result: display_path(result) ```
- 钢条切分
设计原则
面向对象设计原则：
SOLID
开放封闭： 对扩展开发，对修改源代码封闭
替换原则： 保持原有类的方法的传入参数数量类型和返回值类型一样
依赖倒置原则：高层依赖底层的抽象接口，不能依赖细节，防止修改的影响扩散太广，细节依赖抽象
接口隔离原则：使用多个专门接口，而不使用总接口，增加灵活性
单一职责原则：一个类只干一件事
创建型模式：
- 简单产品模式
- 简单工厂模式
- 具体工厂
- 工厂方法模式
- 抽象工厂+具体工厂
- 抽象工厂模式
- 每个工厂生产一套产品手机（手机壳，cpu，os）
- 给一套系统做一点限定
- 缺点：新产品品类添加比较麻烦
- 建造者模式
- 建造和表示相分离
- 同样的建造内容可以有不同的表示
- 单例模式
- 单例相当于全局变量，比全局变量有优点：可以用不同的名字，防止污染命名空间
适配器模式：
当有的类的方法与我们高层调用接口不一致，需要专门写一个适配器进行转换
- 桥模式
- 把一个事物的两个维度相分离
- 用组合的方法可以避免重复使用代码
- 组合模式
- 比如单个图形和多个图形的组合，使他们具有一致的使用接口；适合于树形结构
- 做一个抽象类，使用递归的方法来做
- 外观模式
- 高层代码不用关心具体的细节
- 只给高层提供统一的接口
- 减少耦合
- 代理模式
- 虚拟代理
- 保护代理
- 远程代理 （远程的ip不要考虑，由代理类来封装）
- 责任链模式
- 观察者模式
- 策略模式
- 模板方法
若有收获，就点个赞吧
0 人点赞
