《数据结构与算法Python语言描述》裘宗燕 笔记 第一章 绪论
《数据结构与算法Python语言描述》裘宗燕 笔记系列
该系列笔记结合PPT的内容整理的，方便以后复习，有需要的朋友可以看一下。
源码重新整理了
地址：https://github.com/StarsAaron/DS/tree/master
理解三个基本概念：
（1）问题
问题W是一个需要解决的具体的需求。
（2）问题实例
问题W的一个实例w是该问题的一个具体例子。
（3）算法
解决问题W的一个算法。
常见算法设计模式：
- 枚举
- 贪心
- 分治
- 回溯（搜索）
- 动态规划
- 分支限界
有关算法的研究只要关注的是算法的最坏情况和平均情况，而最好情况是不具研究价值的。
对于算法，没有放之四海而皆灵的设计理论或技术，只能借鉴
常量因子和算法复杂度
对于算法的时间和空间性质，最主要的是其量级和趋势。
算法开销跟问题实例的规模和实例本身有关。即使规模相同，处理不同实例的代价也可能不同。
算法的时间和空间代价
（1）空间代价
被解决实例的规模（以某种单位计量）为 n 时，求解算法所需要的存储空间按某种单位为 S(n)，称该算法的空间代价为 S(n)
（2）时间代价
被求解实例的规模为 n 时，求解算法所耗费的时间以某种单位计算为T(n)，称该算法的时间代价为 T(n)
与度量有关的三个概念（需要根据实际问题确定）：问题规模，空间单位，时间单位
算法的时间和空间代价
对抽象算法，通常无法做精确度量，只能退而求其次，设法估计算法复杂性的量级
例：求两个 n×n 矩阵乘积的常规乘法算法
主要运算：乘法（或加法）
空间单位：一个元素所占存储 s；时间单位：一次乘法所用时间 t
实例规模：矩阵一行（一列）的元素个数
时间复杂性：f(n) ≈ n×n×n ＝ n3（单位为 t）
空间复杂性：只考虑完成算法所需空间，包括结果的存储空间和计算中临时使用的辅助空间，这里约为 n2 （结果矩阵所需空间）
算法的时间和空间复杂性
考虑时空代价时，有些因素的准确值意义不大，例如：
- 时间或空间的基本单位
- 算法描述和实现的细节差异
在理论上考虑复杂性时，通常忽略常量因子。
例如，代价为 3 n2 和 100 n2 的算法，看作复杂性相同的算法
平均和坏情况
对同一问题的同样规模的实例，算法计算的代价也未必一样。
例如：在任意一个整数序列（如 Python 的 list）里找出第一个小于 0 的整数的位置，找不到时给出一个特殊值（例如 –1）
算法：顺序检查序列里的整数。将表大小 n 作为实例规模（很合理），对规模为 n 的实例，可能出现多种不同情况
1. 如果表中第一个元素就小于 0，计算中只需比较 1 次
2. 如果表中没有这样的整数，需要比较 n 次后才能给出结论
3. 其他情况下的比较次数在 1 和 n 之间
情况 1 是 好情况，意义不大（世界上没有那么多好事）。
情况 2 是坏情况，给出了保证：算法在该时间期限内一定能完成指定工作。这称为“坏情况时间复杂性”。还可以考虑 “平均情况时间复杂性”，这种复杂性依赖于实例的分布，需要做假设，而且不易计算
我们主要关心坏情况，有时关心平均情况
大 O 记法
算法的复杂性是算法实际代价的抽象
定义：如果存在两个正常数 c 和 n0，当实例的规模 n ≥ n0 后，某算法的时间（或者空间）代价T(n) ≤ c · f(n)（或 S(n) ≤ c · f(n) ），则说该算法的时间代价（或者空间代价）为 O(f(n))。
- 这个定义就是说，当实例的规模 n 充分大时，该算法所需时间（空间）不大于 f(n) 的某个常数倍
- 也说该算法的时间（或空间）代价的增长率为 f(n)
大 O 记法表示算法复杂性的上界（的量级），还可考虑下界、上确界、下确界。
复杂性增长的阶
O(1)< O(logn) <O(n) < O(n log n) < O(n2) （n的2次方） < O(2n)（2的n次方） 常数 对数 线性 n log n平方指数。
算法复杂性
大 O 记法表示一个算法的复杂性的上界
显然，一般性的上界没什么意义（可以任意大）
希望得到算法复杂性的上确界（的量级），即算法（遇到 难做的实例时）的坏情况能达到的上界。但常常不容易确定
如不能得到上确界，也希望得到算法的尽可能紧的上界
常量时间的复杂性用 O(1) 表示，线性复杂性是 O(n)，等等
易见，算法的复杂性分级就是（数学分析里）无穷大的阶：在规模 n 趋于无穷大的过程中，算法的开销增长的速度
算法复杂性高，其代价随规模增大而增长的速度快。重要吗？
例：设解决某具体问题的基本操作每秒做 10000次，实例规模是 100，
O(n) 的算法，所需时间可忽略不计（1/100秒）
O(n3) 的算法，所需时间是分钟的量级
O(2n) 的算法，所需时间是 4.0*1018 年的量级。（迄今为之的宇宙寿命估计为 1010 年的量级）
算法的复杂性反过来决定了算法的可用性：
如果一算法的复杂性较低，就可能用它去解决很大的实例
如果一算法的复杂性高，它只能用于很小的实例。可用性低
复杂性的计算（推导/估计）
现在考虑算法复杂性的“计算”（推导）循环算法的时间复杂性计算规则
1. 加法规则（顺序复合）
如果所考虑的算法（或其中片段）分为两个部分（或者多个部分），其复杂性是这两部分（或多部分）的复杂性之和
T(n) = T1(n) + T2(n) = O(T1(n)) + O(T2(n)) = O(max(T1(n), T2(n)))
由于忽略常量因子，加法等价于求大值
2. 乘法规则（循环）
如果算法中循环执行 T1(n) 次，每次循环用 T2(n) 时间，则
T(n) = T1(n)×T2(n) = O(T1(n)) ×O(T2(n))= O(T1(n)×T2(n))
复杂性计算实例
例：矩阵乘法，求两个 n×n 矩阵 m1, m2 的乘积 m 假设矩阵实现为两层的表，已准备好保存结果的 m
复杂性的计算，以矩阵的维数作为 n：
这个算法需要用一个 n×n 的结果矩阵，只使用了一个辅助变量（空间是常量），算法的空间复杂性是 O(n2)
问题：求 n 阶方阵的行列式的值
高斯消元法（一种算法）：
一列消元需要做 O(n2) 次乘法和减法
整个算法的复杂性是 O(n3)
采用行列式求值的定义求 n 阶行列式的值需要构造和计算 n 个 n-1 阶行列式
O(n!) 是比 O(2n) 更高的复杂性。
显然，这种算法没有太大实际意义，对很小的 n 就等不到计算结果了
递归算法的复杂性
对比较规范的递归算法，有清晰的理论分析方法前面行列式求值的递归算法的情况更复杂一些
设一个递归求解算法，将规模为 n 的问题实例归结到 a 个规模为 n/b 的子问题，每次递归时还需要做 O(nk) 的其他工作，那么
求解这一递归方程，可以得到下面结果：
注意：这里的 a、b 和 k 是常量，可以覆盖大部分典型情况
对前面行列式求值的示例，上面的解无效（上面公式中 a 和 b 为常量）
Python 程序的计算复杂性问题
Python 程序是算法的实现，因此也可以考虑其复杂性问题
需特别注意：Python 的很多基本操作不是常量时间的
（1）基本算术运算是常量时间操作
（2）组合对象操作有些是常量时间的，有些不是。例如：
a. 复制和切片操作，通常需要线性时间（O(n) 操作）
b. 表和元组的元素访问和元素赋值，是常量时间的
*计算复杂性
P-NP 问题被列为第一数学问题（传统的重大数学问题均列其后），这一情况很有趣，说明了数学界对“计算”的重要性的评价
原本人们认为计算太简单，是简单的数学
P-NP 问题说明计算中存在极深刻的理论，其价值不亚于任何传统数学领域的理论。它有许多有价值的推论，人们已在用各种数学工具去研究它，解决它的过程必定给数学带来许多收获
这一问题还有极其重大的实际意义
目前社会中几乎所有现代意义下的安全性，都依赖于 NP ≠ P。一旦有人证明了 NP = P，所有重要领域的许多系统（军事、金融、通讯等）都需要重建。同时我们也看到了计算能力的新边界，社会生产生活各方面的效率都可能大大提高
如果证明了 NP ≠ P，我们的生活环境不会有什么变化，但人类又进一步认识到自己能力的局限性
从来没有过一个数学问题如此深刻地影响（威胁？）整个人类社会
*NP 完全性问题
深刻的数学理论问题常显示出美妙的结构。P 与 NP 问题是这方面的典范。其中 有趣的问题之一是 NP 完全性
NP 问题类里有一个子集称为 NP 完全性问题（类），有如下结论
任意两个 NP 完全性问题可通过多项式时间复杂性的变换相互转换。
因此只需多项式时间就可以基于一个 NP 完全性问题的解得到另一个 NP 完全性问题的解：只需定义两个适当的多项式时间的翻译算法，就能解决另一 NP 完全性问题
任一 NP 问题都可通过多项式时间变换到某 NP 完全性问题
推论：任一个 NP 问题都可以通过多项式时间变换归结到某个 NP 完全性问题（也就是说，变换到任意一个 NP 完全性问题）
重要结论：
要证明 NP ≠ P，只需证明一个 NP 问题没有多项式时间算法
要证明 NP = P，只需证明一个 NP 完全性问题有多项式时间算法
*几个 NP 完全性问题
现在举几个典型的 NP 完全性问题
货郎担问题：设有 n 个村庄，村庄之间均有路相连，每条路有一定长度
要求找一条 短的路径，它经过每个村庄一次， 后回到出发点
货物打包问题：
设有多种货物，每种有一定重量。货车一台有确定载重量
要求选出一组货品，货车可以承载且在所有可能组合中重量 大
哈密尔顿圈问题：
在一个图中有一些点，有的点之间有连线
问图中是否存在一条环路，它经过每个点且只经过一次
数据结构
数据（Data）：计算机程序能处理的符号形式的总和信息（information）是一个含义更广泛的概念一种说法：数据是编码的信息（信息的编码表示）
数据元素（Data Element）
数据的基本单位，在程序中通常作为一个整体考虑和处理
数据结构（Data Structures）
一组数据元素（结点）按照一定方式构成的复合数据形式以及作用于这些元素或者结构上的一些函数或操作
一种数据结构是采用一套特定方式建立起来的一种数据组织结构（以数据元素为出发点），其特征包括几个方面（层次）：
（1）逻辑结构：数据元素之间有某种特定的逻辑关系。这是元素之间的抽象关系，与实现无关。抽象看，一个数据结构是一个二元组
B = ( E, R )
E 是一些种类的数据的集合，B 的元素取自集合 E
元素之间有关系 R，不同数据结构的元素之间的关系不同
（2）物理结构：数据的逻辑结构在计算机存储器中的映射（或表示），又称存储结构，或数据结构的存储表示
（3）行为特征：作用于数据结构上的各种运算。例如检索元素、插入元素、删除元素等一般性操作，还可能有一些特殊操作
具体实现问题：在编程语言里实现数据结构的具体方式和技术对 Python，还需理解其重要内置数据结构的实现和性质
Python 数据结构
正文序列类型 str
序列类型 list 和 tuple
集合类型 set 和 frozenset
映射类型 dict
标准库还提供了另一些数据结构定义，如 deque 等