学苑撰文

难以想象，本来只会算0和1的「蠢玩意」，却能为我们解决生活上各式各样的问题。这个令电脑能够执行以0和1序列组成的指令，而变得聪明的神奇魔法，就是今天我想分享的主题 ── 「演算法」了。

演算法是甚么？

演算法（algorithm）是电脑科学非常重要的一部分。从定义来说，演算法是可以解决某些问题的有效方法之有限集合（finite set）。听起来好像很复杂，就让我举一个例子来说明吧！

以「洁手」为例，只要完成以下（Ａ）或（Ｂ）的各个步骤，就能解决「洁手」问题：

故此这些步骤可以称为「洁手的演算法」，因为演算法就是透过一系列动作解决特定的问题。

演算法如何运作？

基本上电脑能解决的问题，都是通过0 和 1的运算来实现。无论是基本的四则运算，即加、减、乘、除，还是复杂的任务例如以人工智能按用户喜好排序推荐电影等，背后都离不开演算法。为了令大家更容易明白演算法的运作，下文我将透过两个例子跟大家一探究竟。

1.    插入排序法

将数列分成已整理和未整理的两部分，在未整理部分中挑选一个数字，按数值大小放在已整理部分中正确的位置。重复这个步骤，直至未整理部分的项数变为0。

图1：插入排序法

2.    快速排序法

在数列中随机抽取一个数字，以此为参考值，将数列分成小于和大于该数的两个子数列。在子数列中分别重复这个步骤，直至完成排序。

图2：快速排序法

演算法与「时间复杂度」

以上两种排序法中，哪一种比较快？这就要看它们的「时间复杂度」了。

「时间复杂度」是描述演算法中输入项数（n）与运行所需时间之间关系的函数，通常以大O符号表示。

常见的「时间复杂度」例子：

   O（1）：    判断单双数（判断1位数 和100位数所需时间是一样的）

   O（n）：    加减法（100位数加减所需时间比1位数加减所需时间多100倍）

   O（n²）：   长乘法（100位数乘法所需时间比1位数乘法所需时间多100*100 = 10,000倍）

要留意的是，计算「时间复杂度」时会假设n非常大，因此我们只取增长速度最快的项（通常是最大指数的项），亦会忽略系数，例如：

                              O（3n³ + 2n + 5）→ O（3n³）→ O（n³） 

图3：不同时间复杂度的比较

插入排序法的平均时间复杂度为O（n²） ，而快速排序法的平均时间复杂度则为 O（n log n） 。           

回到上面的问题：两种排序法中到底哪种比较快？这就交给大家思考了！

作者简介：

吴沛熹，中四学生，就读于荃湾官立中学。于小学四年级加入香港资优教育学苑， 积极参与各种课程。对电脑十分感兴趣，希望能学到更多有关人工智能的知识，并以此为职业路向。平时亦喜欢做运动调剂身心，最常做的运动是篮球和排球。