//排版很丑，懒得改了
# 绪论(上)
## （a）计算
1.算法可以有0个输入
实例：比如随机数发生算法rand()，理论上讲不需要任何参数 ——邓俊辉
2.为什么我们认为效率最重要？
“算法分析”包括两个部分：正确性的证明、效率的界定。前者我们也会涉及但不作为重点，比如以bubblesort算法为例，介绍了正确性证明的一般性方法。而对于Huffman、Prim等算法正确性的证明，我所给的证明较之多数教材要严谨很多很多，若有兴趣可详见《习题解析》
实际上关于数学问题解法的正确性，人类已经研究了很长时间；但直到一百年前人们才意识到清晰地意识到，不同的方法还有效率的差异，甚至只将高效率的方法称作“算法”。作为一门学时有限的课程，我的定位首先立足于后一方面
非常有趣的是，在当下的应用环境中，正确性“似乎”的确已经不甚重要了。比如在处理实时数据流时，如果不能在时限内给出解答，将直接把这个问题“扔掉”不理，转而处理下一个。而对于深度神经元网络来说，不可能证明其做出的“每一个”决策都是正确的。
————邓俊辉
3.退化的输入是什么意思？
举例说明吧，
计算三角形面积时，三点共线是退化的情况。
对数组求和时，数组长度为0是退化的情况。
### 01-A-1：计算
1.计算是数据结构这门课的直接研究对象和内容，同时也是最终的研究目的和目标
2.我们需要研究在具体的计算的过程中，所蕴含的本质的内在的规律
3.也需要总结和挖掘出其中一般的方法以及典型的技巧
4.研究对象是规律和技巧；
研究目标是高效和低耗
5.推广：计算可以认为是整个计算机科学的研究对象和内容（计算机不过是研究计算的手段和工具，计算才是最终的研究目的和目标）
### 01-A-2：绳索计算机
1.通过几个实例看看所谓的计算有哪些特点和共性
2.在绳索计算机实例中，计算机是什么呢？就是设计好的长度为12的绳索(12=3+4+5)。这里的计算是什么呢？就是利用这个工具可以重复的机械的完成的一个过程
### 01-A-3：尺规计算机
1.在尺规计算机中，所用的工具是什么？
——欧式作图所允许的理想的直尺和圆规，即尺规计算机。这里的计算也是可以被分解为若干步骤
2.算法与算法之间可以互相套用
### 01-A-4：算法
1.小结：什么是一个算法？什么叫计算过程？
——计算过程可以抽象的认为是一种信息处理的过程，那么它首先必须借助某种工具，然后遵照一定的规则，而且必须能够以明确且机械的一系列简单基本的操作构成一个序列或过程
2.计算 = 信息处理；
计算模型 = 计算机 = 信息处理工具
3.从外延的角度刻画所谓算法需要具备哪些要素？
——输入、输出、正确性、确定性、可行性、有穷性......
### 01-A-5：有穷性
1.引入：Hailstone问题
2.有穷性：对于任何输入，都应该在有限步后退出返回
3.一个事实：程序 ≠ 算法
比如那些没有满足算法外延性的程序
4.算法的有穷性，即使是作为算法的一个侧面的要求，也不是那么简单的就能够确定的。这不是本门课研究的问题
5.我们的问题是：在正确性确定性可行性有穷性等外延特性都基本确定了以后，如何能够设计并且优化出更好的一个计算过程？一个对应的数据结构和对应的算法。
那么，首要的问题是：什么是好的算法，什么是好的数据结构？
### 01-A-6：好算法
1.什么是一个好的算法？一个好的计算过程？
——正确、健壮、可读...
但这些都不是最重要的
——效率：速度尽可能快，存储空间尽可能少
这意味着：我们不仅要能够指挥计算机进行计算，而且希望计算的速度尽可能快，同时消耗的资源(空间资源)尽可能地少
2.算法 + 数据结构 = 程序
但程序未必能够有效计算
不妨说：
(算法 + 数据结构)*效率 = 计算
## （b）计算模型
1.为什么从众多模型中选择了TM和RAM模型？
只选择这两个模型的另一个原因在于，就数据元素的访问方式而言，第二章的向量对应于RAM，第三章列表对应于TM，这样才能使课程讲授内容前后照应
——邓俊辉
2.虽然把算法细化到执行次数进行评价，但不同的步骤，需要的时间一样么？
需要的时间不一样，但是可以认为是常数倍。因此本课比较算法复杂度一般只比较数量级 ————助教
### 01-B-1：性能测度
1.回顾计算概念：如果从有效性和高效性来说，它的基本前提是数据结构和算法两个方面的有机结合，统称为DSA
2.自然，不同的DSA有好坏优劣之分(从效率而言)，我们必须要对其作定量度量
（如果我们要去改进一样东西，首先要懂得如何去测度它，如果都不知道它到底有多好，包括不知道它能够有可能有多好，甚至反过来，不知道它不能有多好，那么无从谈起如何去改进和优化它）
3.本节将引入一把尺子——理性、统一、分层次的尺度。后续会介绍如何运用这把尺子测度DSA的性能
### 01-B-2：问题规模
1.测度其实是算法分析的范畴。所谓算法分析有两方面：正确性；成本(性能)
不妨忽略空间开销，集中关注时间上
我们关注的是时间成本，那么我们该如何度量它？比较它？
2.思路从建模开始，记Ta(P)=算法a求解问题实例P的计算成本，简记为T(P)
由于同一个问题它的实例非常多(无数)，因而不可能遍历求解所有实例的成本，因而必须进行归纳，具体方法是划分等价类，即对任何一个问题无数的实例进行一定的粗分类，就某一类谈它的计算成本，那么，怎么进行分类呢？
——问题实例的规模，往往是决定计算成本的主要因素(一般是正相关)
3.概括言之：
规模接近，计算成本也接近
规模扩大，计算成本也扩大
### 01-B-3：最坏情况
1.采用划分等价类(以问题规模为依据)的方法后，对之前的公式改写为T(n)，n为问题规模。
即，我们把某一算法在求解问题规模为n的不是一个而是一大类实例的过程中，它们各自所需要的时间成本笼统记作T(n)
2.然而，这一定义仍有问题
即：同一问题等规模的不同实例，计算成本不尽相同，甚至有实质差别
3.既然如此，该如何定义T(n)呢
——我们应该更多的关注一个算法的最坏情况，即，在规模同为n的所有实例中，最应该关注最坏(成本最高)者
当然，也需要关注其他性能，但那是次要的
### 01-B-4：理想模型
1.在解决了特定算法的评价问题之后，需要进一步考虑对于同一问题有不同算法，如何评判其优劣？
2.实验统计是最直接的方法，但不足以反映算法的真正效率。这是因为实验统计总是不充分的。
3.综合起来，最后能够可行的方法只有一条：
为给出客观的评判，需要抽象出一个理想的平台或模型。从而不再依赖上述的种种限制因素，能够直接而准确的描述、测量并评价算法
引出：图灵机模型
### 01-B-5：图灵机
1.图灵机的要素：tape、alphabet、head、state、Transition Function
### 01-B-6：图灵机的实例
1.通过一个实例：对一个二进制非负整数数+1，来理解图灵机的整个运行过程
### 01-B-7：RAM模型
1.RAM:Random Access Machine
2.在可计算的意义上，RAM模型和图灵机完全对等。二者的共同点在于都拥有无限的空间
2.RAM的要素：
寄存器顺序编号且总数没有限制、每一基本操作仅需常数时间
3.与TM模型一样，RAM模型也是一般计算工具的简化与抽象，这使我们可以独立于具体的平台，对算法的效率做出可信的比较和评判
4.Why可以这样呢？这里关键是做了一个转换，即我们将算法所运行的时间转化为算法需要执行的基本操作次数，即从时间->次数，这样就将时间的统计问题转换为了次数的整体求和和估算问题
5.前面定义的T(n)转化为算法为求解规模为n的问题，所需执行的基本操作次数
6.这样的好处在于可以不用考虑硬件环境(独立)
### 01-B-8：RAM的实例
1.一个RAM模型实例：向下取整的除法
2.执行过程可以记录为一张表，表的行数即为所执行基本指令的总条数，能够客观度量算法的执行时间
2.小结：通过TM和RAM模型给出了一个清晰的尺度，这个尺度可以对算法进行度量。目前，我们只知道了尺子是什么，接下来，便是如何使用这把尺子，有何规则和技巧。
## （a）大O记号
### 01-C-1：主流长远
1.如果把前面引入的计算模型比作一把直尺，那么大O记号就相当于是这杆直尺上的刻度，我们不必过分追求精度，只需在定性和定量之间达到一个适度的折中，使得我们可以快速抓住DSA性能方面的要害和主要方面
2.渐进分析：随着问题规模的增长，计算成本如何增长？
注意：这里更关心足够大的问题，注重考察成本的增长趋势
——考察当n足够大时，对于规模为n的输入，算法需执行的基本操作次数
### 01-C-2：大O记号
1.基于前面所述，可以采用大O记号来表示T(n)，即T(n) = O(f(n))
2.与T(n)相比，f(n)更加简洁，但依然反映前者的增长趋势
3.大O记号的两个重要的处理手法：
常系数可忽略；低次项可忽略
4.注意点：大O的upper bound这条线，完全可以在常系数意义下，只要预先约定好的一个常系数c，经过放大能够完成构成上界的功能就够了
5.渐进分析的其他记号：
还可以从下界界定T(n)、还可以刻画T(n)的确界
### 01-C-3：高效解
1.在大O记号定义的尺度上，有哪些刻度呢？
常数复杂度：效率最高
对数复杂度：常底数无所谓、常数次幂无所谓；这类算法也非常高效，从渐进的意义上讲，对于任何一个多项式，哪怕次数很低，只要是正数，logn都可以在大O记号意义下被n的c次方所掩盖，所有它应该是低于任何多项式的一个复杂度，因而它本身无限接近于O(1)
### 01-C-4：有效解
1.多项式复杂度：由渐进的意义，可以界定为最高次的复杂度，其中特殊的是一阶线性复杂度
2.这类算法的效率也可以令人满意
### 01-C-5：难解
1.指数复杂度被归结为难解
2.这类算法的计算成本增长极快，通常被认为是不可忍受的，但还属于可计算的，不属于不可计算的
3.在指数和多项式之间，有一个明显的分水岭，可解的称存在有效算法的，反之，称不存在有效算法的
4.很多问题的O(2^n)算法往往显而易见，然而，设计出O(n^c)算法却极其不易，甚至，有时注定的只能是徒劳无功
### 01-C-6：2-SUBSET
1.2-Subset问题描述：
s包含n个正整数，s的和是2m
s是否有子集T，使得满足T的和是m？
2.直接算法：逐一枚举S的每一子集，并统计其中元素的总和
成本是2^n，指数规模
3.有没有更好的办法?
——没有，2-Subset is NP-complete
意即：就目前的计算模型而言，不存在可在多项式时间内回答此问题的算法。就此意义而言，上述的直觉算法已属最优
### 01-C-7：增长速度
1.可以把所有刻度汇集在一起，比如画在一张图上，可以获得各个刻度的直观印象
2.如果只观察局部，比如很小的情况，往往会得到错误结论
//不定期更新