程序设计不仅仅是软件架构以及面向对象设计方面的事情,算法设计问题也是它要解决的一个方面。

算法指的是一个执行过程,包含了能够解决某个特定问题的有限步骤集。

python中的list其实是一个数组,append操作通常会采用一种被称为动态数组或者向量的特定解决方案。

渐进记法

O(g)表示,存在自然数n0和c,对于所有的n>=n0都有f(n)<=cg(n),也就是说O(g)表示的是一个函数集,它的增长速度不会快于g,表示渐进上界

Ω(g)表示,存在自然数n0和c,对于所有的n>=n0都有f(n)>=cg(n),也就是说Ω(g)表示的函数集,它的增长速度都快于g,表示渐进下界

Θ(g)表示,存在自然数n0和c,对于所有的n>=n0都有,c1g(n)<=f(n)<=c2g(n),也就是说f和g有着相同程度的渐进式增长

时间复杂度 名称 说明
Θ(1) 常数级 哈希表,表示这一集合函数的增长速度是常数级别
Θ(lg n) 对数级 二分搜索
Θ(n) 线性级 列表遍历
Θ(nlg n) 线性对数级 序列的最优化排序
Θ(n2) 平方级 n个对象互相比较
Θ(n3) 立方级 不知道
O(nk) 多项式级 基于n的k层循环
Ω(kn) 指数级
Θ(n!) 阶乘级 n个值全排列

Θ(f) + Θ(g) = Θ(f+g)

Θ(g) * Θ(g) = Θ(g)

代码块的复杂度由其先后执行的语句累加而成,而嵌套循环的复杂度则在此基础上成倍增长。

O(n)这就同时概括了最好的和最坏的情况。

当没有把握的时候,就用蛮力试试

使用Python来分析性能

打印出程序中各个函数的计时结果

1
2
import cProfile
cProfile.run('main()')

图与树的实现

如果我们的问题可以诠释成图问题的话,那么该问题至少已经接近解决方案了,而我们的问题如果可以用树结构来诠释的话,那么问题已经拥有一个真正有效的解决方案了。

散列常用于字典类型的实现,dict就是散列表,同样,集合类型set也是这种机制实现的,用散列值对其进行访问的平均时间是Θ(1)

邻接列表

邻接集的表示法,同样的还有邻接表的表示法,set是hash实现的,所以在成员检测中会快一点,但是邻接表在成员遍历上会更加快一点

1
2
3
4
5
6
7
8
9
10
11
12
# 其实是一个有向图
a, b, c, d, e, f, g, h = range(8)
N = [
true{b, c, d, e, f},
true{c, e},
true{d},
true{e},
true{f},
true{c, g, h},
true{f, h},
true{f, g}
]

另外实现一个加权邻接字典,可以使用字典类型来代替set或者list

1
2
3
4
5
6
7
8
9
10
11
a, b, c, d, e, f, g, h = range(8)
N = [
true{b:2, c:3, d:4, e:5, f:9},
true{c:2, e:3},
true{d:8},
true{e:7},
true{f:2},
true{c:2, g:2, h:2},
true{f:1, h:6},
true{f:9, g8}
]

邻接矩阵

将每个节点可能的邻居位置排成一行,用某种值比如True或者False来表示相关节点是否为当前节点的邻居。

1
2
a, b, c, d, e, f, g, h = range(8)
N = [[0,1,1,1,1,1,0,0], ...]

通过向现有表示法中加入双向边元素的方式来实现一个无向图,也就是无向图的邻接矩阵应该是一个对称矩阵。

可以使用float('inf')来获取一个无穷大的值

一些有意思的代码:

1
2
sum(1 for w in W[a] if w < inf) - 1
N = [[0] * 10 for i in range(10)]

树的实现

可以将树表示成一个二维列表,但是这只是表示了叶子节点而已,T = [["a", "b"], ["c"], ["d", ["e", "f"]]],每个列表表示的都是内部节点拥有的包含其所有子节点的列表。

二叉树可以这样表示:

1
2
3
4
5
6
7
class Tree:
def __init__(self, left, right):
truetrue self.left = left
truetruetruetrueself.right = right
# 其实就是用到了递归吧
t = Tree(Tree("a", "b"), Tree("c", "d"))
t.right.left # c

可以使用None来表示不存在的子节点

还有一种树的实现方式是用 先子节点,然后兄弟节点 的表示法,这里的各个节点用到的是一个子节点的兄弟节点链表,并且这些兄弟节点又各自引用了属于它们自己的那个兄弟节点链表。

1
2
3
4
5
class Tree:
def __init__(self, kids, next=None):
truetrue self.kids = self.val = kids
truetruetruetrueself.next = next
t = Tree(Tree("a", Tree("b", Tree("c", Tree("d")))))

可以分析一下得,一个根节点下面a是其子节点,然后b是a的兄弟节点,c是b的兄弟节点,d是c的兄弟节点。也就是说,根节点下面有a,b,c,d四个子节点。

Bunch模式

可以用命令行参数的形式来创建相关对象,并且设置属性

1
2
3
4
5
6
7
8
9
10
11
class Bunch(dict):
def __init__(self, *args, **kwargs):
truetrue super(Bunch, self).__init__(*args, **kwargs)
truetruetruetrue# __dict__里面存的就是属性值,这样就可以使用对象的用法了
truetruetruetrue# 使用dict集成,这样可以使用字典的方式,比如关键值属性值的遍历,查询属性是否存在
truetruetruetrueself.__dict__ = self
T = Bunch
t = T(left=T(left="a", right="b"), right=T(left="c"))
t.left # {'rigth': 'b', 'left': 'a'}
t.left.right # 'b'
t['left']['right'] # 'b'

一些概念

子问题图:绝大部分问题应该都可以被分成若干个子问题,这些子问题在结构上往往都非常相似,因此,这些结构可以被看作相关子问题图中的节点,而它们之间的依赖关系(也就是这些子问题之间的依存关系)就成为该图的边。分治法和动态规划就出自这些分析。

在一般情况下,程序越重要,就应当越去研究某些库或者包的细节,看看背后都隐藏了什么。

  • 当性能成为重点问题时,要着重于实际分析而不是直觉,一些性能瓶颈,可能隐藏于不是自己所认为的地方
  • 正确性至关重要的时候,最好的方法是不同的实现体对答案进行多次计算

即使相关操作已经足够好了,但也有可能会由一个线性级操作变成一个平方级操作。

性能问题

成员查询在list中是线性级的,在set中是常数级的,如果每次往集合中添加新值,然后检查值是否已经被添加,那么用list是平方级的,set就是线性级的。

使用双向队列优于在某个list首端插入对象

字符串的合并,使用''.join(list)会比较好

浮点运算

  • 不要对浮点数进行等值比较,可以检查它们是否接近于相等
1
2
def almost_equal(x, y, places=7):
return round(abs(x-y), places) == 0
  • 如果需要精确的十进制浮点数表示法,使用decimal模块,或者对一定数位的十进制数进行精确计算
1
2
from decimal import *
sum(Decimal("0.1") for i in range(10)) == Decimal("1.0")

如果将两个相近等值的子表达式相减,通常会丢失大量的有效数字。

参考自:Python 算法教程Magnus Lie Hetland