Python算法教程学习笔记＿第二章
标签：algorithms, 算法, 笔记2.2.1渐进记号
用来表示算法的渐进运行时间的记号是用定义域为自然数集N={0,1,2，…}的函数来定义的这些记号便于用来表示最坏情况运行时间T(n)，因为T(n)一般定义于整数的输入规模上。有以下5种：
- Θ记号 渐进确界
- ο记号 渐进上界
- Ω记号 渐进下界
- º记号 非渐进紧确的上界
- ω记号 非渐进紧确的下界
2.2.2算法的渐进运行时间（时间复杂度）
按数量级递增排列，常见的时间复杂度有：
| 名称 | 时间复杂度 | 相关示例及说明 |
|---|---|---|
| 常数阶 | Θ(1) | 哈希表的查询与遍历 |
| 对数阶 | Θ(log n) | 二分搜索 |
| 线性阶 | Θ(n) | 列表的遍历 |
| 线性对数阶 | Θ(n log n) | 任意值序列的最优化排序 |
| 平方阶 | Θ(n2) | n 个对象相互比较 |
| 立方阶 | Θ(n3) | Floyd-Warshall |
| 多项式级 | O(nk) | 基于 n 的 k 层嵌套循环(其中K为整数)，且必须满足常数k>0 |
| 指数阶 | Ω(kn) | 每 n 项产生一个子集(其中k=2)，且必须满足k>1 |
| 阶乘级 | Θ(n!) | 对 n 个只看进行全排列操作 |
2.2.5 实证式算法评估
－ 提示１：只要有可能，就不必去担心 － 提示２：请用timeit模块来进行计时 － 提示３：请使用profiler找出瓶颈 － 提示４：绘制出结果 － 提示５：在根据计时比对结果做出判断时要小心仔细 － 提示６：通过相关实验对渐近时间做出判断的时候要小心仔细
In [1]: import timeit
In [2]: timeit.timeit("x=2+2")
Out[2]: 0.00950163701782003
In [3]: timeit.timeit("x=sum(range(10))")
Out[3]: 0.28970501499134116
In [4]: import cProfile
In [5]: def sumtest():
...: x=sum(range(100))
...: print(x)
...:
In [6]: cProfile.run('sumtest()')
4950
6 function calls in 0.000 seconds
Ordered by: standard name
ncalls tottime percall cumtime percall filename:lineno(function)
1 0.000 0.000 0.000 0.000 <ipython-input-6-6bb9573acd87>:1(sumtest)
1 0.000 0.000 0.000 0.000 <string>:1(<module>)
1 0.000 0.000 0.000 0.000 {built-in method builtins.exec}
1 0.000 0.000 0.000 0.000 {built-in method builtins.print}
1 0.000 0.000 0.000 0.000 {built-in method builtins.sum}
1 0.000 0.000 0.000 0.000 {method 'disable' of '_lsprof.Profiler' objects}
2.3图与树的实现
图结构(graph) 算法学中最强大框架之一。在许多情况下，我们都可以把一个问题抽象为一个图，如果能抽象为一个图的话，那么该问题至少已经接近解决方案了。如果问题实例可以用树(tree)诠释的话，那么我们基本上已经拥有了一个真正有效的的解决方案了。 下面是一些关于图的术语：
- 图 G = (V,E) 通常由一组节点 V 及节点间的边 E 共同组成。如果这些边有方向，就称其为有向图。
- 节点之间通过边来实现彼此相连的。而这些边其实就是节点 v 与其邻居之间的关系。
- G = (V，E) 的子图结构将由 V 和 E 的子集共同组成。在 G 中，每一条路径(path)是一个子图结构，它们本质上都是一些由多个节点串联而成的边线序列。环路(cycle)的定义与路径基本相同，只不过它的最后一条边所连接的末节点同是是它的首节点。
- 如果我们将图 G 中的边与某种权值联系在一起，G 就成了一种加权图。在加权图中，一条路径或环路的长度等于各边上的权值之和，对非加权图来说，就直接等于该图的边数。
- 森林 (forest) 可以被认为是一个无环路图，而这样的连通图就是一棵树。换言之，森林就是由一棵或多棵树构成的。
2.3.1邻接列表及其类似结构
对于图结构的实现来说，邻接列表是最直观的方式之一。 接下来，我们就要用数据结构来表示图。
a, b, c, d, e, f, g, h = range(8)
N = [
{b, c, d, e, f}, # a
{c, e}, # b
{d}, # c
{e}, # d
{f}, # e
{c, g, h}, # f
{f, h}, # g
{f, g} # h
]
Written on 2019-01-09