Python数据结构与算法分析

第二章   算法分析

2.1 何为算法分析

 在解决问题时算法分析关心的是基于所使用的计算资源比较。计算资源指的是考虑算法在解决问题时要占用的空间或内存或者是算法的执行时间或运行时间。

2.1.1 大O记法

 在进行算法分析时，语句总的执行次数T(n)是关于问题规模n的函数，进而分析T(n)随n的变化情况并确定T(n)的数量级。算法的时间复杂度，也就是算法的时间度量，记作T(n) = O(f(n))。它表示随问题规模n的增大，算法执行时间的增长率和 f(n) 的增长率相同，称作算法的渐近时间复杂度，简称时间复杂度。其中f(n) 是问题规模n的某个函数。

①来体现算法时间复杂度的记法，称之为大O记法。

②一般情况下，随着n的增大，T(n)增长最慢的算法为最优算法。

推导大O阶方法

• 推导大O阶：

  • 用常数1取代运行时间中的所有加法常数。
  • 在修改后的运行次数函数中，只保留最高阶项。
  • 如果最高阶存在且系数不是1，则去除与这个项相乘的系数，得到的结果就是大O阶。

最高阶项 ：an³+2bn²+c   c是函数低阶项，n³是高阶项

以下是常见的大O函数：

消耗时间从小到大的一次顺序是： O(1) < O(log n) < O(n) < O(nlog n) < O(n²) < O(n³)

a = 5  #执行1次
b = 6  #执行2次
c = 10 #执行3次
for i in range(n):
    for j in range(n): 
        x = i*i
        y = j*j
        z = i*j    #执行3+3n²次
for k in range(n):
    w = a*k+45
    v = b*b     #执行3+3n²+2n次
d =33           #执行3+3n²+2n+1次

执行次数T(n) = 3+3n²+2n+1 ,最高项为n²，所以时间复杂度是O(n²)

2.1.2 异序词检测示例

 如果一个字符串只是重排了另一个字符串的字符，那么这个字符串就是另一个的异序词，比如 heart 与 earth，以及 python与 typhon。为了简化问题，假设要检查的两个字符串长度相同，并且都是由 26 个英文字母的小写形式组成的。我们的目标是编写一个布尔函数，它接受两个字符串，并能判断它们是否为异序词。

1. 方案1：清点法

 清点第 1 个字符串的每个字符，看看它们是否都出现在第 2 个字符串中。如果是，那么两个字符串必然是异序词。

#思路：s1及s2两个字符串，我们把s2转化为列表，因为字符串不可更改；
#我们循环比较s1,s2的单词是否一致，一致把s2中单词设置none;
def anagramSolution(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(anagramSolution('heart', 'earth'))

 对于 s1 中的 n 个字符，检查每一个时都要遍历 s2 中的 n 个字符。要匹配 s1 中的一个字符，列表中的 n 个位置都要被访问一次。因此，访问次数就成了从 1 到 n的整数之和。最高项为n²，时间复杂度为O(n²)。

2. 方案2：排序法

 尽管 s1 与 s2 是不同的字符串，但只要由相同的字符构成，它们就是异序词。基于这一点，可以采用另一个方案。如果按照字母表顺序给字符排序，异序词得到的结果将是同一个字符串。

#思路：先将字符串转换为列表，然后使用 sort 方法对列表排序

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

3. 方案3：蛮力法

 用蛮力解决问题的方法基本上就是穷尽所有的可能。就是把s1中字符串所有可能的排列全部列出来，字符串的总数是n!，当n很大的时候，比2^n增长还快，算法不可取；

4. 方案4：计数法  两个异序词有同样数目的 a、同样数目的 b、同样数目的 c，等等。要判断两个字符串是否为异序词，先数一下每个字符出现的次数。因为字符可能有26 种，所以使用 26 个计数器，对应每个字符。每遇到一字符，就将对应的计数器加 1。最后，如果两个计数器列表相同，那么两个字符串肯定是异序词。

def anagramSolution(s1,s2):
    c1 = [0]*26
    c2 = [0]*26
    # print(c1)
    if len(s1) != len(s2):
        stillOK = False
    else:
# ord() 函数是 chr() 函数（或 unichr() 函数的配对函数，它以一个字符（长度为1的字符串）作为参数，返回对应的 ASCII 数值，或者 Unicode 数值
#如果所给的 Unicode 字符超出#你的 Python定义范围，则会引发一个 TypeError 的异常。
        
        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
        print(c1,c2)
        j = 0
        stillOK = True
        while j<26 and stillOK:
            if c1[j] == c2[j]:
                j = j+1
            else:
                stillOK = False
    return stillOK

总步骤T(n)=2n+26 即时间复杂度为O(n)

2.2 Python 数据结构的性能

 本节的目标是针对 Python 的列表和字典介绍如何用大 O 记法描述操作的性能。

2.2.1 列表

假设要从 0 开始生成含有 n 个数的列表，来看看 4 种生成方式。

• 用 for 循环通过连接操作创建列表
• 采用追加方法
• 使用列表解析式
• 用列表构造器调用 range函数

#1.用 for 循环通过连接操作创建列表

def test1():
    l =[]
    for i in range(1000):
        l=l+[i]
#2.追加法
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))

下面展示了测试函数各运行 1000次所花的时间：

在列表末尾调用 pop 时，操作是常数阶的，在列表头一个元素或中间某处调用 pop 时，则是 n 阶的。

2.2.2 字典

 Python 的第二大数据结构就是字典。你可能还记得，字典不同于列表的地方在于，可以通过键，而不是位置——访问元素。

2.3 小结

• 算法分析是一种独立于实现的算法度量方法。
• 大 O 记法使得算法可以根据随问题规模增长而起主导作用的部分进行归类。