什么是算法分析？

计算资源指标：一种是算法解决问题过程中需要的储存空间或内存，另一种是算法的执行时间

运行时间检测 time模块，获取计算机系统当前时间

例如： 方法一：累计求和程序的运行时间检测

import time def sumOfN2(n): start = time.time() theSum = 0 for i in range(1, n + 1): theSum = theSum + i end = time.time() return theSum, end - start for i in range(5): print("Sum is %d required %10.7f seconds"% sumOfN2(10000))

Error:第一次输入没有在def的函数名括号里填n 后来搜索明白，括号里必须有一个占位符，专业的说是在类的函数内引入变量

方法二：无迭代的累计算法（利用求和公式）

#只改def这一段 def sunOfN3(n): start = time.time() theSum = (n*(n+1))/2 end = time.time() return theSum, end - start

新算法运行时间几乎与需要累计的数目无关

“大O表示法”

大O表示法：表示了所有上限中最小的那个上限 数量级函数Order of Magnitude f(n)

例如： 代码赋值语句可以分为4个部分 $$T(n)=3+3n^2+2n+1=3n^2+2n+4$$ 仅保留最高阶项n^2，去掉所有系数，数量级$O\left(n^2\right)$

a = 5 b = 6 c = 10 for i in range(n): for j in range(n): x = i * i y = j * j z = i * j for k in range(n): w = a * k + 45 v = b * b d = 33

“变位词”判断

"变位词"判断问题

问题描述:所谓"变位词"是指两个词之间存在组成字母的重新排列关系,如:heart和earth

解题目标:写一个bool函数,以两个词作为参数,返回这两个词是否变位词

解法1:逐字检查 将词1中的字符逐个到词2中检查是否存在 存在就“打勾”标记 如果每个字符都能找到，则两个词就是变位词 只要有1个字符找不到，就不是变位词 为了简单，假设参与判断的两个词仅由大小写字母构成，且长度相等

def anagramSolution1(s1,s2): alist = list(s2)#复制s2到列表 pos1 = 0 stillOK =True while pos1 < len(s1) and stillOK:#循环s1的每个字符 pos2 = 0 found = False while pos2 < len(alist) and not found: if s1[pos1] == alist[pos2]:#在s2逐个对比 found = True else: pos2 = pos2 + 1 if found: alist[pos2] = None#找到，打勾 else: stillOK = False#未找到，失败 pos1 = pos1 + 1 return stillOK print(anagramSolution1('abcd','dcba'))

这段值得学习的是 stillOK=True 增加了代码的可读性 实现“打勾”标记：将词2对应字符设为None 注意：字符串是不可变类型，需要先复制到列表中，如果没有复制会报错 总执行次数n+n-1+n-2+…+3+2+1 数量级为O(n^2)

解法2：排序比较 将两个字符串都按照字母顺序排好序 再逐个字符对比是否相同，如果相同则是变位词

def anagramSolution2(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 print(anagramSolution2('abcde','edcba'))

本算法时间主导的步骤是排序步骤 后面的学习将会知道排序算法的时间数量级差不多是O(n^2)或者O(n log n)，大过O(n)

解法3：暴力法 穷尽所有可能的组合n!个 将s1中出现的字符进行全排列，再查看s2是否出现在全排列列表中

解法4：计数比较 对比两个词中每个字母出现的次数，如果26个字母出现的次数都相同的话，这两个字符串就一定是变位词

具体做法 为每个词设置一个26位的计数器，先检查每个词，在计数器中设定好每个字母出现的次数 计数完成后，进入比较阶段，看两个字符串的计数器是否相同，如果相同则输出是变位词的结论

def anagramSolution4(s1,s2): c1 = [0] * 26 c2 = [0] * 26 #分别都计数 for i in range(len(s1)): pos = ord(s1[i])-ord('a') 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 print(anagramSolution4('apple','pleap'))

值得学习的：计数器的设置 总操作次数T(n)=2n+26，数量级O(n) 本算法依赖于两个长度为26的计数器列表，来保存字符计数，这需要更多的存储空间

时间空间之间的取舍和权衡

Python数据类型的性能

列表list和字典dict操作对比 例如： 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)) from timeit import Timer t1 = Timer("test1()","from __main__ import test1") print("concat %f seconds\n" %t1.timeit(number=1000)) t2 = Timer("test2()","from __main__ import test2") print("append %f seconds\n" % t2.timeit(number=1000)) t3 = Timer("test3()","from __main__ import test3") print("comprehension %f seconds\n" % t3.timeit(number=1000)) t4 = Timer("test4()","from __main__ import test4") print("list range %f seconds\n" % t4.timeit(number=1000))

列表连接（concat）最慢，List range最快，速度相差近200倍 是append两倍的样子 值得了解：timeit 创建一个Timer对象，指定需要反复运行的语句和需要运行一次的“安装语句”，然后调用这个对象的timeit方法，其中可以指定反复运行多少次 List基本操作的大O数量级 例如： list.pop的计时试验 从中部移除元素，要把移除元素后面的元素全部向前挪位复制一遍。这种实现方法能够保证列表按索引取值和赋值的操作很快，达到O(1)

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,100000001,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()是平坦的常数，pop(0) 是线性增长的趋势 dict数据类型 根据关键码（key）找到数据项，二列表是根据位置（index） 最常用的取值get和赋值set,contains(in)判断字典中是否存在某个关键码(key)，性能为O(1)

例如， list和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(1)) lst_time = t.timeit(number=1000) x = {j:None for j in range(i)}#数据是None,key来自于range(i) d_time = t.timeit(number=1000) print("%d,%10.3f,%10.3f"%(i,lst_time,d_time))

值得学习的：x = {j:None for j in range(i)} 字典的执行时间与规模无关，是常数 列表的执行时间则随着列表的规模加大而线性上升