数据结构与算法(Python版)学习笔记——算法衡量指标、大O表示法、列表和字典性能对比

本文主要是介绍数据结构与算法(Python版)学习笔记——算法衡量指标、大O表示法、列表和字典性能对比，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

中国大学MOOC《数据结构与算法（Python版）》(北京大学陈斌教授) 学习笔记

文章目录

- 什么是好算法
- 算法时间的度量指标
- 数量级函数(大O)
- 不同算法，大O不同(举例)
- Python的两种数据类型(List和Dict)的性能对比
- - 对于List列表
  - 对于Dict字典

什么是好算法

我们主要从计算资源消耗的角度来评判和比较算法（即算法分析）。
更高效利用计算资源，或者更少占用计算资源的算法，就是好算法。
计算资源包括运行过程中所需的存储空间和运行时间。
故运行时间是一个衡量算法好坏的重要指标，

运行时间检测方法：time模块、timeit模块。
Jupyter notebook中，可在代码块开头加 %timeit：

%timeit
lst = []

由于绝对运行时间常常受编程语言、运行环境等影响，需要有更好的度量指标来衡量运行时间。

算法时间的度量指标

对于编程语言来说，一共有三种形式的语句：

定义语句：如定义一个变量。不占计算资源。
三种控制流语句(顺序、分支、循环)：组织作用，不实施处理。
赋值语句：包含（表达式）计算和（变量）存储。

所以赋值语句的数量可成为一个算法的合适的度量指标。

a = 100
a += 1

数量级函数(大O)

引入T(n)，表示赋值语句数量函数。

a = 100
for i in range(100):a += 1

上面代码赋值了n+1次，故T(n)=n+1。但是随着n的增大，这个1显得无足轻重，n为该问题的主导部分，称为问题规模。

数量级函数描述了该主导部分，称作“大O”表示法。

记作： $O (f (n))$
其中 $f (n)$ 为主导部分。在上例中，即为 $O (n)$ 。

举个栗子： $T(n)=5n^2+27n+1005$ ，这里n非常大时平方项占主导，故该例为： $O(n^2)$ 。

常见数量级函数（按性能大小排列）：

f(n)	名称
1	常数
log(n)	对数
n	线性
$n l o g (n)$	对数线性
$n^2$	平方
$n^3$	立方
$2^n$	指数

不同算法，大O不同(举例)

举例：变位词判断，如判断 “python” 和 “typhon” 是否为变位词。
以下四种算法：

逐字检查：二重循环， $O(n^2)$
排序比较：各自按字符编码排序，看是否一样， $O (n l o g (n))$
暴力法：穷尽所有可能组合，再判断两个词是否在组合集内， $O (n!)$ ，最不可取
计数比较：统计两个词中每个字母出现的次数，看是否相同， $O (n)$ 、

在方法4中，总操作次数T(n)=2n+26，其数量级为O(n)。
算法依赖于两个长度为26的计数器列表，来保存字符计数，相比前3个算法需要更多的存储空间。
因此这个算法以牺牲存储空间来换取运行时间，达到了运行速度的提升。
我们常需在时间空间之间做取舍。

Python的两种数据类型(List和Dict)的性能对比

Python的常用数据类型List列表和Dict字典在使用性能上是存在差异的，体现在其各自的操作(函数)的数量级函数上。
两种数据类型的常用操作：

类型	list	dict
索引	自然数i	不可变类型值key
添加	append、extend、insert	b[k]=v
删除	pop、remove*	pop
更新	a[i]=v	b[k]=v
正查	a[i]、a[i:j]	b[k]、copy
反查	index(v)、count(v)	无
其它	reverse、sort	has_key、update

对于List列表

按索引取值和赋值（v = a[i], a[i] = v）： $O (1)$
列表增长 append(v)： $O (1)$
列表增长 lst = lst + [v]： $O (n + k)$
k为增加列表的长度，两种列表增长的方式性能差异很大。
slice切片 lst[1:10]： $O (k)$
pop() ： $O (1)$
pop(i) ： $O (n)$
两种删除方式性能有差异。
reverse() ： $O (n)$
sort() ： $O (n l o g (n))$
包含判断in v in lst： $O (n)$