《算法图解》学习1

背景

有些专业基础知识,无论怎样是绕不过的。主要分为操作系统、网络、数据结构和算法、编程语言及工程方法。
有些非专业知识,也是需要持续学习的,比如对世界的认识,对商业的认识,对自我的认识。
在合适的心情下,选择这些类别学习,持续学习,一定可以自我增值。

对数是幂运算的逆运算
幂运算:10 个 2 相乘,结果是多少?210 = ? ,答案 1024
对数运算:多少个 2 相乘,等于 1024?log21024 = ?答案 10

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
# 二分查找
def binary_search(search_list, item):
low = 0
high = len(search_list) - 1
# print low, high

while low <= high:
mid = (low + high) / 2
guess = search_list[mid]
# print low, high, mid, guess
if guess == item:
return mid
if guess > item:
high = mid -1
else:
low = mid + 1
return None

my_list = [1,3,5,7,9]
print binary_search(my_list, 1)
print binary_search(my_list, -1)


# print binary_search(my_list, -1)
1
2
0
None

1.2 练习

  1. 有 128 个名字有序列表,使用二分查找其中一个名字,最多需要多少步?
    log128 = 7
  2. 列表长度翻倍,最多需要多少步?
    log256 = 8

算法是一组完成任务的指令,任何代码片段都可以视为算法。
大 O 表示法表示算法的速度有多快。
大 O 表示法运行时间随着列表增长如何增长。
大 O 表示法指出最糟糕情况下的运行时间。
从快到慢常用的 5 种大 O 运算时间

  1. O(log n) 对数时间,二分查找
  2. O(n) 线性时间,简单查找
  3. O(n * log n) 快速排序
  4. O(n^2) 选择排序
  5. O(n!)旅行商问题

算法的速度并非指时间,而是操作数的增速
算法的速度是指随着输入的增加,其运算时间将以怎样的速度增加。

1.3 练习
用大 O 表示下列情况运行时间

  1. 电话簿中根据名字查找电话号码 O(log n)
  2. 电话簿中根据电话号码找人 O(n)
  3. 阅读电话簿中每个人的电话号码 O(n)
  4. 阅读电话簿中以 A 打头的人的电话号码 电话簿以名排序,要阅读以 A 姓开头的电话号码。 O(n * log n) ?
  • 链表和数组
    数组 链表
    读取 O(1) O(n)
    插入 O(n) O(1)
    删除 O(n) O(1)
    数组适合随机访问,链表适合增删改。

练习 插入多,读取少,使用链表。
点餐程序,队尾加菜,队首取菜单做菜。使用链表,不存在随机读。在链表头删除元素,在链表尾增加元素都只操作 1 次。
Facebook 登陆,后台账号查找使用什么来存储用户名? 数组,因为要求随机访问。
数组中插入数据有何缺点?只能插入再队尾,要想快速查找到用户还需排序。
链表数组,长度为 26 的数组,每个数组元素指向一个链表。这种混合数据结构再查找和插入和单纯的数组、链表对比快慢?二分查找
数组 链表 链表数组(n 个数组中存放长度为 m 的链表)
查找 O(1) O(n) O((log n) _ n )
插入 O(n) O(1) O(log n _ 1)
链表数组,查找比数组慢,比链表快;插入比数组快,比链表慢。

  • 选择排序和快速排序
    选择排序,每次遍历列表,将最大的添加到新列表,需要操作次数为 n _ (1/2 _ n)。大 O 记法省略掉常数,故记作 O(n _ n). 第一个 n 表示对每个元素都要加入新列表,1/2 _ n 表示筛选出最大元素平均需要 1/2 _ n 次,即第一次 n,第二次 n-1,第 n 次 1 ,总次数 n + n-1 + n-2…+ 1=(1+n)_ (1/2 * n).
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
# 选择排序
def findSmallest(arr):
smallest = arr[0]
smallest_index = 0
for i in range(1, len(arr)):
if arr[i] < smallest:
smallest = arr[i]
smallest_index = i
return smallest_index

print findSmallest([5,3,1])

def selectionSort(arr):
newArr = []
for i in range(len(arr)):
smallest = findSmallest(arr)
newArr.append(arr.pop(smallest))
return newArr

print selectionSort([8,2,1,4,2,7,10])
1
2
2
[1, 2, 2, 4, 7, 8, 10]

递归

递归只是让解决方案更清晰,并没有性能上的优势。
如果使用循环,程序性能可能会更高;如果使用递归,程序可能更容易理解。如何选择要看什么对你来说更重要。
每个递归函数都有两部分:基线条件和递归条件。递归条件指的是函数调用自己,基线条件则指函数不再调用自己。
栈只有两种方法,从栈顶压入,从栈顶弹出。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
# test
def countdown(i):
print i
if i <= 1:
return
else:
countdown(i-1)
# print countdown(5)
# 阶乘的递归函数
def fact(x):
if x == 1:
return 1
else:
return x * fact(x-1)

print fact(7)
1
5040

快速排序

快速排序使用分而治之的策略
工作原理

  1. 找到简单的基线条件;
  2. 确定如何缩小问题的规模,使其符合基线条件。

快速排序调用栈深度和选择基准值有关,最差情况基准值选择到最小值,调用栈深度为数组长度 n。最好情况基准值取到平均值,调用栈深度为 logn。
每一层调用栈处理的数据都是 n,所以每一层调用栈处理次数为 n。
算法的性能在 O(n _ n) ~ O(n _ log n) 之间。
选择排序行性能总是 O(n * n)

练习
使用大 O 表示法,下面各种操作都需要多长时间?

  1. 打印数组中每个元素 n
  2. 将数组中每个元素的值都乘以 2 n
  3. 只将数组第一个元素值乘以 2 1
  4. 根据数组元素创建乘法表 n * n
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
# 数组相加
def sum_arr(arr):
total = 0
for x in arr:
total = total + x
return total
print sum_arr([1,2,5,8])

def sum_arr2(arr):
total = 0
if len(arr) == 0:
return None
elif len(arr) == 1:
total = arr[0]
else:
total = sum_arr2(arr[1:]) + arr[0]

return total

print sum_arr2([1,2,5,8])
1
2
16
16
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
# 快速排序
def fast_sort(arr):
new_arr = []
if len(arr) < 2:
return arr
elif len(arr) == 2:
if arr[0] > arr[1]:
new_arr.append(arr[1])
new_arr.append(arr[0])
else:
new_arr = arr
return new_arr
else:
larger = []
smaller = []
pivot = arr[0]
for i in arr:
if i < pivot:
smaller.append(i)
elif i > pivot:
larger.append(i)
smaller_sorted = fast_sort(smaller)
larger_sorted = fast_sort(larger)
return smaller_sorted + [pivot] + larger_sorted

print(fast_sort([2,1,8,7,998,'1']))

# 快熟排序 教程代码
def quicksort(arr):
if len(arr) < 2:
return arr
else:
pivot = arr[0]
less = [i for i in arr[1:] if i <= pivot]
greater = [i for i in arr[1:] if i > pivot]
return quicksort(less) + [pivot] + quicksort(greater)
print quicksort([1,5,3,7,3,8,12])
1
2
[1, 2, 7, 8, 998, '1']
[1, 3, 3, 5, 7, 8, 12]

散列表

散列函数是这样的函数,无论你给它什么数据,它都还你一个数字。
散列函数将输入映射到数字,满足两个要求:相同输入返回相同输出,一致性;不同输入返回不同输出。
python 中字典就是散列表
散列表适用于:模拟映射关系,防止重复,缓存数据
散列表被用于大海捞针式的查找。
散列表(平均) 散列表(最坏) 数组 链表
查找 O(1) O(n) O(1) O(n)
插入 O(1) O(n) O(n) O(1)
删除 O(1) O(n) O(n) O(1)

使用散列表要避开糟糕情况,方法 1:较低的填装因子(散列表元素个数/ 位置总数),2 良好的散列函数。
填装比例操作 70%,数组长度增加 1 倍。

练习
5.5
c, 每一个字母开头的姓名都有
5.6
b,电池尺寸只有 4 种,可根据尺寸名字长度散列。
5.7
d,每本书作者不超过 10 个,可以用模 10 值散列。

广度优先搜索

图用于模拟不同的东西如何连接。
解决最短路径问题的算法被称为广度优先搜索。能回答 1:从节点 A 触发,有前往 B 的路径吗?2:从节点 A 触发,哪条路径最短?

广度优先搜索运行时间为 O(人数+边数),V 为顶点,E 为边,通常记作 O(V+E)
可以用拓扑排序创建一个有序的任务列表

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
from collections import deque
graph = {'you': ['alice','bob','claire'],
'bob': ['anuj','peggy'],
'alice': ['peggy'],
'claire': ['thom','jonny'],
'anuj': [],
'peggy': [],
'thom': [],
'jonny': []}

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

def find_seller(graph):
search_queue = deque()
search_queue.extend(graph['you'])
searched = []
while search_queue:
person = search_queue.popleft()
if person not in searched:
if person_is_seller(person):
print person + ' is a mango seller'
return True
else:
search_queue.extend(graph[person])
searched.append(person)
return False

print find_seller(graph)
1
2
thom is a mango seller
True

狄克斯特拉算法(Dijkstra)

加权图,计算加权图种的最短路径
图中的环导致狄克斯特拉算法失效,有负权边也失效。

  1. 找出最便宜的节点
  2. 更新该节点的邻居的开销
  3. 重复这个过程,直到对图种每个节点都这么做了
  4. 计算最终路径
    算法适用于有向无环图
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
graph = {
'start': {'a': 6, 'b': 2},
'a': {'fin': 1},
'b': {'a': 3, 'fin': 5},
'fin':{}
}
infinity = float('inf')
costs = {
'a': 6,
'b': 2,
'fin': infinity
}
parents = {
'a': 'start',
'b': 'start',
'fin': None
}
processed = []

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

def dijkstra(costs):
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)


print find_lowest_cost_node(costs)
dijkstra(costs)
print costs, parents, processed
1
2
b
{'a': 5, 'b': 2, 'fin': 6} {'a': 'b', 'b': 'start', 'fin': 'a'} ['b', 'a', 'fin']
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
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
# 练习7.1
class Dijkstra():
def __init__(self,graph_info):
self.graph = graph_info['graph']
self.costs = graph_info['costs']
self.parents = graph_info['parents']
self.processed = []

def find_lowest_cost_node(self):
lowest_cost = float('inf')
lowest_cost_node = None
print self.costs
for node in self.costs:
cost = self.costs[node]
if cost < lowest_cost and node not in self.processed:
lowest_cost = cost
lowest_cost_node = node
self.processed.append(node)
print lowest_cost_node
return lowest_cost_node

def run(self):
node = find_lowest_cost_node(self)
print node
while node is not None:
cost = self.costs[node]
neighbors = self.graph[node]
for n in neighbors.keys():
new_cost = cost + neighbors[n]
if self.costs[n] > new_cost:
self.costs[n] = new_cost
self.parents[n] = node
self.processed.append(node)
print self.processed
node = find_lowest_cost_node(self)

def get_result(self):
print self.costs, self.parents, self.processed

graph_1 = {
'graph': {
'start': {'a': 6, 'b': 2},
'a': {'fin': 1},
'b': {'a': 3, 'fin': 5},
'fin':{}
},
'costs': {
'a': 6,
'b': 2,
'fin': float('inf')
},
'parents': {
'a': 'start',
'b': 'start',
'fin': None
}
}
a = Dijkstra(graph_1)
a.find_lowest_cost_node()
a.find_lowest_cost_node()
a.find_lowest_cost_node()
a.find_lowest_cost_node()
#a.run()
# a.get_result()
1
2
3
4
5
6
7
8
{'a': 6, 'b': 2, 'fin': inf}
b
{'a': 6, 'b': 2, 'fin': inf}
None
{'a': 6, 'b': 2, 'fin': inf}
None
{'a': 6, 'b': 2, 'fin': inf}
None
1
2
3
4
5
6
7
graph_1 = {
'graph': {
'start': {'a': 6, 'b': 2},
'a': {'fin': 1},
'b': {'a': 3, 'fin': 5},
'fin':{}
}}

总结

看了 1-7 章,对算法表示法、复杂度计算有一定的认识。学会简单查找、二分查找、简单排序、快速排序、广度优先搜索、狄克斯特拉算法。
加深对递归的理解,特别是用递归做出数组内元素求和,感觉很不错。后面摸索编出快速排序。递归中的循环,在调用栈中展开实现的。
对数据结构 数组、链表、散列表有更深的认识,数组读快,链表编辑快,散列表结合两者。
狄克斯特拉算法的类还没调试正确,后续继续调试。
学习分而治之的思想,每次都减少输入参数数量。
后面几章贪心算法、背包问题,看着有些吃力,多看两遍试试。