Day 25 - 演算法入门理解

前言

如果昨天是资料结构，那今天必然是来讨论演算法啦！

「演算法」是另一个会让许多非本科系的 developer 吓到的词汇，会觉得好像是很高深难懂的技术，应该都是 Google 等级的程序设计师才会用到吧？

但很神奇的是，明明是看起来这麽难的一个词汇，反而满常出现在媒体用语中的：

所以今天让我们来揭开演算法神秘的面纱吧！

跟昨天一样，今天主轴在於让大家初步认识演算法，没有要带着大家到处去刷题，如果有兴趣想用演算法来实际解题，欢迎到我的队友系列文，用 LeetCode 刷题来练习！

演算法是什麽？

由有限步骤所构成的集合，可以用於解决某一个特定的问题。

简单来说，有点像是「解决某个问题的步骤流程」，比如在生活上，我们要做家事洗衣服：

1. 把衣服放进洗衣袋
2. 把洗衣袋及其他衣服都丢进洗衣机
3. 放入洗衣精
4. 打开洗衣机电源
5. 选择洗衣模式，按下启动
6. 完成

没错，上述五个步骤就是为了完成「洗衣服」这个任务，的其中一种演算法！那有没有其它演算法？

有啊！衣服一定要自己洗吗？

1. 把衣服交给妈妈
2. 完成

所以，要完成一件事情，演算法不只一种唷！

这只是个范例，衣服请自己洗嘿！

其实，「如何把大象放进冰箱里」这个冷笑话，也是演算法的一种哦：

1. 把冰箱门打开
2. 把大象放进去
3. 把冰箱门关上

是不是步骤非常明确，而且能够解决问题呢XD

而在计算机科学的领域，演算法其实也是在做同样的事情，我们透过设计一连串的指令、动作，让电脑去执行，以便协助我们解决一些特定问题。

因此，就算是最简单的：我想条列出商品名称与对应的价钱，都是演算法的一种哦！

const products = [
    { name: 'TV', price: 12000 },
    { name: 'laptop', price: 25000 },
    { name: 'washing machine', price: 8000 },
];

products.forEach(product => console.log(`${product.name} 的价钱是 ${product.price}`));

执行结果

TV 的价钱是 12000
laptop 的价钱是 25000
washing machine 的价钱是 8000

演算法有好坏之分吗？

演算法其实就是「解决问题的方法」，所以这个问题应该改成：

解决问题的方法有好坏之分吗？

嗯。。。听起来是有的，只是我们不会说哪个方法绝对好，而是会用两个指标来衡量：动用的资源以及花费的时间。

而这两个指标放在计算机科学领域，就是你曾经听过的：

• 动用的资源：空间复杂度
• 花费的时间：时间复杂度

空间复杂度（Space Complexity）

空间复杂度就是，我用了多少记忆体空间来完成这件事。

比如要把一个阵列的顺序完全反转：

const reverseArr = (input) => {
    const output = [];
    input.forEach(item => output.unshift(item));
    console.log(output);
};

const arr = [1, 2, 3, 4, 5];
reverseArr(arr);

执行结果

[5, 4, 3, 2, 1]

可以看到为了达成「反转」这件事情，我多宣告了一个 output 阵列(花到额外的空间来放)，里面总共有五格，所以看起来 reverseArr 的空间复杂度是 5？

感觉怪怪的对吧！因为这个 output 会根据 input 进来的参数大小，而有所不同，因此我们不能够直接说空间复杂度是 5。

Big O notation（Big O 表示法）

我们使用 Big O notation，表达在「最坏情况下的复杂度等级」，如果像上例复杂度会随着 input 线性变动的，会用O(n) 来表示。

那如果不会随着 input 变动的会像这样：

const reverseArr = (input) => {
    let temp;
    const length = input.length;
    for(let i = 0; i<=length/2; i++) {
        temp = input[i];
        input[i] = input[length-i-1];
        input[length-i-1] = temp;
    }
    console.log(input);
};

const arr = [1, 2, 3, 4, 5];
reverseArr(arr);

执行结果

[5, 4, 3, 2, 1]

可以看到上面的写法，同样是为了达成「反转」这件事情，但我都在 input 本体上面操作，完全没有使用到额外的空间 output，也就是说，无论 input 的 length 有多大，这个函式都不会花费更多空间，称之为 O(1)。

其中 1 其实是代表常数，并不是真的只花 1 个空间，而是表达不会随着 input.length 变动

上面还有提到另一个重点是，Big O 代表的是「最坏情况」，会这样说是因为执行一段程序所花费的时间或空间，有可能有三种情况：

• 最佳情况
• 平均情况
• 最坏情况

比如说，我们要从阵列中找到一个元素，只要找到就可以不用继续找了：

const findElement = (input, element) => {
    const length = input.length;
    for(let i = 0; i<length; i++) {
        if (input[i] === element) break;
    }
};

const arr = [1, 2, 3, 4, 5];
findElement(arr, 3);

像上面这种程序，执行 findElement(arr, 3) 只要跑三次回圈就结束了，但如果执行 findElement(arr, 5) 就要跑五次回圈(虽然这个范例的空间复杂度都是一样的)。

因此我们会有上述三种情况，但计算机科学领域特别重视「上限」，才能够确保系统能够负荷最严重的状况，所以我们才会只强调「最坏状况」。

时间复杂度（Time complexity）

时间复杂度则是，我花了多少时间来完成这件事。

但这边有一点要特别注意，并不是单纯指花了几分钟来执行，因为每台电脑效能不一样，我们不是要衡量哪一台电脑比较快，而是「不同的程序写法在同一台电脑上执行」时的复杂度，因此我们会使用「执行了多少指令」来计算复杂度。

以刚刚上面的例子：

const reverseArr = (input) => {
    const output = []; // 1
    input.forEach(item => output.unshift(item)); // n
    console.log(output); // 1
};

const arr = [1, 2, 3, 4, 5];
reverseArr(arr);

可以看到我在注解的地方写上了复杂度等级，总共合起来是 n+2，我们只取次方最高的 n，因为当 input 增加时，变化最大的会是最高次方的 n，所以 reverseArr 的时间复杂度就是 O(n)。

时间与空间的权衡

可以看到刚刚同样是一个「反转」的任务：

• 一个有宣告额外的空间 output
• 一个没有，但花费的程序码变多

这代表时间与空间这两种「效能」是 trade-off，很多时候如果要空间就得花时间，要时间就要花空间。

简直跟租房子一样，要大套房就要增加通勤时间

而这大多时候没有正确答案，只取决於当下的需求，看是牺牲哪一边比较恰当。(当然如果资料量根本不大，基本上电脑也不痛不痒)

这个网站很视觉化呈现了，不同复杂度执行起来的差异：

结语

演算法也是大学资工系基础必修的一环，而且通常会跟资料结构相互配合，毕竟，使用怎样的资料结构，会直接影响到演算法的复杂度，因此资料结构+演算法一起学，报个 2 次铁人赛 60 天应该就可以了XD"

大多数人会觉得演算法很高深莫测，都是高手在用的，但其实经过今天的说明，不难看出其实，1+1 也是相加的一种演算法，演算法就只是达成目标所需的步骤而已。

之所以会看起来高大上，是因为如最後所说的，只有输入资料量庞大的时候，才容易看出演算法好坏的落差，而会碰到庞大输入量的，当然都是高手啦！

所以希望大家不要被「演算法」这个名字吓到，去了解它，并且试着思考自己的程序是否有更好的演算法，即便资料量不大，也能够在思考的过程中成长！

荆棘的路险峻
远绕的路疲倦
在不知道是否存在的交会点
寻一处沙洲

参考资料

演算法 MDN
big O cheat sheet