Day 03：如何分析演算法？

上一回讲到两种搜寻演算法，一种是一个一个找，一种则是每次寻找都可以去掉一半的选项，好像有一种是明显比较快的做法，可是我们要怎麽表达这样的差异呢？

执行时间

一般在选择演算法时，我们会倾向用比较有效率的演算法，来优化时间或空间(例如记忆体)的运用，所以分析演算法时常常会讨论其执行时间(running time)[注1]，也就是字面上执行一个演算法需要多少时间的意思。

通常执行时间会以演算法进行的基本操作(primitive operations)[注2]次数来衡量，并且写法上利用大O符号(big-O notation)来表达。

以线性搜寻和二分搜寻来说，上回提到，用两种方式来玩定时炸弹的话，最多分别要猜100次和7次。

所以假设输入(例如数列、阵列长度或资料数量)为n时，线性搜寻最多需要进行n次操作，可以说线性搜寻的执行时间为O(n)，或称为它具有线性时间(linear time)；二分搜寻最多需要log2 n次操作，因此执行时间为O(log n)，亦即代表二分搜寻具有对数时间(logarithmic time)。

换句话说，大O符号表达的执行时间，是演算法在最坏情况下的执行时间，也就是花最多步骤、最慢的状态。

除了文字描述，我们还可以将这些关系用图表示：

图片来源 GeeksforGeeks

图中x轴代表输入大小，y轴代表所需时间(以操作次数衡量)，所以像图中O(n)这条线，就代表具有线性时间的演算法(如线性搜寻)在输入量变大时，它所需要的最长时间会如何增加。

这张图中包含了一些常见的演算法执行时间，右侧从上到下是最慢到最快的演算法比较，可以发现线条越陡(如O(n!))，演算法速度会越慢；线条越平(如O(log n))，则速度越快。

一路看名词解释到这边，想必心中累绩了很多疑问：

• 大O符号表达执行时间，那它有次或秒这类的单位吗？
• 之前说二分搜寻最多要log2 n次操作，为什麽大O符号的写法是O(log n)？这是写错还是省略？
• 为什麽一直以来都只讨论演算法花最多时间的情况？

後续的文章会接着讨论这些问题。

• [注1]如果看维基百科或一些文件可能会看到用时间复杂度(time complexity)这个词来表示执行时间。不过目前在查询相关资料的过程中，不管各种难度的课程或书籍里，其实还是用执行时间表达居多。因为这个词真的非常直接好懂，在认识演算法的一般讨论阶段我们会持续用执行时间这个表达。
• [注2]所谓基本操作是指演算法进行的一次简单步骤(例如赋值、相加、比大小)。一次操作不一定等於一行程序码，因为有些语言的语法在一行程序码中即可以进行多次操作(例如检查阵列里的每个数字)。