Day-2 演算法介绍

演算法(Algorithms)

大致上来说，演算法为具有明确定义的计算过程，根据输入得到不同的输出，演算法就是一个将输入变成输出的一连串的计算过程，且须要具备五个特性。
输入 + 演算法 = 输出

来源:http://ms2.ctjh.ntpc.edu.tw/~luti/107-2/images/01.jpeg

1. 输入(input)：演算法会有零或一个输出。
2. 输出(output)：演算法会有一个或多个输出。
3. 有限性(finiteness)：演算法应在有限的步骤内完成。
4. 明确性(definiteness)：演算法的每一个步骤应明确而不含糊的。
5. 有效性(effectiveness)：演算法的每一个步骤应可被执行且有效。

一个演算法虽然我们非常注重他的效能，但也有一些比效能更为重要的议题需要注意

• 正确性(Correctness)
• 简洁性(Simplicity)
• 可维护性(Maintainability)
• 稳定性(Stability)
• 模组化(Modularity) : 让我们只要修改局部程序码，就能改变其功能
• 安全性(security) :
• 可扩充性(Scalability)

举例，Java虽然比C效率慢了许多，但由於提供物件导向和异常检查等功能，我们愿意牺牲一些效能换取到这些东西。

我们也可以将演算法是为解决特定问题的工具，例如我们要将一连串的没有顺序的数字进行排序，由小排到大，这是一个非常常见的问题，我们可以试着正式定义一下这个问题。

演算法问题定义

Input: 一连串正整数，从 到 所构成的集合{}
Output: 一连串重新排列的正整数 {}，且

举例来说，给定一连串正整数集合 {}，经过排序演算法会得到输出
{ }。对於这样的输入，我们称为这个输入为排序问题的实例(instance)，一般来说，一个问题的实例由输入所构成，且这些输入需要满足这个演算法的输入条件，以这个例子来说，输入的条件为正整数所构成的集合，我们给定的实例就必须皆为正整数。

要使用哪一种演算法，会取决於我们输入的多寡，或是根据电脑架构等因素，会影响到我们演算法的选择。

一个演算法要说他是正确的，必须要有以下条件 : 对於每一个输入的实例，都会输出如演算法预期的输出，且在输入完成时，该演算法就会随之停止。那这个演算法就可以称为能够解决某问题的正确演算法。对於一个不正确的演算法来说，会发生在输入完成後，演算法却没有停止，或是输出结果不符合预期。

要描述一个演算法，我们可以直接使用虚拟码进行描述，或是程序码，HDL等，唯一需要遵守的原则就是必须精确的描述每一个计算步骤的行为。

资料结构

资料结构是一种储存资料的方式，将这些资料以特定的方式进行阻止以方便我们进行修改和存取。当然，没有一种资料结构可以有效率的达成我们所有的目的，因此了解每一种资料结构的优势和劣势是十分重要的。

演算法效率(Algorithms Efficiency)

一个问题我们设计了不同的演算法是因为在不同的输入，硬体或是软件条件之下，会有不同的效率。

举例来说，针对排序，我们知道有插入排序演算法(insertion sort)，在排列n个物件的情况所需花费的时间大约为，为常数，且不受到n的影响。也就是说，这个演算法所需花费的时间大约和呈线性关系。

第二种为合并排序法(merge sort)，所需花费的时间大约为，为常数，且不受到n的影响。(的意思为)

我们假设插入排序法需要的时间为，合并排序法要花费的时间为，我们试着分析这两种演算法所需要花费的时间。

一般来说，插入排序法的常数，会小於合并排序法的。插入排序法所需要的时间受到n所影响，合并排序法受到所影响，我们可以试着比较，如果时，大约为3.2，时，大约为10，当时，大约为20。我们可以看到在n足够大时，合并排序法所花费的时间相较於插入排序法要少的非常多，但在n较小时，反而插入排序法比合并排序法还要来的快，因为常数的关系，n够大时，补偿了常数所产生的差异。不论比小多少，一定会在测资达到n笔时，合并排序法的速度大於插入排序法。

我们假设在一个环境下，有两部电脑，一台为A电脑，速度非常的快，执行插入排序法。另一台为B电脑，速度比A电脑还要慢，执行合并排序法。让这两部电脑去针对一个阵列进行排序，阵列中有一千万个元素，假定A电脑每一秒钟可以处理 笔指令，B电脑每一秒钟可以处理笔指令，所以，大致上我们可以说A电脑比B电脑快了1000倍。我们可以大致上计算一下A电脑和B电脑所需要花费的时间，如下图所示


由此可见，A电脑需要超过5.5个小时才能够完成排序的工作，而B电脑需要的时间只需要20分钟以内就能够完成排序的工作，可见一个好的演算法的重要性。

在资料量足够大时，电脑效能带来的影响大约就是一个常数因子而已，

对於θ和θ，总会存在一点n使得θ的增长率大於θ。

但这也不表示我们弃用一些低速的演算法，假设n要足够大时，才会导致θ的增长率大於θ，而这个n大到电脑无法负荷，也就是电脑的效能根本达不到n这样的资料量处理，这时候我们就会考虑使用这些低速的演算法，我们可以看到在资料规模够小时，θ是要比θ来的更加快速。

(p.s : 编辑器居然不支援LaTex...，还是我的问题XD 麻烦底下留言告知 感恩~)
参考资料: Introduction to algorithms 3rd