算法分析
算法和算法复杂性
可计算的问题：
- what：分类问题——树状判定分支
- why： 证明问题——公式序列解决
- how： 或称问题——算法流程解决
欧几里得算法的python实现
def alg(a,b):
if b==0 :
return a
print(a)
c=a%b
alg(b,c)
def main(): #a,b为要计算的两个数
a=15
b=9
print(alg(a,b))
main()
计算复杂性研究的是问题的难度，算法实在资源约束的情况下寻找最优方案。
不可计算问题
- 停机问题
- 几乎所有无理数都无法通过算法找出任意一位精确数
程序与算法的区别
算法是描述问题解决的分布步骤而程序则是通过某种编程语言实现的算法。
算法分析主要是从计算机资源消耗的角度来评判和比较算法。评判的两个标准有两种：算法执行时间和空间（内存或存储空间）。
利用python的time库中 time.time()函数可以计算算法的执行时间。
time.time()是计算从1970到现在的时长，并将值返回。
对于算法运行时间的检测也收到语言性能、机器的性能的影响。
大O表示法
一个算法所实施的操作数量或步骤可作为独立于程序/机器的度量指标。
程序设计语言中除与计算资源无关的定义语句外，主要是三种控制流语句和赋值语句。
一个赋值语句包含了（表达式）计算和（变量）存储两个基本资源。而控制流语句仅起组织语句的作用，并不涉及处理。
算法分析的目标是找出问题规模如何影响执行时间
数量级函数
数量级函数描述了T（n）中随着n增加而增加速度最快的主导部分。称作大O表示法记作O(f(n)),其中f(n)表示T(n)中的主导部分。
T(n)=5n^2+27n+1005
当n越来越大起主导作用的是5*n^2,其中系数5对n^2的增长速度无影响。因此可以表示为O(n^2)
具体数据也会影响算法运行时间，如排序算法。此时分为最好，最差和平均状况，主要还是通过平均状况分析性能。
大O表示所有上限中最小的那个上限
大Ω表示所有下限中最大的那个下限
如果上下限相同用Θ大表示
变位词
写一个布尔函数，一两个此作为参数，返回两个词是否为变位词
- 将每一个单词逐个检查
课程给的代码示例：
def solu1_example(s1,s2):
alist = list(s2)
pos1 = 0
stillok = True
while pos1 < len(s1) and stillok: #只要字符中有一个没找到就可以通过32行退出
pos2 = 0
found =False
while pos2 < len(alist) and not found:
if s1[pos2] == alist[pos2]:
found = True
else:
pos2 = pos2 + 1
if found:
alist[pos2] = None
else:
stillok = False
pos1 = pos1 + 1
return stillok
如果将自己一个一个对比，要注意同一个字符在字符串中可能会出现很多次。因此，在判断是找到一个相同时必须要设置为none
数量级的计算
两层循环，外层循环为n次，每次到内层每次循环查找次数为1–n之间。因此总和为：1/2*(n^2)+1/2*n。所以数量级为O(n^2)
- 排序比较：先将字符串按字母顺序排好，再一一对比
def solu2(s1,s2):
alist1 = list(s1)
alist2 = list(s2)
alist1.sort() #列表排序函数
alist2.sort()
pos=0
matches = True
while pos < len(s1) and matches:
if alist1[pos] == alist2[pos]:
pos = pos + 1
else:
matches = False
return matches
看似很简单仅有一个循环，但在两个数组排序过程消耗的时间不可忽视。时间运算数量级为O(nlog n)
暴力法
将S1中的字符进行全排列，然后查看S2是否在其中。
用暴力算法解决时，数量级会以N!的方式增长。
计数比较
检查26个字母在字符中出现的情况，若两者相同则输出。
ord()函数：返回字符的Unicode编码值
T(n)=2n + 26;
因此数量级为O(n);相比之下，该项算法性能较优，然而该算法需要的内存空间较大。
def solu4(s1,s2):
c1 = [0] * 26
c2 = [0] * 26
for i in range(len(s1)):
pos = ord(s1[i]) - ord('a') #返回一个字符的uincode编码
c1[pos] = c1[pos] + 1
for i in range(len(s2)):
pos = ord(s2[i]) - ord('a')
c2[pos] = c2[pos] + 1
j = 0
stillok = True
while j < 26 and stillok:
if c1[j] == c2[j]:
j = j + 1
else:
stillok = False
return stillok
Python数据类型的性能
list和dict
按索引取值和赋值：由于列表的随机访问特性，均为O(1)
列表添加append()和_add_()"+"
- list.append(v)–O(1),lst= lst+ [v]
- 实行时间为O(n+k),k为所加列表长度
pop的复杂度
从尾部移除数组的元素是复杂度为O(1),移除数组中某一元素为O(N)；原因是移除中间元素需要将这个元素后面的元素前移。这是为了保证按索引取值和赋值速度的妥协。
在列表中in操作复杂度为O(N),字典中为O(1)。