二、算法分析

201 什么是算法分析

对比程序，还是算法？

• 如何对比两个程序？
  • 看起来不同，但解决同一个问题的程序，哪个“更好”？
• 程序和算法的区别
  • 算法是对问题解决的分布描述
  • 程序则是采用某种编程语言实现的算法，同一个算法通过不同的程序员采用不同的编程语言，能产生很多程序

累计求和问题

• 我们来看一段程序，完成从 1 到 n 的累加，输出总和
  • 设置累计变量 = 0
  • 从 1 到 n 循环，逐次累加到累计变量
  • 返回累计变量

def sum0fN(n):
  theSum = 0
  for i in range(1, n + 1):
    theSum = theSum + i
  return theSum

print(sum0fN(10))

• 再看第二段程序，是否感觉怪怪的？
  • 但实际上本程序功能与前面那段相同
  • 这段程序失败之处在于：变了命名词不达意，以及包含了无用的垃圾代码

def foo(tom):
  fred = 0
  for bill in range(1, tom + 1):
    barney = bill
    fred = fred + barney
  return fred

print(foo(10))

算法分析的概念

• 比较程序的“好坏”，有很多因素
  • 代码风格、可读性等等
• 我们主要感兴趣的是算法本身特性
• 算法分析主要就是从计算资源消耗的角度来评判和比较算法
  • 更高效利用计算资源，或者更少占用计算资源的算法，就是好算法
  • 从这个角度，前述两段程序实际上是基本相同的，它们都采用了一样的算法来解决累计求和问题

说到代码风格和可读性

• 为什么Python的强制缩进是好的？
  • 语句块功能和视觉效果统一
• 苹果公司的一个低级Bug
  • 由于c语言源代码书写缩进对齐的疏忽
  • 造成SSL连接验证被跳过
  • 2014.2.22修正iOS7.0.6
• 代码不像看起来那样运行

计算资源指标

• 那么何为计算资源？
• 一种是算法解决问题过程中需要的存储空间或内存
  • 但存储空间受到问题自身数据规模的变化影响
  • 要区分哪些存储空间是问题本身描述所需，哪些是算法占用，不容易
• 另一种是算法的执行时间
  • 我们可以对程序进行实际运行测试，获得真实的运行时间

运行时间检测

• Python中有一个time模块，可以获取计算机系统当前时间
  • 在算法开始前和结束后分别记录系统时间，即可得到运行时间

import time
time.time()

• 累计求和程序的运行时间检测
  • 用time 检测总运行时间
  • 返回累计和，以及运行时间（秒）

import time

def sum0fN2(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" % sum0fN2(10000))

• 在交互窗口连续运行5次看看
  • 1 到 10000累加
  • 每次运行约需 0.0007秒
• 如果累加到100000？
  • 看起来运行时间增加到 10000的10倍
• 进一步累加到 1000000？
  • 运行时间又是 100000的10倍了

第二种无迭代的累计算法

• 利用求和公式的无迭代算法

def sum0fN3(n):
  start = time.time()
  theSum = (n * (n + 1)) / 2
  end = time.time()
  return theSum, end - start

• 利用同样的方法检测运行时间
  • 10000；100000；1000000；10000000；100000000
  • 0.000010 接近于0
• 需要关注的两点
  • 这种算法的运行时间比前种都短很多
  • 运行时间与累计对象n的大小没有关系（前种算法是倍数增长关系）
• 新算法运行时间几乎与需要累计的数目无关

运行时间检测的分析

• 观察一下第一种迭代算法
  • 包含了一个循环，可能会执行更多语句
  • 这个循环运行次数跟累加值n有关系，n增加，循环次数也增加

def sum0fN(n):
  theSum = 0
  for i in range(1, n + 1):
    theSum = theSum + i
  return theSum

print(sum0fN(10))

• 但关系运行时间的实际检测，有点问题
  • 关于编程语言和运行环境
• 同一个算法，采用不同的编程语言编写，放在不同的机器上运行，得到的运行时间会不一样，有时候会大不一样：
  • 比如把非迭代算法放在老旧机器上跑，甚至可能慢过新机器上的迭代算法
• 我们需要更好的方法来衡量算法运行时间
  • 这个指标与具体的机器、程序、运行时段都无关

202 大O表示法

算法时间度量指标

• 一个算法所实施的操作数量或步骤数可作为独立于具体程序/机器的度量指标
  • 哪种操作跟算法的具体实现无关？
  • 需要一种通用的基本操作来作为运行步骤的计量单位
• 赋值语句是一个合适的选择
  • 一条赋值语句同时包含了（表达式）计算和（变量）存储两个基本资源
  • 仔细观察程序设计语言特性，除了与计算资源无关的定义语句外，主要就是三种控制流语句和赋值语句，而控制流仅仅起了组织语句的作用，并不实施处理。

赋值语句执行次数

• 分析 Sum0fN的赋值语句执行次数
  • 对于“问题规模”n
  • 赋值语句数量 T(n) = 1 + n
  • 那么，什么是问题规模？

def sum0fN(n):
  theSum = 0  # 1
  for i in range(1, n + 1):  # n
    theSum = theSum + i  # 1
    return theSum

问题规模影响算法执行时间

• 问题规模：影响算法执行时间的主要因素
• 在前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)
  • O(n)

• 例2：T(n)=5n²+27n+1005

  • 当n很小时，常数1005其决定性作用
  • 但当n越来越大，n²项就越来越重要，其它两项对结果的影响则越来越小
  • 同样，n²项中的系数5，对于n²的增长速度来说也影响不大
  • 所以可以在数量级中去掉27n+1005，以及系数5的部分，确定为O（n²）
  • O(n²)

影响算法运行时间的其它因素

• 有时决定运行时间的不仅是问题规模
• 某些具体数据也会影响算法运行时间
  • 分为最好、最差和平均情况，平均状况体现了算法的主流性能
  • 对算法的分析要看主流，而不被某几种特定的运行状况所迷惑

常见的大O数量级函数

• 通常当n较小时，难以确定其数量级
• 当n增长到较大时，容易看出其主要变化量级

从代码分析确定执行时间数量级函数

• 代码赋值语句可以分为4个部分
  • T(n) = 3+3n²+2n+1 = 3n²+2n+4

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

• 仅保留最高阶项n²，去掉所有系数
• 数量级为 O(n²)

其它算法复杂度表示法

• 大O表示法
  • 表示了所有上限中最小的那个上限
• 大Ω表示法
  • 表示了所有下限中最大的那个下限
  • f(n) = Ω(g(n)) 当且仅当 g(n) = o(f(n))
• 大θ表示法
  • 如果上下限相同，那么就可以用大θ表示
  • f(n) = θ(g(n))
  • 当且仅当 f(n) = O(g(n)) 且 f(n) = Ω(g(n))

203 “变位词”判断问题（上）

“变位词”判断问题

• 问题描述
  • 所谓“变位词”是指两个词之间存在组成字母的重新排列关系
  • 如：heart和earth，Python和typhon
  • 为了简单起见，假设参与判断的两个词仅由小写字母构成，而且长度相等
• 解题目标：写一个bool函数，以两个词作为参数，返回这两个词是否变位词
• 可以很好展示同一问题的不同数量级算法

解法1：逐字检查

• 解法思路
  • 将词1中的字符逐个到词2中检查是否存在
  • 存在就“打勾”标记（防止重复检查）
  • 如果每个字符都能找到，则两个词是变位词
  • 只要有1个字符找不到，就不是变位词
• 程序技巧
  • 实现“打勾”标记：将词2对应字符设为None
  • 由于字符串是不可变类型，需要先复制到列表中

解法1：逐字检查-程序代码

def anagramSolution1(s1, s2):
  alist = list(s2)
  pos1 = 0
  stillOK = True
  while pos1 < len(s1) and stillOK:
    pos2 = 0
    found = False
    while pos2 < len(alist) and not found:
      if s1[pos1] == alist[pos2]:
        found = True
      else:
        pos2 = pos2 + 1
    if found:
      alist[pos2] = None
    else:
      stillOK = False
    pos1 = pos1 + 1
  return stillOk

print(anagramSolution1('abcd', 'dcba'))

解法1：逐字检查-算法分析

• 问题规模：词中包含的字符个数n
• 主要部分在与两重循环
  • 外层循环遍历 s1 每个字符，将内层循环执行n次
  • 而内层循环在s2中查找字符，每个字符的对比次数，分别是1、2…n中的一个，而且各不相同
• 所以总执行次数是 1 + 2 + 3 + ……+ n
  • 可知其数量级为 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'))

解法2： 排序比较-算法分析

• 粗看上去，本算法只有一个循环，最多执行n次，数量级是 O(n)
  • 但循环前面的两个sort并不是无代价的
  • 如果查询下后面的章节，会发现排序算法采用不同的解决方案，其运行时间数量级差不多是 O(n²) 或者 O(n log n)，大过循环的O(n)
• 所以本算法时间主导的步骤是排序步骤
• 本算法的运行时间数量级就等于排序过程的数量级O(n log n)

204 “变位词”判断问题（下）

解法3：暴力法

• 暴力法解题思路为：穷尽所有可能组合
• 将s1 中出现的字符进行全排列，再查看 s2 是否出现在全排列列表中
• 这里最大困难时产生s1所有字符的全排列
  • 根据组合数学的结论，如果n个字符进行全排列，其所有可能的字符串个数为n!
• 我们已知 n! 的增长速度甚至超过 2^n
  • 例如，对于 20 个字符长的词来说，将产生 20! = 2,432,902,008,176,640,000 个候选词
  • 如果每微秒处理1个候选词的话，需要近8万年时间来做完所有的匹配。
• 结论：暴力法恐怕不能算是个好算法

解法4：计数比较

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

解法4：计数比较-程序代码

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'))

解法4：计数比较-算法分析

• 计数比较算法中有3个循环迭代，但不像解法1那样存在嵌套循环
  • 前两个循环用于对字符串进行计数，操作次数等于字符长度n
  • 第3个循环用于计数器比较，操作次数总是26次
• 所以总操作次数 T(n) = 2n + 26，其数量级为 O(n)
  • 这是一个线性数量级的算法，是4个变位词判断算法中性能最优的
• 值得注意的是，本算法依赖于两个长度为26的计数器列表，来保存字符计数，这相比前3个算法需要更多的存储空间
  • 如果考虑由大字符集构成的词（如中文具有上万不同字符），还会需要更多存储空间。
• 牺牲存储空间来换取运行时间，或者相反，这种在时间空间之间的取舍和权衡，在选择问题解法的过程中经常会出现。
  • “不可随处小便”，“小处不可随便”

思考：把解法4用字典作为计算器修改…

205 Python数据类型的性能（上）

Python数据类型的性能

• Python两种内置数据类型上各种操作的大O数量级
  • 列表list 和字典 dict 这是两种重要的Python数据类型

对比list和dict的操作

都是容器类型、可变类型

List 列表数据类型

• list 类型各种操作（Interface）的实现方法有很多，如何选择具体哪种实现方法？
• 总的方案就是，让最常用的操作性能最好，牺牲不太常用的操作
  • 80/20准则：80%的功能其使用率只有20%

list 列表数据类型常用操作性能

• 最常用的是：按索引取值和赋值（v = a[i]，a[i] = v）
  • 由于列表的随机访问特性，这两个操作执行时间与列表大小无关，均为O(1)
• 另一个是列表增长，可以选择append() 和 _add_() “+”
  • lst.append(v)，执行时间是O(1)
  • lst = lst + [v]，执行时间是O(n+k)，其中k是被加的列表长度
  • 选择哪个方法来操作列表，决定了程序的性能

4种生成前n个整数列表的方法

• 首先是循环连接列表（+）方式生成
• 然后是用append方法添加元素生成
• 接着用列表推导式来做
• 最后是Range函数调用转成列表

def test1():
  l = []
  for i in range(1000):
    l = l + [i]
    
def test2():
  l = []
  for i in range(1000):
    l.append(i)

def test3():
  l = [i for i in range(1000)]
  
def test4():
  l = list(range(1000))

使用 timeit 模块对函数计时

• 创建一个 Timer 对象，指定需要反复运行的语句和只需要运行一次的“安装语句”
• 然后调用这个对象的 timeit 方法，其中可以指定反复运行多少次

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))

4种生成前n个整数列表的方法计时

• 我们看到，4种方法运行时间差别很大
  • 列表连接（concat）最慢，List range 最快，速度相差近200倍。
  • append 也要比 concat 快得多
  • 另外，我们注意到列表推导式速度是 append 两倍的样子

concat 1.889487 seconds
append 0.091561 seconds
comprehension 0.038418 seconds
list range 0.009710 seconds

List 基本操作的大O数量级

206 Python数据类型的性能（下）

list.pop 的计时试验

• 我们注意到pop这个操作

  • pop() 从列表末尾移除元素，O(1)
  • pop(i) 从列表中部移除元素，O(n)

• 原因在于Python所选择的实现方法

  • 从中部移除元素的话，要把移除元素后面的元素
  • 全部向前挪位复制一遍，这个看起来有点笨拙
  • 但这种实现方法能够保证列表按索引取值和赋值的操作很快，达到O(1)
  • 这也算是一种对常用和不常用操作的折衷方案

• 为了验证表中的大O数量级