一、什麽是演算法 ( Algorithm ) ?

演算法是一组 step by step 用来解决问题、完成任务的指令，它的定义：

• 在有限时间内
• 在有限步骤内
• 一步一步解决一个问题的方法

输入 + 演算法 = 输出

二、演算法的目的

在程序中，可以使用回圈、if else 等逻辑，来定义程序的运作与流程控制，例如：

• 循序 / 非同步
• 分支
• 重复

而演算法可以简单地想像为复杂版的流程控制，用更复杂的逻辑，优化迭代出更有效率的方法，来解决问题。

演算法的目的是提升时间复杂度，更有效率地控制程序流程

三、演算法与运算思维

而在面对问题时，先别急着马上写程序，我们可以透过运算思维，先思考要如何拆解问题、整理自己的想法，再来转换成程序码表达。

运算思维 ( Computational Thinking ) 的步骤

1. 拆解：将问题拆解成较好处理的小问题 ( ex. Divide-and-Conquer )
2. 规律辨识：检视小问题，观察是否有规律或趋势存在
3. 抽象化：找出通则 ( 用数学符号表示 )
4. 演算法：设计、归纳出步骤来解决问题

四、透过猜数字游戏来了解演算法

接下来透过终极密码猜数字的游戏，来稍微感受一下演算法。

我们有 1 到 100 的数字 ( 有顺序性 )，你要如何用最快的方法猜到我心中设定的数字呢 ?

方法一：
按照 1、2、3、4 … 依序往下猜，每猜一次就剔除一个数字。这样地简易搜寻，其实就算一个演算法。
让我们试着用正式一点的「虚拟码」( Pseudocode ) 来表达：

set item be 90

for i (from 1 to 100) do
  if guess = item then
    print("Correct")
  end if
end for

但是，如果我设定的数字是 90，方法一就得猜 90 次才猜的到。最坏的情况要 100 次 !
那有没有更快速的方法呢 ?

方法二：
从中间的 50 开始应该是比较好的办法，虽然比较低，但是马上剔除一半的数字。
接下来从 75 开始猜 ( 50 到 100 的中位数 )，还是太低，但我们又去除掉了一半的数字 ( 50 到 75 )
就这样从中间的位置开始猜，每次可以剔除一半的数字，最多 7 次就可以猜到了吧 !

arr is an array from 1 to 100
let low be 0
let high be arr.length-1

set item be 90

while low < high do
  mid = (low+high)/2
  guess = arr[mid]
  if guess = item then
    return mid
  end if
  if guess < item then
    low = mid + 1
  else
    high = mid - 1
  end if
end while

方法二这样类似的搜寻方式，就是使用二进位搜寻 ( Binary Search ) 演算法来解决问题。

如果今天数字很大很大用 n 表示的话，最坏的情况下，方法一需要 n 个步骤才能完成，但方法二只需要 log n 个步骤就好。

原文连结：认识演算法 Algorithm ( 使用 JavaScript ) - Ted's Point 泰德观点