数据结构与算法之美

什么是数据结构和算法（一）

2020-06-11  本文已影响0人  焰火青春

1.1 数据结构和算法的概念

数据结构与算法相辅相成，不会孤立存在；数据结构是为算法服务的，算法是作用在特定的数据结构之上（如数组具有随机访问的特点，二分查找算法需要用数组来存储数据）。

数据结构是静态的，只是组织数据的一种形式，若不在它的基础上操作、构建算法、孤立存在的数据结构是没有意义的。

两种层面区分数据结构和算法

为什么学数据结构和算法

学好算法写出 时间复杂度高、空间复杂度高的垃圾代码也会越来越少，可以提升自己的代码性能，从而使自己的编程水平得到质的飞升。

建立时间、空间复杂度意识，写出高质量代码，能够设计基础架构，提升编程技能，训练逻辑思维，积攒人生经验，以此获得工作回报，实现你的价值，完善人生。

1.2 算法的五大特性

1.3 算法的提出

如果 a+b+c=1000，且 a2+b2=c^2（a,b,c 为自然数），如何求出所有a、b、c可能的组合？

1、方法一：

import time

start_time = time.time()
for a in range(1001):
    for b in range(1001):
        for c in range(1001):
            if a + b + c == 1000 and a**2 + b**2 == c**2:
                print(a, b, c)

end_time = time.time()
print('总耗时：', end_time-start_time)

运行结果如下：

0 500 500
200 375 425
375 200 425
500 0 500
总耗时：300.36014199256897

2、方法二：

import time

start_time = time.time()
for a in range(1001):
    for b in range(1001):
        c = 1000 - a - b
        if a**2 + b**2 == c**2:
            print(a, b, c)

end_time = time.time()
print('总耗时：', end_time-start_time)

运行结果如下：

0 500 500
200 375 425
375 200 425
500 0 500
总耗时：2.6143789291381836

同样的一道题，只是解题的思路不同，性能却是天差地别，这就是算法的魅力。

1.4 大 O 表示法

理论上来讲依靠执行时间就能衡量一个算法的效率，但若将两个相同的算法放在不同配置的机器上运行，那么单纯地依靠运行时间来衡量，显然是不合理的。那么应该用什么方式来衡量一个算法的效率呢？

算法效率衡量

假设计算机执行算法每一个基本操作的时间是固定的一个时间单位，那么多少个操作就有多少个时间单位。可能每台机器的单位时间不同，但是对算法来说进行多少个基本操作在规模数量级上是相同的，由此可忽略机器环境（配置/网络）对算法的客观影响。

大 O 表示法

下面我们通过两个小示例来理解什么是 大 O 表示法：

假设每行代码执行时间为：unit_time

示例一：

def func():
    a = 3               # 1
    b = 9               # 2
    for i in range(n):      # 3
        c = a*i + b         # 4
        return c

第1 、2 行代码各花费 一个 unit_time，而第 3 、4 行需要执行 n 次，各花费 n * unit_time，那么代码总执行时间 T(n) 即为：T(n) = （2n + 2）*unit_time。

示例二：

def func():
    a = 3               # 1
    b = 9               # 2
    for i in range(n):      # 3
        for j in range(n):  # 4
            c = a*i + b + j     # 5
            return c

那么代码总执行时间为：T(n) = (2n^2 + n + 2) * unit_time

根据上面两个例子的推导，可以得出一个规律：“所有代码执行时间 T（n）与每行代码执行次数 n 成正比”

将其总结成一个公式，即为 大 O 时间复杂度分析法

T(n) = O(f(n))

当 n 很大时，公式中的 低阶、常量、系数三部分几乎不左右增长趋势，常常忽略不计，而只取 最大量级。所以上述两个例子用 大 O 复杂度表示法表示为：T(n) = O(n)、T(n) = O(n^2)

注意：大 O 时间复杂度不具体表示代码真正运行时间，而是表示代码执行时间随数据规模增长的变化趋势，也叫做 ——渐进时间复杂度 （asymptotic time complexity），简称时间复杂度

1.5 时间复杂度分析

如何分析一段代码的时间复杂度，有三个方法：

# 若 T1(n) = O(f(n)),    T2(n) = O(g(n))，那么
T(n) = T1(n) * T2(n) = O(f(n)) * O(g(n)) = O(f(n) * g(n))

# 假设 T1(n) = O(n), T2(n) = O(n^2)，那么
T(n) = T1(n) * T2(n) = O(n * n^2) = O(n^3)

1、只关注循环次数最多的代码：

def func(n):
    a = 0
    b = 1
    c = 0
    for i in range(n):  # 循环 n 次
        c += i
    return c

第2/3/4 行都是常量级的执行时间，与 n 大小无关，因此对整个复杂度也没有影响。第 6 行循环执行了 n 次，因此总的时间复杂度为 O(n)，只需要关心循环次数最多的代码。

2、加法法则：总复杂度等于量级最大的那段代码的复杂度。

def func(n):
    sum_1, p = 0, 1
    while p < 100:
        sum_1 += sum_1 + p
        p += 1
        
    sum_2, q = 0, 1
    for i in range(n):
        sum_2 += i
        
    sum_3, i, j = 0, 1, 1
    for i in range(n):
        j = 1
        for j in range(n):
            sum_3 += i * j
            
     return sum_1, sum_2, sum_3

整段代码可以分为三部分，分别是求：sum_1、sum_2、sum_3 的值，每一部分的时间复杂度为：

总的时间复杂度为：O(1) + O(n) + O(n^2)，取最大量级为：O(n^2)

3、乘法法则：

嵌套代码的复杂度等于嵌套内外代码复杂度的乘积

def func(m, n):
    a, b, sum = 0, 0, 0
    for i in range(n):
        a = b + i
        for p in m:
            sum = a + p
            
     return sum

时间复杂度为：O(n) * O(n) = O(n^2)

最坏时间复杂度

分析算法时，存在几种可能的考虑：

最好时间复杂度并没有什么实际意义，往往需要特殊情况才能达到。平均时间复杂度是对这个算法的全面评价，反映了这个算法的本质，但是这种衡量没有保证，不是每个计算都能保证在这个操作内完成。因此我们更应该关心的是最坏时间复杂度，因为不管怎样在这个操作内，都能完成。

1.6 算法分析

现在我们已经知道什么是时间复杂度，也知道怎么用大 O 表示法，现在我们来分析下开头的两个示例各自的时间复杂度。

for a in range(1001):
    for b in range(1001):
        for c in range(1001):
            if a + b + c == 1000 and a**2 + b**2 == c**2:
                print(a, b, c)

我们只关注循环次数最多的，根据乘法法则，得出应为：T(n) = (n*n*n)*unit_time 即 O(n^3)

for a in range(1001):
    for b in range(1001):
        c = 1000 - a - b
        if a**2 + b**2 == c**2:
            print(a, b, c)

根据加法法则和乘法法则，可得出为：T(n) = (n*n + n*n) * unit_time 即 O(n^2)

随着规模的增长，显然第二个方法要比第一个方法快得多。

1.7 常见时间复杂度

执行次数函数举例 阶 非正式术语
12 O(1) 常数阶
2n+3 O(n) 线性阶
3n^2+2n+1 O(n^2) 平方阶
5log2n+20 O(logn) 对数阶
2n+3nlog2n+19 O(nlogn) 线性对数阶
6n3+2n2+3n+4 O(n^3) 立方阶
2^n O(2^n) 指数阶
n! O(n!) 阶乘阶
n^k O(n^k) k 次方阶

Tips：log2n（以2为底的对数）简写成 logn

常见时间复杂度对比

O(1) < O(logn) < O(n) < O(nlogn) < O(n2) < O(n3) < O(2^n) < O(n!) < O(nn)

常见时间复杂度对比

1.8 Python 内置类型分析

Python 给我们提供了一个 timit 模块，可以用来测试一小段 Python 代码的执行速度。

# 类 Timer 是测量小段代码执行速度的类
Timer(stmt='pass', setup='pass', timer=<timer function>)

# stmt参数是要测试的代码语句（statment）
# setup参数是运行代码时需要的设置
# timer参数是一个定时器函数，与平台有关

# timeit() 方法，执行速度的对象方法，number参数是测试代码时的测试次数，默认为1000000次，返回执行代码的平均耗时，一个float类型的秒数
timeit(number=1000000)

示例

from timeit import Timer

def test1():
    """列表相加"""
    l = []
    for i in range(1000):
        l = l + [i]

def test2():
    """append 尾部添加"""
    l = []
    for i in range(1000):
        l.append(i)

def test3():
    """列表生成式"""
    l = [i for i in range(1000)]


def test4():
    """range() 方法"""
    l = list(range(1000))

t1 = Timer('test1()', 'from __main__ import test1')
t2 = Timer('test2()', 'from __main__ import test2')
t3 = Timer('test3()', 'from __main__ import test3')
t4 = Timer('test4()', 'from __main__ import test4')

print('test1 总耗时：', t1.timeit(number=1000),  '秒')
print('test2 总耗时：', t2.timeit(number=1000),  '秒')
print('test3 总耗时：', t3.timeit(number=1000),  '秒')
print('test4 总耗时：', t4.timeit(number=1000),  '秒')

运行结果：

test1 总耗时： 2.0456191 秒
test2 总耗时： 0.10657389999999989 秒
test3 总耗时： 0.03904730000000001 秒
test4 总耗时： 0.016495899999999786 秒

list pop 测试

from timeit import Timer

x = list(range(2000000))
pop_zero = Timer("x.pop(0)","from __main__ import x")
print("pop_zero ",pop_zero.timeit(number=1000), "seconds")

y = list(range(2000000))
pop_end = Timer("y.pop()","from __main__ import y")
print("pop_end ",pop_end.timeit(number=1000), "seconds")

运行结果：

pop_zero  2.4630802 seconds
pop_end  0.00010299999999974219 seconds

列表常见操作的时间复杂度

操作 时间复杂度 操作 时间复杂度
index() O(1) index assignment 索引赋值 O(1)
append() O(1) pop() O(1)
pop(i) O(n) insert(i, item) O(n)
del list O(n) iteration 迭代 O(n)
contains(in) 包含 O(n) get slice [x:y] 分片 O(k)
set slice O(n + k) reverse() 翻转 O(n)
concatenate 两个列表拼接 O(k) sort() 排序 O(nlogn)
multiply 两个列表相乘 O(nk)

字典常见操作时间复杂度

操作 时间复杂度 操作 时间复杂度
copy O(n) get(item) O(1)
set(item) O(1) delete item O(1)
contains(in) O(1) iteration 迭代 O(n)

1.9 常用数据结构的算法

要想搞懂什么是数据结构，就要懂得什么是数据，什么又是结构？

Python 给我们提供了很多内置的数据结构类型：int、float、list、dict...，而有一些并没有提供，需要我们自己去定义，如：队列、栈等。

算法与数据结构区别

一个好的程序应该是在合适的数据结构基础上选择算法。一个合适的数据结构非常重要，比如：存储全世界人们的个人信息，如果用列表存储。那么遍历时其时间复杂度为 O(n)，而用字典存储，遍历其时间复杂度为 O(1)。

常用的数据运算

插入、删除、查找、修改、排序

常用的二十种数据结构和算法

在实际开发中，我们能够经常用到的有如下 20种，数据结构和算法各 10种：

上一篇 下一篇

猜你喜欢

热点阅读