数据结构与算法 - 二、算法分析 - 《03_数据结构与算法》

1. 程序和算法的区别
2. 算法分析的概念
- 2.1 计算资源的指标
3. 大O表示法
4. 变位词判断问题
5. Python数据类型的性能
6. 第三方模块big-O

1. 程序和算法的区别

算法：是对问题解决的分步描述。

程序：则是采用某种编程语言实现的算法，同一个算法通过不同的程序员采用不同的编程语言，能够产生很多程序。

2. 算法分析的概念

比较程序的 “好坏” ，有更多因素，代码风格，代码可读性。
我们主要感兴趣的是算法本身的特性。
算法分析主要就是：从计算资源消耗的角度来评判和比较算法

更高效利用计算资源，或者更少占用计算资源的算法，就是好算法。

2.1 计算资源的指标

一种是算法解决问题过程需要的存储空间或内存
- 但是存储空间受到问题自身数据规模的变化影响，要区分哪些存储空间是本身描述所需，哪些是算法占用，不容易。

另一种是算法的执行时间
- 我们可以对程序进行实际运行测试，获得真正的运行时间；
- python中有一个 time 模块，可以获取计算机系统当前时间；
- 关于运行时间的实际检测，有点问题：关于编程语言和运行环境；
- 同一个算法，采用不同的编程语言编写，放在不同法人机器上运行，得到的运行时间会不一样，有时候会大不一样。
所以我们需要更好的方法来衡量算法的运行时间，这个指标与具体的机器、程序、运行时段无关。

【扩展】

下面是一个装饰器，来获取程序执行时间：

# 一个装饰器，可以统计任意一个函数的执行时间
import time
def get_time(func):
    def inner(*args,**kwargs):
        # 开始时间
        start = time.time()   # 获取当前时间
        # 调用原函数
        func(*args,**kwargs)
        # 结束时间
        end = time.time()
        result = round(end - start,3) # 四舍五入，保留3位小数
        return result
    return inner
@get_time
def check():
    for i in range(1000000):
        pass
print(check())

3. 大O表示法

3.1 算法时间的衡量指标

一个算法所实施的操作数量或者步骤数可以作为独立于具体程序/机器的度量指标，

哪种操作跟算法的具体实现无关？
需要一种通用的基本操作来作为表示运行步骤的计量单位

赋值语句是一个合适的选择

一条赋值语句同时包括了（表达式）计算和（变量）存储两个基本资源；
仔细观察程序设计语言特性，除了与计算资源无关的定义语句外，主要就是三种控制流语句和赋值语句，而控制流仅仅起了组织语句的作用，并不实施处理。

赋值语句执行次数：

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

分析SumOfN的赋值语句执行次数：

对于 “问题规模” n，即n输入的时候源代码会执行多少次；
赋值语句数量 T(n)=1+n
那么什么是问题规模？

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

问题规模：影响算法执行时间的主要因素。
在前 n 个整数累计求和的算法中，需要累计的整数个数合适作为问题规模的指标
- 前100,000个整数求和对比前 1,000个整数求和，算是同一问题的更大规模

算法分析的目标就是要找出问题规模会怎么影响一个算法的执行时间

3.3 数量级函数(Order of Magnitude)

基本操作数量级函数 T(n) 的精确值并不是特别重要，重要的是 T(n) 中起决定性因素的主导部分
- 用动态的眼光看，就是当问题规模增大的时候， T(n) 中的某一部分会盖过其他部分的贡献

数量级函数描述了 T(n) 中随着 n 增加而增加速度最快的主导部分
- 称作 “大O” 表示法，记作O(f(n))，其中 f(n) 表示 T(n) 中主导部分

例1：T(n) = n + 1

当 n 增大时，常数1在最终结果中显得越来越无足轻重
所以可以去掉1，保留n 作为主要部分，运行时间数量级就是 O(n)

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

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

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

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

4.4 常见大O数量级函数

通常当n 较小时，难以确定其数量级
当 n 增长到较大时，容易看出其主要变化量级 | f(n) | 名称 | | —- | —- | | 1 | 常数 | | log(n) | 对数 | | n | 线性 | | n*log(n) | 对数线性 | | n² | 平方 | | n³ | 立方 | | 2ⁿ | 指数 |

04_数量级实例.png

仅保留最高阶项 n² ，去掉所有系数；
数量级为 O(n²)
04_大O数量级.png

4.5 其他算法复杂度表示法

05_其他算法复杂度表示法.png

4. 变位词判断问题

问题描述：所谓 “变位词” 是指两个词之间存在 组成字母的重新排列关系。

如：heart和earth，python和typhon，为了简单起见，假设参与判断的两个词仅由小写字母构成，而且长度相等

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

可以很好展示同一问题的不同数量级算法

解法1：逐字检查

def anagramSolution1(s1, s2):
 # s2转化为列表
 alist = list(s2)
 pos1 = 0
 stillOK = True
 # 循环s1的每个字符
 while pos1 < len(s1) and stillOK:
     pos2 = 0
     found = False
     while pos2 < len(alist) and not found:
         # 逐个与s2对比
         if s1[pos1] == alist[pos2]:
             found = True
         else:
             pos2 = pos2 + 1
     if found:
         alist[pos2] = None  # 找到了，打钩，即将原有值改为None
     else:
         stillOK = False
     pos1 = pos1 + 1
 return stillOK
print(anagramSolution1('abcd', 'dcba'))

逐字检查-算法分析：

问题规模：词中包含的字符个数 n
主要部分在于两重循环

外层循环遍历 s1 每个字符，将内层循环执行n次，而内层循环在 s2 中查找字符，每个字符的对比次数，分别是1、2 …… n 中的一个，而且各不相同

所以总执行次数是 1+2+3+……+n

可知其数量为O(n²)

解法2：排序比较

代码：

排序比较-算法分析：

粗看上去，本算法只有一个循环，最多执行 n 次，数量级是 O(n)

但循环前面两个 sort并不是无代价的
排序算法采用不同的解决方案，其运行时间数量级差不多是 O(n²) 或者 O(n log n)，大过循环的 O(n)

所以本算法时间主导的步骤是排序步骤
本算法的运行时间数量级就等于排序过程的数量级 O(n log n)

解法4：计数比较

解题思路：对比两个词中的每个字母出现的次数，如果26个字母出现的次数都相同的话，这两个字符串就一定是变位词。
具体做法：

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

代码：

def anagramSolution4(s1, s2):
    c1 = [0] * 26  # 计数器 [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
    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'))

计数比较-算法分析：

计数比较算法中有3个循环迭代，但不像解法1 那样存在循环嵌套

前两个循环用于对字符串进行计数，操作次数等于字符串的长度；
第3 个循环用于计数器比较，操作次数总是26 次。

所以总操作此时 T(n)=2n+26，其数量级为 O(n)

这是一个线性数量级的算法，是4个变位词判断算法中性能最优的

值得注意的是，本算法依赖于两个长度为26的计数器列表，来保存字符计数，这相比前3个算法需要更多的存储空间

如果考虑由大字符集构成的词（如中文具有上万个不同字符），还会需要更多的存储空间

牺牲存储空间来换取运行时间，或者相反，这种在时间空间之间的取舍和权衡，在选择问题解法的过程中经常会出现。

5. Python数据类型的性能

讨论Python两种内置数据类型上各种操作的大O数量级：

列表list、字典dict
这是两种重要的python数据类型，
通过运行试验来估计其各种操作运行时间数量级

5.1 列表和字典的操作

类型	list	dict
索引	自然数	不可变类型值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)	无
其它	sort、reverse	has_key、update

5.2 List列表数据类型

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

1)、List列表数据类型常用操作性能：

最常用的是：安索引取值和赋值（v=a[i]，a[i]=v)
- 由于列表的随机访问特性，这两个操作执行时间与列表大小无关，均为O(1)

另一个是列表增长，可以选择 append() 和 __add__() +
- list.append(v)，执行时间是 O(1)
- lst = lst + [v]，执行时间是O(n+k)，其中k是被加的；列表长度
- 选择哪个方法来操作列表，决定了程序的功能

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

# 1.首先是循环连接列表（+）方式生成
def test1():
    l = []
    for i in range(1000):
        l = l + [i]
# 2.用append方法添加元素生成
def test2():
    l = []
    for i in range(1000):
        l.append(i)
# 3.用列表推导式生成
def test3():
    l = [i for i in range(1000)]
# 4.用range函数调用转成列表
def test4():
    l = list(range(1000))

3)、使用`timeit` 模块对函数计时

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

from timeit import Timer
t1 = Timer("test1()", "from __main__ import test1")
print("concat %f seconds\n" % t1.timeit(number=1000))            # concat 1.074861 seconds
t2 = Timer("test2()", "from __main__ import test2")
print("append %f seconds\n" % t2.timeit(number=1000))            # append 0.051259 seconds
t3 = Timer("test3()", "from __main__ import test3")
print("comprehension %f seconds\n" % t3.timeit(number=1000))    # comprehension 0.027395 seconds
t4 = Timer("test4()", "from __main__ import test4")
print("list range %f seconds\n" % t4.timeit(number=1000))        # list range 0.012668 seconds

分析：
- 列表连接 concat 最慢，List range 最快，速度相差100倍
- append也要比concat快的多
- 列表推导式的速度是append 的2倍
关于 timeit 参数理解：

4)、List基本操作的大O数量级

5)、list.pop的计时试验
pop 这个操作
- pop() 从列表末尾移除元素，O(1)
- pop(i) 从列表中部移除元素，O(n)

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

5.3 dict数据类型

字典与列表不同，根据关键吗（key）找到常数项，而列表是根据位置（index）
- 最常用的取值 get 和赋值 set ，其性能为 O(1)
- contains(in) 是判断字典中是否存在某个关键吗（key），这个性能也是O(1)
5.4 list和dict的in操作对比

Python官网的算法复杂度网站：https://wiki.python.org/moin/TimeComplexity

6. 第三方模块big-O

参考：https://pypi.org/project/big-O

作用：估算一个函数的大O数量级。

安装：

pip install big-O

模块：

big_o(func, data_generator, min_n, max_n, n_measures, n_repeats, n_timings)
# 返回值：(best_class, fitted) 最佳拟合的复杂度，以及其他拟合信息

参数	含义
func	需要估计大O数量级的算法，1个输入参数
data_generator	能产生输入参数的函数，以N为参数
min_n	最小N
max_n	最大N
n_measures	取多少个N
n_repeats	重复执行多少次func，来计算执行时间
n_timings	重复测量多少次，保留最好测量结果

一些通用的data_generator：

bigo.datagen.n(N) 就是参数N；

big_o.datagen.integers(N，min，max) 返回N个随机整数list

big_o.datagen.range_n(N) 返回参数N的range(N)列表list

示例：估算排序函数sorted 的大O数量级

from big_o import big_o, datagen
# 估算排序函数sorted 的大O数量级
best, other = big_o(
    sorted,
    lambda n: datagen.integers(n, 10000, 50000),  # 将三个参数的函数变成一个参数的函数，用lambda
    min_n=10000,
    max_n=100000,
    n_measures=100,
)
print(best)  # Linearithmic: time = 0.00027 + 1.3E-08*n*log(n) (sec)

二、算法分析