刘硕的技术查阅手册

Python 全栈开发学习笔记

0%

数据结构和算法概述

发表于 更新于 分类于
数据结构和算法思想的通用性异常的强大，在任何语言中都被使用，它们将会是我们编码生涯中伴随我们最长久利器（左膀右臂）。有一定经验的程序员最终拼的就是算法和数据结构。

计算机科学概述

首先明确的一点就是计算机科学不仅仅是对计算机的研究。虽然计算机在科学发展的过程中发挥了重大的作用，但是它只是一个工具，一个没有灵魂的工具而已。

所谓的计算机科学实际上是对问题、解决问题以及解决问题的过程中产生产生的解决方案的研究。例如给定一个问题，计算机科学家的目标是开发一个算法来处理该问题，最终得到该问题的解、或者最优解。所以说计算机科学也可以被认为是对算法的研究。因此我们也可以感受到，所谓的算法就是对问题进行处理且求解的一种实现思路或者思想。

形象化地理解算法

一个常胜将军在作战之前都会进行战略的制定，目的是为了能够在最短的时间切成本消耗最低的情况下获取最终的胜利。如果将编码作为战场，则程序员就是这场战役的指挥官，你如何可以将你的程序可以在最短且消耗资源最小的情况下获取最终的执行结果呢？算法就是我们的策略！

学习数据结构和算法的意义

数据结构和算法思想的通用性异常的强大，在任何语言中都被使用，它们将会是我们编码生涯中伴随我们最长久利器（左膀右臂）。有一定经验的程序员最终拼的就是算法和数据结构。

数据结构和算法思想也可以帮助我们拓展和历练编码的思维，可以让我们更好的融入到编程世界的角角落落。

算法分析概述

刚接触编程的学生经常会将自己编写的程序和别人的程序做比对，获取在比对的过程中会发现双方编写的程序很相似但又各不相同。那么就会出现一个有趣的现象：两组程序都是用来解决同一个问题的，但是两组程序看起来又各不相同，哪一组程序更好呢？

  • a+b+c = 1000，a**2 + b**2 = c**2（a，b，c 均为自然数），求出 a，b，c 可能的组合。

方法一：三层循环

1
2
3
4
5
for a in range(0, 1001):
    for b in range(0, 1001):
        for c in range(0, 1001):
            if a + b + c == 1000 and a**2 + b**2 == c**2:
                print(a, b, c)

方法二：两层循环

1
2
3
4
5
for a in range(0, 1001):
    for b in range(0, 1001):
        c = 1000 - a - b
        if c >= 0 and a**2 + b**2 == c**2:
                print(a, b, c)

评判程序优劣的方法

分别运行上面的两组代码。我们发现，方法二很快就运算除了结果，而方法一运行了好一会儿才把所有的解求出来。我们可以说，方法二的运行效率要高于方法一。

我们评定程序优劣的方式有这么几种：

  • 消耗计算机资源和执行效率（不推荐，无法直观表现）
  • 计算算法执行的耗时（适当推荐，因为会受机器和执行环境的影响）
  • 时间复杂度（推荐）

时间复杂度

评判规则：量化算法执行的操作/执行步骤的数量

最重要的项：时间复杂度表达式中最有意义的项

大 O 记法：就是使用时间复杂度衡量算法好坏的表现形式。

  • O(最重要的项)

观察下面的代码：

1
2
3
4
5
6
7
def sumOfN(n):
    theSum = 0    # 1
    for i in range(1,n+1):
        theSum = theSum + i   # n

    return theSum    # 1
print(sumOfN(10))

这个函数最开始初始化需要一步，循环 n 次需要 n 步，返回值还需要 1 步，总共需要 $n + 2$ 步。只取最有意义的一项，可知上面代码的时间复杂度为 $O(n)$。

计算下列代码的时间复杂度：

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

不难看出，这几行代码总共需要 $3+3n^2+2n+1$ 步，只保留最有意义的那一项，其时间复杂度为 $O(n^2)$。

常见的时间复杂度有：

  • $O(1)$ < $O(log\space n)$ < $O(n)$ < $O(nlog\space n)$ < $O(n^2)$ < $O(n^3)$ < $O(2^n)$ < $O(n!)$ < $O(n^n)$

数据结构

概念：对于数据（基本类型的数据 int，float，char）的组织方式就被称作为数据结构。数据结构解决的就是一组数据如何进行保存，保存形式是怎样的。

案例： 需要存储一些学生的学生信息（name，score），那么这些数据应该如何组织呢？查询某一个具体学生的时间复杂度是什么呢？（三种组织方式）

方式一，列表套字典：

1
2
3
4
5
6
7
8
9
10
[{
    'name': 'xxx',
    'score': 'xxx'
},{
    'name': 'xxx',
    'score': 'xxx'
},{
    'name': 'xxx',
    'score': 'xxx'
}]

方式二，列表套元组：

1
2
3
4
5
[
    ('name', 'score'),
    ('name', 'score'),
    ('name', 'score')
]

方式三，字典套字典：

1
2
3
4
{
    'zhangsan': {'score': 'xxx'},
    'lisi': {'score': 'xxx'}
}

三种组织形式基于查询的时间复杂度分别是多少？

时间复杂度一般都是基于最坏的情况的。列表套字典和列表套元组的两种结构基于查询的时间复杂度都为 $O(n)$，而字典套字典的结构基于查询的时间复杂度则为 $O(1)$。

我们看到，使用不同的形式组织数据，在基于查询时的时间复杂度是不一样的。

算法是为了解决实际问题而设计的，数据结构是算法需要处理问题的载体，二者联系机密。