1、大O表示法

发表于 更新于 分类于 ， 本文字数： 5.7k 阅读时长 ≈ 5 分钟

摘要：跟随b站陈斌老师学习数据结构与算法第一课。

所谓算法分析

算法是解决问题的方法或者思路，它是程序实现的灵魂。程序是解决问题的具体做法，它是算法的实现过程。同一个算法可能对应不同程序。

比较程序的好坏因素众多，而比较算法好坏的指标就简单许多，其一般从计算资源的消耗角度出发：好的算法往往能够更高效地利用更少的计算资源。高效往往对应着程序执行时间短，占用更少的计算资源往往对应着需要更小的存储空间或者内存。

一般很难区分算法需要的存储空间究竟是因为问题本身还是算法需要，所以我们一般使用算法执行时间来衡量算法。

下面我们对两个累计求和的算法进行运行时间检测。

  • 利用循环累计求和：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
import time

def sum0fN2(n):
    start = time.time()
    theSum = 0
    for i in range(1, n+1):
        theSum += i
    end = time.time()
    return theSum, end-start

for i in range(5):
    print("Sum is %d required %10.7f seconds" % sum0fN2(10000))
print('\n')

# 如果将累加和分别增大十与一百倍，其执行时间如下：

for i in range(5):
    print("Sum is %d required %10.7f seconds" % sum0fN2(100000))
print('\n')
for i in range(5):
    print("Sum is %d required %10.7f seconds" % sum0fN2(1000000))

# 输出结果为：
# Sum is 50005000 required  0.0001163 seconds
# Sum is 50005000 required  0.0001297 seconds
# Sum is 50005000 required  0.0000899 seconds
# Sum is 50005000 required  0.0001163 seconds
# Sum is 50005000 required  0.0001256 seconds

# Sum is 5000050000 required  0.0011559 seconds
# Sum is 5000050000 required  0.0012946 seconds
# Sum is 5000050000 required  0.0011950 seconds
# Sum is 5000050000 required  0.0013113 seconds
# Sum is 5000050000 required  0.0012801 seconds

# Sum is 500000500000 required  0.0132554 seconds
# Sum is 500000500000 required  0.0133324 seconds
# Sum is 500000500000 required  0.0128369 seconds
# Sum is 500000500000 required  0.0120413 seconds
# Sum is 500000500000 required  0.0124726 seconds
  • 利用求和公式的无迭代算法：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def sum0fN3(n):
    start = time.time()
    theSum = (n * (n+1)) / 2
    end = time.time()
    return theSum, end-start

for i in range(5):
    i = 10 ** (i+4)
    print("Sum is %d required %10.7f seconds" % sum0fN3(i))

# 输出的结果为：
# Sum is 50005000 required  0.0000010 seconds
# Sum is 5000050000 required  0.0000002 seconds
# Sum is 500000500000 required  0.0000002 seconds
# Sum is 50000005000000 required  0.0000002 seconds
# Sum is 5000000050000000 required  0.0000002 seconds

从以上的实验中我们可以管中窥豹了解算法分析所要研究的东西：就是对于描述问题的数据量n，不同算法的运行时间会怎样随n变化而变化。

当数据n增大十倍，循环迭代累计求和算法执行时间增大十倍，而求和公式算法的执行时间不变。

但是还需要考虑到，算法的执行时间还受机器、程序、运行时段有关，所以我们接下来会用时间复杂度来衡量算法运行时间。

大O表示法

算法时间度量指标可以用算法所实施的操作数量或者步骤。

程序解决问题基本上实在进行计算与存储，算法基本上就是在做这两件事，而程序中赋值语句基本上包含两个操作，所以使用赋值语句作为基本计量单位来衡量算法时间指标。

这里还有一个前面提到过的量：问题规模，其实这个量就是上节代码中的“描述问题的数据量”。算法分析，就是找出问题规模会怎样影响一个算法的执行时间。

现在问题已经很明朗了，我们定义一个基本操作数量级函数$T(n)$，这个函数的精确值并不是重点，重点是函数中起决定因素的主导部分。

我们将数量级函数的主导部分提取，用以描述算法的时间复杂度，这就是大O表示法。比如说上述两种算法的时间复杂度分别是$O(n)$与$O(1)$。

“变位词”判断问题

“变位词”：两个词之间存在组成字母的重新排列关系（小写，等长度）。写一个bool函数，输入两词，判断两词是否为变位词。

逐字检查

将词1中的字符逐个到词2中检查是否存在，存在就“打勾”标记。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
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 += 1
        if found:
            alist[pos2] = None
        else:
            stillOK = False
        pos1 += 1
    return stillOK

算法包含两重循环，数量级为$O(n^2)$

排序比较

将两个字符串都按照字母排序，比较字符串是否相等。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
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 alist2[pos] == alist1[pos]:
            pos += 1
        else:
            matches = False
    return matches

粗略来看，本算法只有一个循环，数量级好像是$O(n)$，但是循环前面的两个sort并不是无代价的，排序算法的复杂度差不多是$O(n^2)$或者$O(nlogn)$，本算法的数量级等于排序的数量级$O(nlogn)$。

暴力法

穷尽所有可能的组合，即将s1中出现的字符全排列，判断s2是否出现，这种算法的数量级是$n!$。

计数比较

对比两个词中每个字母出现的次数，如果26个字母出现的次数都相同则是变位词。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def anagramSolution4(s1, s2):
    c1 = [0] * 26
    c2 = [0] * 26
    for i in range(len(s1)):
        pos = ord(s1[i]) - ord('a')
        c1[pos] += 1
    for i in range(len(s2)):
        pos = ord(s2[i]) - ord('a')
        c2[pos] += 1
    j = 0
    stillOK = True
    while j < 26 and stillOK:
        if c1[j] == c2[j]:
            j += 1
        else:
            stillOK = False
    return stillOK

时间复杂度是$O(n)$但是需要更多的存储空间。

python数据类型的性能

这里的数据类型主要是列表list以及字典dict。

对比list与dict常见操作：

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

让最常用的操作性能最好，略微牺牲不太常用操作的性能。

list列表数据类型

list基本操作大O数量级如下：

list取值赋值、增长

列表最常用的操作是按照索引取值与赋值，这两个操作执行时间与列表大小无关，均为$O(1)$。

列表增长，list1.append(v)执行时间是$O(1)$，list1 = list1 + [v]执行时间是$O(n + k)$。

下面比对四种生成前n个整数列表的算法：

  • 循环连接列表$(+)$方式生成

  • 用append方法添加元素

  • 列表推导式

  • range函数转换

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
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))

由于列表创建过快，采用循环操作记录算法执行时间：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
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 0.374207 seconds

# append 0.009102 seconds

# comprehension 0.006745 seconds

# list range 0.003467 seconds

list删除

可以注意到，list.pop()操作有两个复杂度，这是因为要保证列表按索引值取值和赋值的操作复杂度为$O(1)$，从中部移除元素要将后面的元素都向前挪一位。

下面可以通过计时试验验证这两个复杂度：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
import timeit
popzero = timeit.Timer("x.pop(0)", "from __main__ import x")
popend = timeit.Timer("x.pop()", "from __main__ import x")

# 先进行直观对比
x = list(range(2000000))
print(popzero.timeit(number=1000))      # 0.4276322829991841
x = list(range(2000000))
print(popend.timeit(number=1000))       # 1.2026999684167095e-05

import matplotlib.pyplot as plt
# 再进行计时试验
pop_zero_time = []
pop_end_time = []
for i in range(1000000, 10000001, 1000000):
    x = list(range(i))
    pop_zero_time.append(popzero.timeit(number=1000))
    x = list(range(i))
    pop_end_time.append(popend.timeit(number=1000))
plt.plot(range(1000000, 10000001, 1000000), pop_zero_time, 'o')
plt.plot(range(1000000, 10000001, 1000000), pop_end_time, 'o')

dict字典数据类型

字典常见操作数量级如下：

dict与列表不同，它是根据关键码（key）找到数据项，而列表是根据位置（index），前者无序，后者有序。

dict常用的取值与赋值性能都是$O(1)$。

重要操作contains(in)是判断字典中是否存在某个关键码(key)，这个性能也是$O(1)$。

更多的python数据类型操作复杂度在python官方算法复杂度网站