清华大学学堂在线 邓俊辉老师 deng@tsinghua.edu.cn
第1章 绪论
(a)计算
计算=信息处理
对象：规律，技巧 目标：高效，低耗
何为计算：借助某种工具，遵照一定规则，以明确而机械的形式进行。
计算模型=计算机=信息处理工具
算法：
输入：待处理的信息（问题）
输出：经处理的信息（答案）
正确性：的确可以解决指定的问题
确定性：任一算法都可以描述为一个有基本操作组成的序列
可行性：每一基本操作都可实现，且在常数时间内完成
有穷性：对于任何输入，经有穷次基本操作都可以得到输出
例子：Hailstone问题
什么是个好算法：正确，健壮，可读，
效率
Data Structure + Algorithms = Programs
(b)计算模型
成本：运行时间+存储空间
特定算法+不同实例， 以及，不同算法+特定实例
图灵机 Turing Machine
包括：纸带，读写头，Transition Function
(q,c,d,L/R,p) 表示若当前状态为q且当前字符为c，则将当前字符改写为d，转向左侧/右侧的邻格，转入p状态，一旦转入特定的终止状态 ‘h’ ，则停机。
例子：图灵机实例
RAM模型概念
在这些算法中，算法的运行时间成正比于算法需要执行的基本操作次数。
RAM模型的实例
执行过程可以记录为一张表，表的行数即是所执行的基本指令的总条数，能够客观度量算法的执行时间。
图灵机(TM)，RAM等模型为度量算法性能提供了准确的尺度。
(c)大O记号(Big O Notation) Paul Bachmann 1894 同阶无穷小
Mathematics is more in need of good notations than of new theorems. ----Alan Turing
长远，主流
渐进分析 Asymptotic analysis:
当n>>2后，对于规模为n输入，
算法需执行的基本操作次数：T(n)=?? 需占用的存储单元数：S(n)=??
T(n) = O(f(n)) iff 存在 c>0，当 n>>2 后，有 T(n) < c*f(n) 。
O(1)：常数复杂度，2=2017=...=2011111111=O(1)
O( (log n)c ),对数多项式的复杂度 (poly log function)
对数：O(log n) ln n, lg n, ... , 与对数的底数无关
常底数无所谓： 对任意的a，b，有 log(a)n=log(a)b*log(b)n=O( log(b)n )
常数次幂无所谓：对任意的c>0, (log n)c=c*log n=O(log n)
对于对数多项式而言，取对数多项式里面次数最高的项即可
此类算法非常有效，因为复杂度无限接近于常数。
对任意的c>0, n充分大时，O(log n)小于n的c次方。
O(n的c次方)，多项式复杂度，polynomial function
O(2的n次方)，指数(exponential function) 指数爆炸
这类算法的计算成本增长极快，通常被认为是不可忍受的，从O(n的c次方)到O(2的n次方)，
是从有效算法到无效算法的分水岭，很多问题的O(2的n次方)算法显而易见，
然而，设计出O(n的c次方)算法却极为不易，甚至，有时注定地只能是徒劳无功。
2-Subset 问题，美国大选实例
对于2-Subset 问题，
直觉算法：逐一枚举S集中的每一个子集，并统计其中元素的总和，须2的n次方轮。
亦即：在最坏的情况下，必须花费2的n次方的时间，不甚理想！
直觉提出的问题：是否有更好的算法？
定理：2-Subset is NP-complete
not Polynomial, 非多项式时间内完成
即：就目前的计算模型而言，不存在可以在多项式时间内回答此问题的算法，就此意义而言
上述的直觉算法已经属于最优。
网友评论