数据结构之算法分析
算法分析
什么是算法分析
问题：如何对比两个程序？看起来写法不同，但解决同一个问题的程序，哪个“更好”？
程序和算法的区别
算法是对问题解决的分步描述
程序则是采用某种编程语言实现的算法，同一个算法通过不同的程序员采用不同的编程语言，能产生很多程序。
累计求和问题
我们来写一个累加求和的程序，就是从1到n累加输出和。
示例1：
def sum_num(n):
sum = 0
for i in range(1,n+1):
sum += i
return sum
print(sum_num(10))
示例2：
def foo(tom):
fred = 0
for bill in range(1,tom+1):
barney = bill
fred = fred + barney
return fred
print(foo(10))
看完示例1再看示例2，是不会死感觉怪怪的，但是实际上两个程序是相同的，示例2的失败之处在于变量命名词不达意，而且包含了无用的垃圾代码。
算法分析的概念
比较程序的“好坏”，有更多因素，比如代码风格，可读性等等。我们主要感兴趣的是算法本身特性。
算法分析主要就是从计算资源消耗的角度来评判和比较算法。
更高效利用计算资源，或者更少占用计算资源的算法，就是好算法。从这个角度，上面的两段程序实际上是基本相同，他们都采用了一样的算法来解决累加求和问题。
计算资源指标
何为计算资源
一种是算法结局问题过程中需要存储空间和内存，但存储空间受到问题自身数据规模的变化影响，要区分哪些存储空间是问题本身描述所需，哪些是算法占用，不容易区分。
另一种是算法的执行时间，我们可以对程序进行实际运行测试，获得真是的运行时间。
迭代累加
我们可以利用Python中的time模块，对程序运行时间进行统计。
import time
def sum_num(n):
start = time.time() # 程序开始时间
sum = 0
for i in range(1,n+1):
sum += i
end = time.time() # 结束时间
return sum,end - start
for i in range(5):
print("sum is %d required %10.7f seconds" % sum_num(10000))
输出结果：
sum is 50005000 required 0.0009971 seconds
sum is 50005000 required 0.0010009 seconds
sum is 50005000 required 0.0000000 seconds
sum is 50005000 required 0.0009973 seconds
sum is 50005000 required 0.0000000 seconds
我们看到1到10000累加，每次运行大约需要0.0009s
那么累加到100000呢？以及累加到1000000呢？
# 累加到100000
sum is 5000050000 required 0.0049376 seconds
sum is 5000050000 required 0.0049913 seconds
sum is 5000050000 required 0.0050364 seconds
sum is 5000050000 required 0.0049746 seconds
sum is 5000050000 required 0.0049860 seconds
# 累加到1000000
sum is 500000500000 required 0.0538669 seconds
sum is 500000500000 required 0.0499117 seconds
sum is 500000500000 required 0.0588810 seconds
sum is 500000500000 required 0.0499055 seconds
sum is 500000500000 required 0.0498645 seconds
我们不难发现运行时间以10的倍数增加。
无迭代累加
我们可以利用求和公式，对从1到n的数进行累加。
def sum_num(n):
start = time.time()
sum = (n * (n + 1)) / 2
end = time.time()
reutrn sum, end-start
采用上述同样的方法进行检测运行时间。
分别对10000,100000,1000000,10000000,100000000进行累加检测运行时间
sum is 50005000 required 0.0000000 seconds
sum is 500000500000 required 0.0000000 seconds
sum is 50000005000000 required 0.0000000 seconds
sum is 5000000050000000 required 0.0000000 seconds
我们发现这种无迭代的算法，运行时间几乎与需要累加的数目无关，而使用迭代，运行时间与累加对象n的大小是倍数增长关系。
运行时间检测的分析
我们先看第一种迭代算法，包含了一个循环，可能会执行更多语句，这个循环运行次数跟累加n是有关系的，n增加，循环次数也增加。
但是关于运行时间的实际检测，是有点问题的，同一算法，采用不同的编程语言编写，放在不同的机器上运行，得到的运行时间会不一样，有时候会大不一样。比如把非迭代算法放在老舅机器上跑，甚至可能慢过新机器上的迭代算法。所以我们需要更好的方法来很亮算法运行时间，这个指标与具体的机器，程序运行时段都无关。
大O表示法
算法时间度量指标
一个算法所实施的操作数量或步骤可作为独立于具体程序/机器的度量指标。
哪种操作跟算法的具体实现无关？
这是我们需要一种通用的基本操作来作为运行步骤的计量单位。
赋值语句是一个不错的选择，一条赋值语句同时包含了（表达式）计算和（变量）存储两个基本资源，仔细观察程序设计语言特性，除了与计算资源无关的定义语句外，主要就是三种控制流语句和赋值语句，而控制流仅仅气到了组织语句的作用，并不实施处理。
赋值语句执行次数
我们继续上面的累加，分析sum的赋值语句执行次数。
第一次初始化赋值为0，接着开始循环，每循环一次就赋值一次，那么赋值语句数量T = n +1。
问题规模影响算法执行时间
问题规模：影响算法执行时间的主要因素
在前n个整数累加求和的算法中，需要累计的整数个数合适作为问题规模的指标。前100000个整数求和对比前1000个整数求和，算是同一问题的更大规模。
算法分析的目标是要找出问题规模会怎么影响一个算法的执行时间。
数量级函数Order of Magnitude
基本操作数量函数T(n)的精确值并不是特别重要，重要的是T(n)中起决定性因素的主导部分。用动态的眼光看，就是当问题规模增大的时候，T(n)中的一些部分会盖过其他部分的贡献。
数量级函数描述了T(n)中随着n增加速度最快的主导部分，称作“大O”表示法，记作O(f(n)),其中f(n)表示了T(n)中主导部分。
确定运行时间数量级大O的方法
例1：T(n) = 1 + n
当n增大时，常数1在最终结果中显得越来越无足轻重，所以可以去掉1，保留n作为主要部分，运行时间数量级就是O(n)
例2：T(n) = 5n² +27n=1005
当n很小的时候，常数1005起决定性作用，但当n越来越大，n²项就越来越重要，其他两项对结果的影响也就越来越小，同样，n² 项中的系数5，对于n² 的增长速度来说也影响不大，所以 可以在数量级中去掉27n+1005,以及系数5，最终确定为O(n²)
影响算法运行时间的其他因素
有时候决定运行时间的不仅是问题规模，某些具体数据也会影响算法运行时间，分为最好，最差和平均情况体现了算法的主流性能，对算法的分析要看主流，而不被某几个特定的运行状态所迷惑。
常见的大O数量级函数
通常当n较小时，难以确定其数量级，当n增长到较大时，容易看出其变化量级。
f(n) 名称
1 常数
log(n) 对数
n 线性
n*log(n) 对数线性
n² 平方
n³ 立方
2ⁿ 指数
“变位词”判断问题
问题描述
所谓“变位词”,是指两个词之间存在组成字母的重新排列关系。如heart和earth,python和typhon。
为了简单起见，假设参与判断的两个词仅由小写字母构成，而且长度相等。
逐字检查
将词1中的字符逐个到词2中检查是否存在，若存在就“打勾”标记（防止重复检查），如果每个字符都能找到，则两个词是变位词，只要有一个字符找不到，就不是变位词。
实现“打勾”标记：可以将词2对应的字符设为None,由于字符串是不可变类型，需要先复制到列表中。
def foo(s1, s2):
l = list(s2) # 由于字符串是不可变类型，将s2转换为列表
p1 = 0
ok = True
while p1 < len(s1) and ok: # 循环编译s1的每个字符
p2 = 0
found = False
while p2 < len(l) and not found:
if s1[p1] == l[p2]: # 对s2逐个对比
found = True
else:
p2 += 1
if found:
l[p2] = None # 找到进行打勾
else:
ok = False # 未找到，失败
p1 += 1
return ok
上面的代码中，词中包含的字符个数为n,主要部分在于两重循环，外层循环遍历s1每个字符，将内层循环执行n次，而内层循环在s2中查找字符，每个字符的对比次数，分别是1,2…n中的一个，而且各不相同。所以总执行次数是1+2+3+…+n。这个式子是不是很熟悉，是不是又回到数字累加的问题上了？那么我们就可以知道其数量级为O(n²)。
1+2+…+n=n(n+1)/2=1/2n²+1/2n–>O(n²)
排序比较
将两个字符串都按照字母的顺序排好序，再逐个字符对比是否相同，如果相同则是变位词，有任何不同就不是变位词。
def foo(s1,s2):
l1 = list(s1)
l2 = list(s2) # 转换为列表
l1.sort()
l2.sort() # 排序
p = 0
result = True
while p < len(s1) and result: # 这边直接判断两个列表是否相等不是更好么 哈哈
if l1[p] == l2[p]:
p += 1
else:
result = False
return result
粗略的看上去，这个算法只有一个循环，最多执行n次，数量级也就是O(n)。
但是循环前面的两个sort并不是无代价的，所以本算法时间主导的步骤是排序步骤。
暴力破解
暴力破解的解题思路就是穷尽所有的可能组合，将s1中出现的字符进行全排列，再查看s2是否出现在全排列列表中。
这里最大的困难是产生s1所有字符的全排列，根据组合数学的结论，如果n个字符进行全排列，其所有可能的字符串个数为n!。
我们已知n!的增长速度甚至超过2ⁿ。例如对于20个字符长的词来说，将产生20！=3432902008156640000个候选词，如果一微秒处理一个候选词的话，需要近8万年时间来昨晚所有匹配。所以这个方法坤怕不是个好算法。
计数比较
对于两个词中每隔字母出现的次数，如果26个字母出现的次数都相同的话，这两个字符串一定是变位词。
我们可以为每个词设置一个26位的计数器，选检查每个词，在计数器中设定好每隔字母出现的次数，计数完成后，进入比较阶段，看两个字符串的计数器是否相同，如果相同则输出是变位词的结论。
def foo(s1,s2):
l1 = [0] * 26
l2 = [0] * 26
# 分别计数
for i in range(len(s1)):
p = ord(s1[i]) - ord("a")
l1[p] += 1
for i in range(len(s2)):
p = ord(s2[i]) - ord("a")
l2[p] += 1
j = 0
result = True
# 进行比较
while j < 26 and result:
if l1[j] == l2[j]:
j += 1
else:
result = False
return result
这个算法中有三个循环迭代，但是不像逐字检测那样存在嵌套循环，这个算法中前两个循环用于对字符串进行计数，操作次数等于字符串长度n,第三个循环用于计数器比较，操作次数总共为26次。
所以总操作次数为T(n) = 2n +26,那么其数量级为O(n)。
由此可见这是一个线性数量级的算法，是4个变位词判断算法中性能最优的。
但是需要注意的是，此算法依赖于两个长度为26的极速器列表，来保存字符计数，这相对前三个算法需要更多的存储空间。如果考虑由大字符集构成的词（如中文具有上万个不同字符），这需要更多存储空间。
牺牲存储空间来换取运行时间，或者相反，这种在时间空间之间的取舍和权衡，在选择问题解法的过程中经常出现。
Python数据类型的性能比较
前面我们了解了“大O表示法”以及对不同的算法评估。
下面我们来讨论下Python中list和dict两种内置数据类型上各种操作的大O数量级。
对比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列表数据类型
list类型各种操作的实现方法有很多，如何选择具体哪种实现方法？总的方案是让最常用的操作性能最好，牺牲不太常用的操作。
常用性能操作
最常用的是按照索引取值和赋值v=a[i]和a[i]=v。
由于列表的随机访问特性，这两个操作执行时间与列表大小无关，均为O(1)。
另一个是列表增长，可以选择append()和__add__() 或 “+”
l.append(v) 执行时间是O(1)
l = l + [v] 执行时间是O(n+k),其中k是被加的列表长度
四种生成前n个整数列表的方法
- 方法一：
def foo1():
l = []
for i in range(1000):
l = l + [i] - 方法二：
def foo2():
l = []
for i in range(1000):
l.append(i) - 方法三：
def foo3():
l = [i for i in range(1000)] - 方法四：
def foo4():
l = list(range(1000))
使用timeit模块对函数计时
创建一个Timer对象，指定需要反复运行的语句和只需要运行一次的”安装语句”。然后调用这个对象的timeit方法，其中可以指定返回运行多少次
if __name__ == \'__main__\':
from timeit import Timer
t1 = Timer("foo1()","from __main__ import foo1")
print("concat %f seconds\n" % t1.timeit(number=1000)) # cconcat 1.099056 seconds
t2 = Timer("foo2()", "from __main__ import foo2")
print("append %f seconds\n" % t2.timeit(number=1000)) # append 0.064581 seconds
t3 = Timer("foo3()", "from __main__ import foo3")
print("comprehension %f seconds\n" % t3.timeit(number=1000)) # comprehension 0.039818 seconds
t4 = Timer("foo4()", "from __main__ import foo4")
print("list range %f seconds\n" % t4.timeit(number=1000)) # list range 0.023467 seconds
我们可以看到，列表连接（concat）最慢，list range最快，速度相差50倍左右
append也要比concat快的多，另外我们注意到推导式的速度是append两倍的样子。
List基本操作的大O数量级
Operation Big-O Efficiency
index[] O(1)
index assignment O(1)
append O(1)
pop() O(1)
pop(l) O(n)
insert(i,item) O(n)
del operator O(n)
iteration O(n)
contain(in) O(n)
get slice[x:y] O(k)
del slice O(n)
set slice O(n+k)
reverse O(n)
concatenate O(k)
sort O(n log n)
multiply O(nk)
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变大而边长。
示例1：
# 我们对长度两百万的列表，执行1000次
if __name__ == \'__main__\':
import timeit
x = list(range(2000000))
popzero = timeit.Timer("x.pop(0)", "from __main__ import x")
print("x: %f seconds\n" % popzero.timeit(number=1000)) # x: 1.452277 seconds
y = list(range(2000000))
popend = timeit.Timer("y.pop()", "from __main__ import y")
print("y: %f seconds\n" % popend.timeit(number=1000)) # y: 0.000058 seconds
我们发现pop()的时间是0.000058秒，pop(0)的时间是1.452277秒
示例2：我们通过改变列表的大小来测试两个操作的增长趋势
if __name__ == \'__main__\':
import timeit
popzero = timeit.Timer("x.pop(0)", "from __main__ import x")
popend = timeit.Timer("x.pop()", "from __main__ import x")
print("pop(0) pop()")
for i in range(1000000,10000001,1000000):
x = list(range(i))
pt = popend.timeit(number=1000)
x = list(range(i))
pz = popzero.timeit(number=1000)
print("%15.5f,%15.5f" % (pz, pt))
输出结果：
pop(0) pop()
0.41731, 0.00007
1.38946, 0.00006
2.46675, 0.00006
3.48518, 0.00014
4.51965, 0.00006
5.54893, 0.00006
6.80396, 0.00007
8.26509, 0.00007
8.88511, 0.00007
9.87580, 0.00007
不难发现，pop()是平坦的常数，pop(0)是线性增长的趋势。
dict数据类型
字典与列表不同，根据key找到数据项，而列表是根据位置(index).
最常用的取值get和赋值set，其性能为O(1),另一个重要的操作contains(in)是判断字典中是否存在某个key,这个性能也是O(1)。
operation Big-O Efficiency
copy O(n)
get item O(1)
set item O(1)
delete item O(1)
contains(in) O(1)
iteration O(n)
List和dict的in操作对比
设计一个性能试验来验证list中检索一个值，以及dict中检索一个值的计时对比。生成包含连续值的list和包含连续key的dict,用随机数来检验操作符in的耗时。
if __name__ == \'__main__\':
import timeit
import random
for i in range(10000, 100001, 20000):
t = timeit.Timer("random.randrange(%d) in x" %i,
"from __main__ import random,x")
x = list(range(i))
l_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, l_time, d_time))
输出结果：
10000, 0.059, 0.001
30000, 0.188, 0.001
50000, 0.274, 0.001
70000, 0.395, 0.001
90000, 0.521, 0.001
110000, 0.614, 0.001
130000, 0.725, 0.001
150000, 0.859, 0.001
170000, 0.968, 0.001
190000, 1.068, 0.001
210000, 1.280, 0.001
230000, 1.398, 0.001
250000, 1.458, 0.001
270000, 1.562, 0.001
...
我们可以清楚的看到字典的执行时间与规模无关，是常数。
而列表的执行时间则随列表的规模加大而线性上升。
更多Python类型操作复杂度
Python官方的算法复杂度网站：https://wiki.python.org/moin/TimeComplexity