数据结构 学习记录 2

B2 图灵机

To measure is to konw.

If you can not measure it,you can not improve it.

1.特定问题+不同算法：

同一问题通常有多种算法，如何评价器优劣？试验统计是最直接的方法，但不能反映算法的真正效率。因为：

• 不同的算法，可能更适应不同的规模或者类型的输入
• 同一算法，在不同的环境下得到的结论也不同

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

2.图灵机模型Turing Machine

• Tape：依次均匀的划分为单元格各注有某一字符，默认为“#”

• Alphabet：字符的种类有限

• Head：总是对准某一单元格，并可读取和改写其中的字符，没经过一个节拍，课转向左侧或者右侧邻格

• State：TM总是处于有限种状态中的某一种，每经过一个节拍，可按规则转向另外一种状态

• Transition Function：（q，c；d，L/R，p），若当前状态为q且当前字符为c，则当前字符改写为d；转向左侧/右侧的邻格；转入p状态一旦转入特定的状态h，则停机

  例子说明：
  
  第三步就已经完成了基本的要求了，为什么还要完成后面复位的要求了？因为这个过程可能会成为某个算法的一部分，每次调用此程序的时候就需要提供一个接口，这是一种规范

3.RAM（Random Access Machine）

• RAM作为计算模型来讲与图灵机模型是差不多的，都具有无限的空间，与图灵机的转换函数相比，RAM提供的是一些可执行的语句：
  

• 实例：向下取整的除法floor（）
  

• 总结：

• 与TM模型一样，RAM模型也是一般算法的简化与抽象，使我们可以独立于具体的平台，对算法的效率做出可信的比较和评判。

• 在这些模型中：算法的运行时间 与 算法需要执行的基本操作次数正相关；T(n) = 算法求解规模为n的问题，所需执行的基本操作次数。

要执行的基本操作次数正相关；T(n) = 算法求解规模为n的问题，所需执行的基本操作次数。