Day-4 演算法分析概念

分析演算法

分析演算法，即是分析一个演算法的效率，来决定我们要使用哪一种演算法，而效率的分析方式通常会使用时间进行分析，忽略记忆体，或是频宽之类的议题。

在分析一个演算法时，我们通常会使用两种工具，一种是使用模型进行分析，另一种是数学方法，模型的部分，需要能够描述演算法使用的资源或是付出的代价，我们这里使用随机存取机(random-access machine, RAM)作为描述演算法所使用的资源或时间复杂度的模型，随机存取机常常应用在计算复杂性理论(Computational complexity theory)中。

图灵机（Turing Machine，TM）

图灵机（Turing Machine，TM），又被称为确定型图灵机。是一种抽象的数学计算模型。可以看作等价於任何有限次数数学逻辑运算过程的逻辑机器。

基本上。图灵机就是模拟人们使用纸笔计算数学问题的过程，而这样的过程我们可以定义为以下两个步骤

1. 在纸上写上或是擦掉一个记号
2. 把注意力从纸的一个位置移动到另一个位置

为了类比人类的运算过程，图灵建造出一种假想机器，由以下部分所组成

1. Tape : 表示一条一条无限长的纸带，划分出一格一格的小格子，每一个格子包含一个有限字母表的符号。
2. Head : 表示读写头，读写头可以在胶带上向左或是向右移动，能够读取当前格子的符号，或是改变当前格子的符号。
3. Table : 一套控制读写的规则，根据机器目前所处的状态以及读写头所读取到格子的内容来决定执行什麽样的动作，并改变暂存器的值，令机器进入新的状态，按照以下几个顺序告知图灵机
   1. 写入或是擦掉目前的符号
   2. 移动Head， 'L'向左， 'R'向右或者'N'不移动
   3. 保持目前的状态或是移动到下一个状态
4. 一个状态暂存器 : 储存图灵机目前的状态。图灵机的状态数目是有限的，并且含有一个特殊的状态，称为停机状态。
5. 状态转移方程序(Transition Function) : 举例: 表示如果目前状态为q,格子内的内容为字符c，则将目前格子的字符改成d，读写头转向左侧/右侧/停止，进入p状态，一但转入特定状态h，则停机。

举一个简单运用图灵机的例子
Example 1. 把纸带上储存的值加1

定义演算法:

1. 初始状态 : head指向最右边内容为'#'的储存格
2. head的移动与动作 : 如果指到的储存格内容为1，则将1变为0，并head向左移动。如果指到的储存格内容为0，则将0变为1，并head向右移动
3. 当head向右移动时不改变储存格上面的数值
4. 最终状态 : head向右移动，知道head指向'#'的单元格结束

状态表格 :

状态表达式 :
(1, 0, L)，如果Head碰到1，会将内容改成0，并Head向左移动
(#, 1, R)，如果Head碰到#，会将内容改成1，并Head向右移动
(0, 0, R)，如果Head碰到0，会将内容改成0，并Head往右移动
(#, #, N)，如果Head碰到#，会将内容改成#，并Head停止

随机存取机(random-access machine RAM)

在计算复杂性理论内，随机存取图灵机(random-access Turing machines)是一种变形的图灵机，可以想像成它是一个巨大的阵列，用来处理大小较小的复杂度演算法，特别是使用O的复杂度演算法.在随机存取图灵机上，多了一个特殊的指针磁带(储存格的概念)，大小是对数空间，字母是二进位单字(0和1)。图灵机有一个特殊的状态(state)，当指到这个状态而指针磁带的数字(二进位)是’p’时，图灵机会将工作磁带上面的指针移动到输入的第p个符号。

这特性让图灵机可以直接读取输入的特定字母，而不需要花时间去处理整条输入。这对使用少於线性时间的复杂度演算法来说，是必要的(因爲处理整个输入的时间是线性时间)^2

随机存取机和图灵机在计算能力上是等价的，但是在计算速度上有所不同

插入排序法分析(Insertion sort)

插入排序法所需花费的时间会根据输入资料的长度而增加，且根据输入集合已经被排序的程度，插入排序法可能需要花费不同的时间来排序两个相同长度的输入集合。一般来说，演算法所需要的时间与输入集合元素的多寡成正比，我们使用一种函数去描述一个演算法所需要的时间，因此，我们需要先定义所谓的运行时间和输入的规模。

输入的规模，根据我们研究的问题而有不同的定义，如在排序问题或是离散傅立叶转换，输入的规模会根据输入集合的元素个素，例如 : 有一个含有10个元素的阵列需要排列。对於其他问题，如两个数字的相乘，输入规模可能运用二进位的方式来表示输入需要的总位数。对於每一个问题，我们需要定义输入规模的量级。

一个演算法在特定输入所需花费的时间是指执行操作的步数或是操作数。我们使用这样的观点，来观察插入排序法的虚拟码，去评估这个演算法所需要花费的时间，假定第i行指令每一次执行时间为ci(虽然每一行可能需要不同的数量与时间)，ci为一个常数。这个观点是基於RAM模型的。

在下面的讨论中，我们由简单到复杂，由ci到具体的步数，写出插入排序法所需时间的表示式。

这个演算法所需要花费的时间即为times的加总。需要执行步且执行n次的一条述句需要的时间，以下为假设输入有n个元素的阵列插入排序法所需要的时间

即使我们给定的输入元素数量皆相同，演算法也可能因为输入阵列的排序情况而有不同的执行时间，例如在插入排序中，如果输入的阵列已经完成排序，则会出现最佳情况，我们可以发现在第5行程序码，，不会进入while回圈，我们可以计算出在这样的最佳情况下的运行时间

我们可以把简化为，简化成，把表示成，其中和根据所决定。因此，我们可以把表示成n的线性函数。

最糟的情况为整个阵列进行反向排序，我们必须将阵列中每一个元素和已经排序的子阵列中每一个元素进行比较，对，，在第5行的while

将以代入，得到以下

第6行和第7行也是如此，整理过後，得到整个运行时间

把有关於的部分用a, b, c取代过後，得到，a, b, c取决於，得到这是一个n的二次函数。

整理一下，我们得到

• 最佳情况 :
• 最坏情况 :

最坏情况与平均情况分析

对於一个演算法，我们通常只在意他的最坏情况，也就是对於长度为n的输入，演算法运行的最长时间。而这样的想法是基於以下三个理由

• 只要我们知道一个演算法运行时间的上界，我们就可以不必对运行时间做出各种复杂的猜测并可以预期这个演算法的不会超过这个时间。
• 对於某一些演算法来说，最坏情况是频繁出现的。
• 演算法的平均情况时常和他的最坏情况一样的糟糕，平均情况的运行时间和最坏情况往往是相同的，以插入排序法为例，平均情况得出来的时间规模也同样是n的二次函数。

增加量级概念

我们在上面用了一些抽象的方法使我们分析插入排序法更加的方便，把最坏的情况表示成，我们可以想像，当n无限的放大，可以发现对於整体二次函数的影响更大，也因此在分析演算法时，我们常常只在意演算法时间规模的最高次数项，直接将 当作 看待。我们大致上会将这样的表示法以Θ表示，後面我们会对这个符号进行精确的定义。

资料来源:Introduction to algorithms 3rd, 图片来自网路