算法分析

  • 两个主要方面:

                 正确性:算法的功能与问题要求一致?

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

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

                                如何度量?如何比较?

  • 考察:(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'     

 

  •