算法分析基础
2018-02-07 本文已影响0人
持墨
算法分析基础
大O表示法（Big-O）
- 一个算法所实施的操作数量或这步骤数可作为独立于具体程序/机器的度量指标
- 赋值语句是一个合适的选择：一条赋值语句同时包含了（表达式）计算和（变量）储存两个基本资源；仔细观察程序设计语言特性，除了与计算资源无关的定义语句外，主要就是三种控制流语句和赋值语句，而控制流语句仅仅起了组织赋值语句的作用，并不实施处理。
#对于问题规模n，赋值语句数量T(n)=1+n
def sumOfn(n):
theSum=0#做了一次赋值
for i in range(1,n+1):
theSum=theSum+i#做了n次赋值
return theSum
- 问题规模影响算法执行时间：在前n个自然数累计求和的算法中，需要累计的自然数个数适合作为问题规模的指标，而算法分析的目标是要找到问题规模会怎样影响一个算法的执行时间
- 数量级函数（Order of Magnitude function)：基本操作数量级函数T(n)的精确值不是特别重要，重要的是T(n)中起决定性因素的主导部分。用动态的眼光看，就是当问题规模增大时，T(n)中的一些部分会覆盖过其他部分的贡献，数量级函数描述了T(n)中随着n增加而增长速度最快的部分
称作“大O”表示法，记作O(f(n))，其中f(n)表示T(n)中的主导部分 - 有时决定运行时间不仅是规模问题，某些具体数据也会影响算法运行时间：一般来说，平均情况体现了算法的主流性能，因此对算法的分析主要看主流，而不是被特殊情况所迷惑
常见的大O数量级函数
image
“变位词”判断问题
- 问题描述：所谓“变位词”是指两个词之间存在组成字母的重新排列关系
- 解题目标：写一个bool函数，以两个词作为参数，返回真假，表示这两个词是否变位
- 解法一：逐字检查：将字符串1中的字符逐个到字符串2中检查是否存在，存在就“打勾”标记（防止重复检查），如果每个字符都能找到，则两个词是变位词，只要有一个找不到就不是
def anagramsolution(s1,s2):
alist=list(s2)
pos1=0
stillOK=True
while pos1 < len(s1) and stillOK:
pos2=0
found=False
while pos1 < len(alist) and not found:
if s1[pos1]=alist[pos2]:
found=Ture
else:
pos2=pos2+1
if found:
alist[pos2]=None #打勾
else:
stillOK=False
pos1=pos1+1
return stillOK
- 解法二：排序比较：将两个字符串都按照相同字母顺序排好序，再逐个字符对比是否相同，如果相同则是变位词
def anagramsolution(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)
else:
matches=False
return matches
- 解法三：暴力法：穷尽所有可能的组合，即对字符串1中出现的字母进行全排列再查看字符二是否出现在全排列列表中
- 有组合数学的结论，对n个字符全排列，其所有可能的字符串有n！个
- 解法四：计数比较：对比两个字符串中每个字母出现的个数，如果26个字母出现的次数都相同的话，则为变位词
def anagramsolution(s1,s2):
c1 = [0]*26
c2 = [0]*26
for i in range(len(si))
pos = ord(s1[i]) - ord('a')
c1[pos] = c1[pos] + 1
for i in range(len(si))
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
以上四种算法的算法分析
- 解法一：主要部分在于两重循环，数量级为O(n^2)
- 解法二：一个循环的数量级为O(n)，丹sort函数的数量级为O(nlogn)
- 解法三：O(n!)
- 解法四：T(n)=2n+26,数量级为O(n)，但是由于算法依赖长度为26的计数表，因此牺牲了储存空间，提高了空间复杂度
python数据结构的性能
- python内置数据结构列表和字典在各种操作的大O数量级
image
- List基本操作的大O数量级
image
- Dictionary基本操作的大O数量级
-
image
使用timeit模块对函数计时
- 对于每个具体函数的执行时间，timeit模块提供了一种在一致的运行环境下可以反复调用并计时的机制
- timeit计时的使用方法：首先创立一个Timer对象，需要两个参数，第一个是需要反复运行的语句，第二个是为了建立运行环境而只需要运行一次的“安装语句”
然后调用这个对象的timeit方法，其中可以指定反复运行多少次，计时完毕后可以返回以秒为单位的时间
from timeit import Timer
t=Timer("test()","from __main__ import test")
print "cincat %f seconds" % t.timeit(number=1000)#运行1000次
