1.1 计算机问题求解

程序一般是解决一类问题的，然后程序的每次运行解决该类问题的一个实例。

1.1.1 程序开发过程

实际问题-》数学模型（用数据结构来组织数据，用算法来操纵数据，是一种描述，可以分成说明性描述和操作性描述）-》程序-》反复调试

• 说明性描述：给出问题的严格定义，说明求解的是什么样的问题
• 操作性描述（算法）：给出具体解决方法的步骤【最重要的一步】

程序是算法的实现，程序更接近各种编程语言，而算法更接近与具体语言无关的计算过程。

1.1.2 一个简单的例子

问题：求任一个非负实数的平方根

• 说明性描述

由于平方根大多数为无理数，所以在有限步内无法求解精确的平方根，故而我们可以设定一个允许误差。

• 操作性描述

可以使用牛顿迭代法。

这里我们要断言：y 值序列收敛，极限是x的平方根。【这个断言有赖于数学证明，这里不说明了】

• 具体的python程序

1.2 交叉路口的红绿灯安排

1.2.1 问题分析与严格化

• 问题

考虑红绿灯如何安排，可以保证相应的允许行驶路线互不交错，从而保证路口的交通安全。
由于路口样式多种，所以我们可以先考虑一个简单的实例：
# 将其他无关的因素省略（道路宽度、人流量等），只保留行驶方向
图中C、E是单向道，其余是双向道路。

• 目标

基本目标：合理的红绿灯安排，保证同属一组的车辆可以同时行驶，不会有相互交错的行驶路线。
提升目标：组数要尽可能的少，每一组尽可能的大，提高路口的效率。

• 抽象表示

对可行方向的抽象表示：

对冲突的抽象表示：
# 由于问题中关于冲突的描述很模糊，比如在运行BD时，是否运行AD和ED，所以我们自己先选择一种定义。图中，相邻顶点之间定义为冲突。

1.2.2 图的顶点分组和算法

基本的方式是：首先枚举出所有可能的分组，然后筛选满足基本要求的分组，在从中选出分组数最小的分组。
这种方法的代价很高，组合数是顶点个数的指数函数。
下面考虑贪心算法：

• 总体概况

# 一种分组方式，也就是一组中有哪些顶点

• 新颜色着色处理的细节

将实例带入该算法中：

注意到算法中涉及到了一些图操作和集合操作。

1.2.3 算法的精化和Python描述

将上述的算法映射到具体的程序实现。
比如：

• 图的操作（这里先假定，后面再说具体的实现）

• 集合的操作

• 代码实现

注意到：颜色可以和new_group可以作为二元组加入group中，也可以只将new_group加入group中

1.2.4 讨论

• 解唯一吗？

不唯一，依赖于迭代中顶点的顺序。

• 求解算法与原问题的关系

注意到原问题中一个行驶方向允许属于不同的分组（比如右转弯），但是算法中不允许这种情况。
也就是说结果可以有限度的合并：

• 实际问题的复杂性

在实际问题中，远比我们的模型要复杂，比如说考虑到人流量的问题，以及冲突的定义、实际需要等等，这需要我们人工的去做大量的工作

1.3 算法与算法分析

1.3.2 算法的代价及其度量

可以有以下的印象：1s计算机运行十亿次，一台计算机有十亿存储单元。

度量的单位和方法

算法开销（时间或空间）定义为问题实例规模n的函数。
【其中n代表了实例的某些信息，比如数的大小、字符串的长短、要求处理的实例的个数等等】

与实例和规模有关的两个问题

• 实例规模n的选取

一般来说：选取输入数据的多少，比如数字串的长度、矩阵的元素个数。
有时候也使用矩阵的维数，这是由习惯决定的，与基于矩阵的个数描述，算法代价差了一个平方。

• 算法的特性+实例对算法开销的影响

所以此时我们可以考虑三个指标：

其中最少时间没有参考意义。
最多时间提供了一种保证，有价值。
平均时间，是对算法开销的一个全面评价，依赖于实例的分布，而实际问题的分布我们无法得知，所以不是一个好的指标。【比如说假设是正态分布，而实际问题的分布是其他】

常量因子和算法复杂度

由于环境的不同、程序中各种细节和分支结构，统计精确的具体次数是非常困难的，且实践意义有限。
所以我们主要是估计算法开销的量级。

• 大O记法

也就是说f(n)的增长速度不超过g(n)，这是一种保证。
需要注意的是，一般取时间复杂度为f(n)的上确界。因为：

理论上可以使用任意函数作为g(n),但是一般情况下使用：

• 算法的改进

算法如果只是加快了常量倍，则在时间复杂度上没有体现，但是在实际中也有作用。
算法复杂度提供了一种宏观的认识。

• 辨析

A1的时间复杂度高于A2，在同等的规模实例下，并不能保证A2算法执行的速度一定更快。
根据定义，只有在规模足够大的情况下，才能这么说。【这里可以考虑f(n)有各种次要的项的时间累加】

算法复杂度的意义

n趋近于无穷大时，算法代价增长的速度。
算法的复杂度越高，其实施的代价随着规模增大而增长的速度就越快。

1.3.3 算法分析

基本循环结构

• 基本的计算规则：

• 一个简单的例子（矩阵乘法）：

时间复杂度的推导：

• 高斯消元法

• 普通方法计算行列式的值

注意到平方项是从大矩阵中构建小矩阵所用的时间，这是递归上层和下层之间的连接部分，需要特别注意。

1.3.4 Python程序的计算代价

时间开销

dict插入键值对，最坏是O(n)，平均复杂度为O(1)
在表的最后加入和删除元素的操作效率高，在其他地方加入和删除元素的效率低。
普通算术运算复杂度是O(1)，用软件方法实现的大数运算复杂度大于O(1)

空间开销

组合数据对象通常没有预设的最大元素个数，可以根据元素个数的增长自动扩充存储空间，但通常不会自动缩小，即便元素变得很小了。
全局变量一般不会被回收内存，除非通过赋值将其抛弃。

Python程序的时间复杂度实例

其中第一种方法是O(n^2)的，因为每次迭代都涉及列表的复制。
Python几种创建list的方法的效率对比

程序实现和效率陷阱

假设算法的设计复杂度为O(n)，用语言实现的程序复杂度可能为O(n^2)，这就是效率陷阱。
可能把原来有用的变成基本无用的算法。

1.4 数据结构

问题求解的过程，可以看成把一种形式表示的信息-》运行程序-》另一种形式表示的信息
为了方便程序的处理，我们可以将信息表示A转换成一种良好的数据组织结构/数据结构。

1.4.1 数据结构及其分类

信息、数据和数据结构

数据（data）：计算机能处理的符号形式的总和。
数据元素（data element）：最基本的数据单元，比如二进制位，或者列表中的一项。
数据结构（data structure）：数据元素之间的结构，方便操纵数据和取用数据。其数据元素作为原子性的单元，可以任意简单或复杂，没有任何限制。

抽象定义与重要类别

抽象的说，数据结构包含一组数据元素和元素之间的逻辑关系，结构如下：

我们可以对R加以限制，分化出不同的数据结构：

可以认为图结构包含前面几类结构，前面几类结构可以看成图的受限形式。
正是因为元素之间的关系受限，可能存在一些有意义的特殊性质。

算法和程序中的数据结构

抽象数据结构-》映射到编程语言基本的数据类型-》通过编译器或解释器映射到计算机存储器中。

结构性数据结构和功能性数据结构

结构性数据结构：线性结构、树结构等，最重要的特征是他们的结构。
功能性数据结构：只有功能要求，支持元素的存储和使用，称为容器，比如栈、队列、字典等，不同的结构有不同的访问特性。
在实现的时候，通常把功能性数据结构-》映射-》结构性的数据结构来实现。

1.4.2 计算机内存对象的表示

内存单元和地址

64位计算机一次可以存取8个字节的数据。
CPU采用多级缓存结构和复杂的数据调度算法，使得连续访问一批单元的速度远高于在较大内存区域里同样次数的随机访问。
标准的浮点数，需要8个单元。

对象存储和管理

存储管理系统：建立对象-》安排存储空间，当对象无用时-》设法回收其占用的内存。
每个对象都有唯一的标识，id可获取对象标识，is和is not 可以比较标识从而确定是否为同一个对象。
在具体的系统中，可以使用对象的存储地址作为标识（一定是唯一的），因为不会有两个对象存放在同一存储位置。

对象的访问

知道了对象的标识（其中蕴含了对象地址），访问对象，这种操作可以在O（1）时间完成。
组合对象，其中包含一组元素，元素大小相同，通过下标访问对象中的元素也可以在O（1）的时间内完成。【比如数组】
组合对象，包含一组元素，其中元素的大小不同【考虑结构体】，通过元素的存储偏移量，访问对象的元素可以在O（1）时间完成。

对象关联的表示

• 基本类型的数据的内存表示方式由编程语言和计算机硬件确定，比如一个浮点数占据连续的8个字节单元。
• 复杂数据对象，包含一批数据元素（可能是基本类型的数据或者复杂对象），为了确定其内存表示，我们从两个方面来入手：数据元素的表示和数据元素之间关系的表示。

数据元素的表示视具体的情况而定，我们主要研究如何表示数据元素之间的关系。
有两种方式：

1. 存储位置的隐式表示/顺序表示，已知元素位置+大小-》确定序列中任一元素的位置。
2. 将联系保存为数据，这种方式可以表示任意复杂的关系，一般是链接结构。

# 字符串顺序表示
# 字符串顺序表示+保存长度来判断字符串的结束位置
# 书籍对象的链接表示【总体是链接表示，其实也用到了顺序表示】

1.4.3 Python对象和数据结构

Python变量和对象

变量本身也需要占用内存空间，变量关联着保存其值的对象，可以是基本整数、浮点数对象，也可以是组合类型的对象，如list等等，这种关联可以通过赋值来改变。

其中pi是变量名，其值保存了一个对象的引用，其中放了他真实的值。

• 这种实现内存的方式称为变量的引用语义，变量所需的存储空间大小一致（都只要保存一个引用）。

• 值语义：变量的值就保存在变量的存储区中，C语言等采用该种方式。

  Python对象的表示

  Python语言基于一套链接结构：

• 变量与其值对象的关联通过链接的方式实现

• 对象之间的联系也通过链接，比如list对象中记录10个字符串的链接关系。

Python对象可以有任意大的规模。

• 一个对比

python-》数据对象的具体表示方式（已经实现好了），折中的-》效率产生影响-》某些情况效率高，某些情况效率低
C语言-》自己实现数据对象-》效率高，但是细节多，编程复杂繁琐。

Python的几个标准数据类型

list-》常用
tuple-》不能改变，必须一下子构造出来，不能逐步构造。
dict-》键只能是不变对象，比如字符串、元祖，不变的组合对象也行，支持高效的O（1）检索

程序的错误

主要分成三种：逻辑错误、运行时错误和编译错误。
编译错误：一般是语法问题，编译器可以检查出来
运行时错误：程序运行时出现的错误，比如指针越界、除数为0等
逻辑错误：程序的运行结果不符合预期

两种基本的算法设计

枚举和选优：先枚举所有的情况，然后选择最优的解。
贪心算法：根据当时已知的局部信息，完成尽可能多的工作。这样做可以得到正确的解，但是可能非最优。（在复杂问题中考虑全局的代价太高，所以为了编写实际可用的算法，在最优方面做妥协）

确定性算法和不确定性算法

确定性算法，对于给定的输入，根据算法的描述可以产生唯一确定的一个动作序列，得到最终的解。【注意到即便有if、else判断语句也是确定性算法】
不确定性算法：动作序列不是唯一的，而是可选择的。

算法设计模式

需要注意的是，这些方法可以结合使用，作为建模的思路。

算法分析

分析出算法的空间和时间的消耗，作为评价算法的一种标准。