什麼是演算法？ - David J. Malan：英語精讀講義

What's an algorithm?

什麼是演算法？

In computer science,

在電腦科學中，

an algorithm is a set of instructions for solving some problem, 用詞

演算法是一套用於解決某個問題的指令，

step by step. 片語搭配

循序漸進。

Typically, algorithms are executed by computers,

通常，演算法是由電腦執行的，

but we humans have algorithms as well. 片語搭配

但我們人類也有演算法。

For instance, how would you go about counting the number of people in a room? 講解

例如，你打算如何計算一個房間裡的人數？

Well, if you're like me, 語氣意圖

好了，如果你和我一樣，

you probably point at each person,

你可能會指著每個人，

one at a time, 片語搭配

一次指一個，

and count up from zero. 片語動詞

從零開始數。

1 2 3 4 and so forth. 片語搭配

1、2、3、4 等等。

Well, that's an algorithm.

嗯，這就是一個演算法。

In fact, let's try to express it a bit more formally in pseudocode, 講解

事實上，讓我們試著用虛擬碼更正式地表達它，

English-like syntax that resembles a programming language.

虛擬碼是一種類似英文、也類似程式語言的語法。

Let n equal zero. 文法

讓 n 等於零。

For each person in room, 文法

對於房間裡的每個人，

set n = n + 1. 用詞

設定 n = n + 1。

How to interpret this pseudocode? 表達脈絡

如何解讀這段虛擬碼呢？

Well, line one declares, so to speak, 講解

可以這麼說，第一行宣告了

a variable called n and initializes its value to zero.

一個名為 n 的變數，並將其值初始化為零。

This just means that at the beginning of our algorithm,

這只是意味著在我們的演算法開始時，

the thing with which we're counting has a value of zero. 文法

我們用來計數的東西的值為零。

After all, before we start counting, 表達脈絡

畢竟，在我們開始計數之前，

we haven't counted anything yet. 文法

我們什麼都還沒數。

Calling this variable n is just a convention. 用詞

把這個變數叫做 n 只是個慣例。

I could have called it almost anything. 文法

我幾乎可以叫它任何名字。

Now, line two demarks the start of a loop, 用詞

現在，第二行標誌著迴圈的開始，

a sequence of steps that will repeat some number of times.

迴圈是一系列將重複若干次的步驟。

So, in our example, the step we're taking is counting people in the room.

所以，在我們的例子中，我們採取的步驟是計算房間裡的人數。

Beneath line two is line three,

第二行下面是第三行，

which describes exactly how we'll go about counting.

它確切地描述了我們將如何進行計數。

The indentation implies that it's line three that will repeat. 用詞

縮排意味著將要重複的是第三行。

So, what the pseudocode is saying is that after starting at zero, 講解

所以，虛擬碼的意思是，在從零開始之後，

for each person in the room, we'll increase n by one. 片語搭配

針對房間裡的每個人，我們會把 n 增加一。

Now, is this algorithm correct?

那麼，這個演算法正確嗎？

Well, let's bang on it a bit. 慣用語

讓我們來測試一下。

Does it work if there are two people in the room? 文法

如果房間裡有兩個人，這行得通嗎？

Let's see.

讓我們來看看。

In line one, we initialize n to zero.

在第一行，我們將 n 初始化為零。

For each of these two people, we then increment n by one. 用詞

對於這兩個人中的每一個，我們接著將 n 加一。

So, on the first trip through the loop, we update n from zero to one. 慣用語

所以，在第一次進入迴圈時，我們將 n 從零更新為一。

On the second trip through that same loop, we update n from one to two.

在第二次進入同一次迴圈時，我們將 n 從一更新為二。

And so, by this algorithm's end, 片語搭配

這樣，當這個演算法結束時，

n is two, which indeed matches the number of people in the room. 表達脈絡

n 是二，這確實與房間裡的人數相符。

So far, so good. 慣用語

到目前為止，一切順利。

How about a corner case though? 用詞

但如果遇到極端情況呢？

Suppose that there are zero people in the room, 文法

假設房間裡有零個人，

besides me, who's doing the counting.

除了正在計數的我。

In line one, we again initialize n to zero.

在第一行，我們再次將 n 初始化為零。

This time though, line three doesn't execute at all, 用詞

這次，第三行根本不會執行，

since there isn't a person in the room,

因為房間裡沒有其他人，

and so n remains zero,

所以 n 仍然是零，

which indeed matches the number of people in the room.

這確實與房間裡的人數相符。

Pretty simple, right? 語氣意圖

非常簡單，對吧？

But counting people one at a time is pretty inefficient too, no?

但是一次數一個人效率也很低，不是嗎？

Surely we can do better. 表達脈絡

我們肯定能做得更好。

Why not count two people at a time? 語氣意圖

為什麼不一次數兩個人呢？

Instead of counting 1 2 3 4 5 6 7 8 and so forth, 文法

為什麼要數 1、2、3、4、5、6、7、8 等等，

why not count 2 4 6 8 and so on.

而不數 2、4、6、8 等等呢。

It even sounds faster and it surely is.

聽起來甚至更快，而且確實如此。

Let's express this optimization in pseudocode. 用詞

讓我們用虛擬碼來表達這個最佳化。

Let n equal zero.

讓 n 等於零。

For each pair of people in room,

對於房間裡的每對人，

set n = n + 2.

設定 n = n + 2。

Pretty simple change, right?

非常簡單的改變，對吧？

Rather than count people one at a time,

我們不再一次數一個人，

we instead count them two at a time.

而是改成一次數兩個人。

This algorithm is thus twice as fast as the last. 文法

因此這個演算法比上一個快兩倍。

But is it correct?

但它正確嗎？

Let's see.

讓我們來看看。

Does it work if there are two people in the room?

如果房間裡有兩個人，這行得通嗎？

In line one, we initialize n to zero.

在第一行，我們將 n 初始化為零。

For that one pair of people, we then increment n by two.

對於那一對人，我們接著將 n 增加二。

And so, by this algorithm's end,

這樣，在這個演算法結束時，

n is two, which indeed matches the number of people in the room.

n 就是二，這確實與房間裡的人數相符。

Suppose next that there are zero people in the room.

接下來假設房間裡有零個人。

In line one, we initialize n to zero.

在第一行，我們將 n 初始化為零。

As before, line three doesn't execute at all, 表達脈絡

和之前一樣，第三行根本沒有執行，

since there aren't any pairs of people in the room,

因為房間裡沒有任何成對的人，

and so n remains zero,

所以 n 仍然是零，

which indeed matches the number of people in the room.

這確實與房間裡的人數相符。

But what if there are three people in the room? 文法

但是如果房間裡有三個人呢？

How does this algorithm fair?

這個演算法表現如何？

Let's see.

讓我們來看看。

In line one, we initialize n to zero.

在第一行，我們將 n 初始化為零。

For a pair of those people, we then increment n by two.

對於這些人中的一對，我們接著將 n 加二。

But then what? 表達脈絡

但是接下來呢？

There isn't another full pair of people in the room,

房間裡沒有另外完整的一對人了，

so line two no longer applies. 片語搭配

所以第二行不再適用。

And so, by this algorithm's end,

這樣，在這個演算法結束時，

n is still two, which isn't correct.

n 仍然是二，這是不正確的。

Indeed, this algorithm is said to be buggy, 用詞

事實上，這個演算法可以說是有 bug 的，

because it has a mistake.

因為它有一個錯誤。

Let's redress with some new pseudocode. 用詞

讓我們用一些新的虛擬碼來修正。

Let n equal zero.

讓 n 等於零。

For each pair of people in room,

對於房間裡的每對人，

set n = n + 2.

設定 n = n + 2。

If one person remains unpaired,

如果有個人落單，

set n = n + 1.

設定 n = n + 1。

To solve this particular problem,

為了解決這個特定的問題，

we've introduced in line four a condition, 用詞

我們在第四行引入了一個條件，

otherwise known as a branch,

也被稱為分支，

that only executes if there's one person we could not pair with another. 文法

只有當有一個人無法與別人配對時才會執行。

And so now,

這樣一來，

whether there's one or three or any odd number of people in the room, 文法

無論房間裡有一個人、三個人還是任何奇數個人，

this algorithm will now count them.

這個演算法現在都能將他們數出來了。

Can we do even better?

還能做得更好嗎？

Well, we could count in threes or fours or even fives and tens, 片語搭配

嗯，我們可以一次數三個、四個，甚至五個、十個，

but beyond that it's going to get a little bit difficult to point. 講解

但是超過這個數，就很難用手指了。

At the end of the day, 慣用語

歸根結底，

whether executed by computers or humans, 文法

無論是電腦還是人類執行，

algorithms are just a set of instructions with which to solve problems. 文法

演算法都只是用於解決問題的一套指令。

These were just three.

這裡只是其中三種。

What problem would you solve with an algorithm? 語氣意圖

你會用演算法解決什麼問題呢？