- 算法是对问题解决的分步描述
- 程序则是采用某种编程语言实现的算法， 同一个算法通过不同的程序员采用不同的编程语言，能产生很多程序
- 算法分析:主要就是从计算资源消耗的角度来评判和比较算法(更高效利用计算资源，或者更少占用计算资源的算法，就是好算法)
- 计算资源指标
一种是算法解决问题过程中需要的存储空间或内存(但存储空间受到问题自身数据规模的变化影响要区分哪些存储空间是问题本身描述所需，哪些是算法占用，不容易)
另一种是算法的执行时间(我们可以对程序进行实际运行测试，获得真实的运行时间) - Python中有一个time模块，可以获取计
算机系统当前时间(在算法开始前和结束后分别记录系统时间，做差即可得到运行时间)
import time start = time.time() ... end = time.time() yunxingtime = end - start
- 同一个算法，采用不同的编程语言编写， 放在不同的机器上运行，得到的运行时间 会不一样，有时候会大不一样.我们需要更好的方法来衡量算法运行时间
- 算法时间度量指标
❖ 一个算法所实施的操作数量或步骤数可作为独立于具体程序/机器的度量指标。需要一种通用的基本操作来作为运行步骤的计量单位
❖ 赋值语句是一个合适的选择
一条赋值语句同时包含了（表达式）计算和（变量）存储两个基本资源仔细观察程序设计语言特性，除了与计算资源无关的定义语句外，主要就是三种控制流语句和赋值语句，而控制流仅仅起了组织语句的作用，并不实施处理
- 问题规模影响算法执行时间
❖ 问题规模：影响算法执行时间的主要因素
❖ 在前n个整数累计求和的算法中，需要累计的整数个数合适作为问题规模的指标（前100,000个整数求和对比前1,000个整数求和，算是同一问题的更大规模）
❖ 算法分析的目标是要找出问题规模会怎么影响一个算法的执行时间
- 数量级函数 Order of Magnitude
❖ 基本操作数量函数T(n)的精确值并不是特别重要，重要的是T(n)中起决定性因素的主导部分。用动态的眼光看，就是当问题规模增大的时候，T(n)中的一些部分会盖过其它部分的贡献
❖ 数量级函数描述了T(n)中随着n增加而增加速度最快的主导部分称作“大O”表示法，记作O(f(n))，其中f(n) 表示T(n)中的主导部分
例：
1.
def sumfN(n):
theSum = 0;
for i in range(1, n + 1):
theSum = theSum + i
return theSum
赋值语句数量T(n)=1+n
当n增大时，常数1在最终结果中显得越来越无足轻重
所以可以去掉1，保留n作为主要部分，运行时间数量级就是O(n)
2.T(n)=5n2+27n+1005
当n很小时，常数1005其决定性作用
但当n越来越大，n2项就越来越重要，其它两项对结果的影响则越来越小
同样， n2项中的系数5，对于n2的增长速度来说也影响不大
所以可以在数量级中去掉27n+1005，以及系数5的部分，确定为O(n2)
- 常见的大O数量级函数
| f(n) | 名称 |
|---|---|
| 1 | 常数 |
| log(n) | 对数 |
| n | 线性 |
| n*log(n) | 线性对数 |
| n**2 | 平方 |
| n**3 | 立方 |
| 2**n | 指数 |
- 讨论下Python两种内置数据类型上各种操作的大O数量级
❖ 列表list和字典dict
❖ 这是两种重要的Python数据类型，后面会用来实现各种数据结构
❖ 通过运行试验来估计其各种操作运行时间数量级 - List列表数据类型常用操作性能
最常用的是：按索引取值和赋值（ v=a[i], a[i]= v）
由于列表的随机访问特性，这两个操作执行时间与列表大小无关，均为O(1)
另一个是列表增长，可以选择append()和 add ()“+”
lst.append(v)，执行时间是O(1)
lst= lst+[v]，执行时间是O(k)，其中k是被加的列表长度
选择哪个方法来操作列表，决定了程序的性能
4种生成前n个整数列表的方法
❖ 首先是循环连接列表（+）方式生成
def test1():
l = []
for i in range(1000):
l = l + [i]
❖ 然后是用append方法添加元素生成
def test2():
l = []
for i in range(1000):
l.append(i)
❖ 接着用列表推导式来做
def test3():
l = [i for i in range(1000)]
❖ 最后是range函数调用转成列表
def test4():
l = list(range(1000))
使用timeit模块对函数计时
❖ 创建一个Timer对象，指定需要反复运行的语句和只需要运行一次的“安装语句”
❖ 然后调用这个对象的timeit方法，其中可以指定反复运行多少次
from timeit import Timer
t1= Timer("test1()", "from __main__ import test1")
print("concat %f secondsn" % t1.timeit(number= 1000))
t2= Timer("test2()", "from __main__ import test2")
print("append %f secondsn" % t2.timeit(number= 1000))
t3= Timer("test3()", "from __main__ import test3")
print(" comprehension %f secondsn" % t3.timeit( number= 1000))
t4= Timer("test4()", "from __main__ import test4")
print("list range %f secondsn" % t4.timeit( number= 1000) )
结果
concat 2.201882 seconds
append 0.155145 seconds
comprehension 0.094716 seconds
list range 0.028956 seconds
列表连接（concat）最慢， Listrange最快，速度相差近200倍。
append也要比concat快得多
另外，我们注意到列表推导式速度是append两倍的样子
- List基本操作的大O数量级
- list.pop
❖ 我们注意到pop这个操作 pop()从列表末尾移除元素， O(1) pop(i)从列表中部移除元素， O(n) ❖ 原因在于Python所选择的实现方法 从中部移除元素的话，要把移除元素后面的元素全部向前挪位复制一遍，这个看起来有点笨拙 但这种实现方法能够保证列表按索引取值和赋值的操作很快，达到O(1) 这也算是一种对常用和不常用操作的折衷方案 ❖ 为了验证表中的大O数量级，我们把两种情况下的pop操作来实际计时对比 相对同一个大小的list，分别调用pop()和pop(0) ❖ 对不同大小的list做计时，期望的结果是: pop()的时间不随list大小变化，pop(0)的时间随着list变大而变长
- dict数据类型
字典与列表不同，根据关键码（key）找到数据项，而列表是根据位置（index） 最常用的取值get和赋值set，其性能为O(1) 另一个重要操作contains(in)是判断字典中是否存在某个关键码（key），这个性能也是O(1)
- list和dict的in操作对比
#设计一个性能试验来验证list中检索一个 值，以及dict中检索一个值的计时对比
#生成包含连续值的list和包含连续关键码key的dict，用随机数来检验操作符in的耗时
import timeit
import random
for i in range( 10000, 1000001,20000):
t = timeit.Timer("random.randrange(%d) in x" % i ,"from __main__ import random,x")
x = list(range(i))
lst__time = t.timeit( number= 1000)
x = {j:None for j in range(i)}
d__time = t. timeit( number=1000)
print("%d,%10.3f,%10.3f" % (i, lst__time, d__time))
❖ 可见字典的执行时间与规模无关，是常数
❖ 而列表的执行时间则随着列表的规模加大而线性上升
