基础算法

算法

递归

程序调用自身的编程技巧称为递归( recursion)。

阶乘

1
2
3
4
5
6
def factorial(num):
"""阶乘"""
assert num >= 0
if num in (0, 1):
return 1
return num * factorial(num - 1)

贪心法

贪心算法(又称贪婪算法)是指,在对问题求解时,总是做出在当前看来是最好的选择。也就是说,不从整体最优上加以考虑,他所做出的是在某种意义上的局部最优解。

小偷问题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
class Goods():
"""物品类"""

def __init__(self, name, price, weight):
"""初始化"""
self.name = name
self.price = price
self.weight = weight

@property
def values(self):
"""返回物品价格重量比"""
return self.price / self.weight


def thing():
"""输入物品信息"""
inputs = input().split()
return inputs[0], int(inputs[1]), int(inputs[2])


def main():
"""主函数"""
total_weight, total_nums = map(int, input().split())
goods_list = []
for _ in range(total_nums):
# 解包语法(对thing方法返回的元组进行解包操作)
goods_list.append(Goods(*thing()))
goods_list.sort(key=lambda x: x.values, reverse=True)
final_weight, final_price = 0, 0
for goods in goods_list:
if goods.weight + final_weight <= total_weight:
final_weight += goods.weight
final_price += goods.price
print(f'小偷拿了{goods.name}')
print(f'小偷偷取的物品总价为{final_price}')

"""
20 6
电脑 200 20
收⾳机 20 4
钟 175 10
花瓶 50 2
书 10 1
油画 90 9
"""

动态规划

多阶段过程转化为一系列单阶段问题,利用各阶段之间的关系,逐个求解,创立了解决这类过程优化问题的新方法——动态规划

在编程中, 我们通常使用空间换时间的方式是是实现”动态规划”

斐波那契数列

1
2
3
4
5
6
7
8
9
10
def fib(num, results={}):
"""递归-斐波那契数列"""
assert num > 0
if num in (1, 2):
return 1
try:
return results[num]
except KeyError:
results[num] = fib(num - 1) + fib(num - 2)
return results[num]

通过牺牲空间换取时间的方式,将每次得到的值存到字典中, 需要计算的时候直接去取值,代替每次都去计算, 这种方式能够极大地缩短程序运行时间, 对代码的性能提高很大。

分治

分而治之,就是把一个复杂的问题分成两个或更多的相同或相似的子问题,再把子问题分成更小的子问题……直到最后子问题可以简单的直接求解,原问题的解即子问题的解的合并。

  • 分割:递归地把当前序列平均分割成两半
  • 集成:在保持元素顺序的同时将上一步得到的子序列集成到一起(归并)

归并排序

将两个已经排序的序列合并成一个序列的操作,依赖于归并操作

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
def merge(left, right, cmp=lambda x, y: x <= y):
"""归并操作"""
result = []
while left and right:
if left[0] <= right[0]:
result.append(left.pop(0))
else:
result.append(right.pop(0))
result.extend(left)
result.extend(right)
return result

def merge_sort(items, cmp=lambda x, y: x <= y):
"""归并排序"""
if len(items) <= 1:
return items[:]
mid = len(items) >> 1
left = items[:mid]
right = items[mid:]
left = merge_sort(left, cmp)
right = merge_sort(right, cmp)
return merge(left, right, cmp)

b = [7, 4, 5, 2, 6, 9, 1]
print(merge_sort(b)) # [1, 2, 4, 5, 6, 7, 9]

快速排序

回溯

回溯法(探索与回溯法)是一种选优搜索法,又称为试探法,按选优条件向前搜索,以达到目标。但当探索到某一步时,发现原先选择并不优或达不到目标,就退回一步重新选择,这种走不通就退回再走的技术为回溯法,而满足回溯条件的某个状态的点称为“回溯点”。

骑士巡游问题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
# import os
# import time
# import sys

SIZE = 5
TOTAL = 0

def print_loc(board):
"""打印每一步的数字"""
# 清屏, 有的是os.system('clear')
# os.system('cls')
for raw in board:
for col in raw:
print(str(col).center(4), end=' ')
print()


def move(board, raw, col, step=1):
"""移动"""
if raw >= 0 and raw < SIZE and \
col >= 0 and col < SIZE and \
board[raw][col] == 0:
board[raw][col] = step
# 单步骤打印
# time.sleep(1)
# print_loc(board)
if board[raw][col] == SIZE * SIZE:
global TOTAL
TOTAL += 1
print(f'第{TOTAL}个')
print_loc(board)

move(board, raw + 2, col + 1, step + 1)
move(board, raw + 1, col + 2, step + 1)
move(board, raw - 1, col + 2, step + 1)
move(board, raw - 2, col + 1, step + 1)
move(board, raw - 2, col - 1, step + 1)
move(board, raw - 1, col - 2, step + 1)
move(board, raw + 1, col - 2, step + 1)
move(board, raw + 2, col - 1, step + 1)
board[raw][col] = 0


def main():
"""主函数"""
board = [[0] * SIZE for _ in range(SIZE)]
move(board, SIZE - 1, SIZE - 1)

深度优先算法

Python中list、dict、set的大规模查找辨析

列表数据类型其底层实现是基于顺序表实现的,其查找效率为O(n),因此在面对大数量级查找时就相当笨拙。

集合类型是会做出去重操作(其底层实现是通过__hash____eq__去判断是否去重),再根据哈希表进行查找,其查找效率理想化是O(1)

字典类型会对键进行hash运算,与集合一样也是基于哈希表,但它只对键的引用进行而没有值得引用。查找效率理想上是O(1),这在理想化的没有冲突的哈希表中才成立(一一对应的映射关系),但是实际上值是会存在重复,也就是多对一的关系,在数据结构这被称为哈希冲突或哈希碰撞,因此其查找效率是在O(1)~O(n)之间。并且因为字典类型需要对键进行hash运算,因此它叫set类型要稍慢一些。

总结下来,对于大数量级的查找:set > dict > list

代码测试:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
def differ():
d_list = []
d_set = set()
d_dict = dict()
data = randint(0, 10000000, 100000)

for d in data:
d_list.append(d)
d_set.add(d)
d_dict.setdefault(d, 1)

start = time.clock()
for item in range(100):
status = item in d_list
end = time.clock()
t1 = end - start

start = time.clock()
for item in range(100000):
status = item in d_set
end = time.clock()
t2 = end - start

start = time.clock()
for item in range(100000):
status = item in d_dict
end = time.clock()
t3 = end - start
return t1,t2,t3

print(differ())

#(1.8686458943706916, 0.00849873291109482, 0.010258474940004536)
# 在list只判断100个数据时其查找时间就远大于字典和集合的100000量级

在线排序算法动态展示

动态展示

-------------end-------------
0%