数据结构与算法学习笔记 2 （2018.10.06）

算法分析

• 两个主要方面：

                 正确性：算法的功能与问题要求一致？

                                 数学证明？可不那么简单...

                   成本：运行时间 + 所需存储空间

                                如何度量？如何比较？

• 考察：（P）=算法A求解问题实例P的计算成本

                                 意义不大，毕竟...可能出现的问题实列太多

                                 如何归纳概括？

• 观察：问题实例的规模，往往是决定计算成本的主要因素
• 通常：规模接近，计算成本也接近

                    规模扩大，计算成本亦上升

特定算法 + 不同实列

• ​​​​​​令（n)=用算法A求解某一问题规模为n的实列，所需的计算成本讨论特定算法A(及其对应的问题）时，简记作T（n）
• 然而，这一定义仍有问题...
• 观察：同一问题等规模的不同实列，计算成本不尽相同，甚至有实质差别
• 例如：在平面上的n个点中，找到所成三角形面积最小的三个点。

                    以蛮力算法为例，最坏情况下需枚举所有（n，3）种组合。

                    但运气好的话...可能只需一次就找到（三个点几乎在一条线上，面积无限接近于0）。

• 既然如此，又该如何定义T（n）呢？
• 稳妥起见，取T（n）= max { T（p） |   |p| = n }，亦即，在规模相同为n的所有实例中，只关注最坏（成本最高）者

特定算法 + 不同算法

• 同一问题通常有多种的算法，如何评判其优劣？
• 实验统计是最直接的方法，但足以准确反映算法的真正效率吗？
• 不足够！！！

                                不同算法，可能更适应于不同规模的输入

                                不同的算法，可能更适应与不同类型的输入

​​​​​​​                                同一算法，可能由不同的程序员，用不同程序语言，经不同编译器实现

​​​​​​​                                同一算法，可能实现并运行于不同的体系结构，操作系统...

• 为给出客观的评判，需要抽象出一个理想的平台或模型

​​​​​​​​​​​​​​                                不再依赖于上述种种具体的因素

​​​​​​​                                从而直接而准确地描述，测量并评价算法

TM：Turing Machine （图灵机）

 

• Tape   依次均匀地划分为单元格，各注有某一字符，默认为‘#’ 
• Alphabet   字符的种类有限
• Head  总是对准某一单元格，并可读取和改写其中的字符       

                    每经过一个节拍，可转向左侧或右侧的邻格

• State   TM总是处于有限种状态中的某一种

                    每经过一个节拍，可（按照规则）转向另一种状态

• Transition Function ：（ q，c；d，L/R，p）

                 若当前状态为q且当前字符为c,则当前字符改写为d；转向左侧/右侧的邻格；转入p状态，一旦转入待定的状态'h'，则停机

TM：Increase

• 功能：

                   将二进制非负整数加一

• 算法：

                   全'1'的后缀翻转为全'0'

                   原最低位的'0'或’#'翻转为'1'     

 

•