What's an algorithm? - David J. Malan

你的大脑也能运行算法 - David J. Malan

Translator: Andrea McDonough Reviewer: Jessica Ruby

翻译人员: Judy Z 校对人员: Catherine Gu

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 0:

从0开始：

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 0.

设n等于0。

For each person in room, set n = n + 1.

对于房间中的每个人，让n=n+1。

How to interpret this pseudocode?

如何来理解这些伪代码呢？

Well, line 1 declares, so to speak,

好吧，第一行，可以这么说，它声明了

a variable called n

变量n

and initializes its value to zero.

并且将它初始化为零。

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 2 demarks the start of 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 2 is line 3,

接着第二行的是第三行，

which describes exactly how we'll go about counting.

它描述了我们究竟怎样去计数。

The indentation implies that it's line 3

行首缩进表明这是第三行

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 1.

我们给n加1。

Now, is this algorithm correct?

那么，这种算法正确吗？

Well, let's bang on it a bit.

我们继续来讨论这个话题。

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

如果房间中有两个人，这个算法有效吗？

Let's see.

我们来看一看。

In line 1, we initialize n to zero.

在第一行，我们初始化n为零。

For each of these two people,

对于两人中的每一个人，

we then increment n by 1.

我们把n增加1。

So, in the first trip through the loop,

所以在第一次循环时，

we update n from zero to 1,

我们将n的值从零更新为1，

on the second trip through that same loop,

在第二次循环时，

we update n from 1 to 2.

我们将n的值由1更新为2。

And so, by this algorithm's end, n is 2,

在这个算法结束时，n的值是2，

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 1, we again initialize n to zero.

在第一行中，我们仍然将n初始化为零。

This time, though, line 3 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 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's thus twice as fast as the last.

所以这个算法比之前的算法快了两倍。

But is it correct?

但是它正确么？

Let's see.

让我们来看看。

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

假设房间中有两个人时算法正常工作吗？

In line 1, we initialize n to zero.

在第一行中，我们把n初始化为零。

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

对于这一对人，我们把n增加2。

And so, by this algorithm's end, n is 2,

所以，当算法结束时，n的值是2，

which indeed matches the number of people in the room.

它正好等于房间中的人数。

Suppose next that there are zero people in the room.

进一步假设房间中人数是0。

In line 1, we initialize n to zero.

在第一行中，我们把n初始化为零。

As before, line 3 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 3 people in the room?

但要是房间中有三个人时情况会怎样呢？

How does this algorithm fair?

这个算法会怎么公平处理？

Let's see.

让我们来看一看。

In line 1, we initialize n to zero.

这三人中的两人组成一对

For a pair of those people,

在第一行中，我们把n初始化为0，

we then increment n by 2,

我们把n增加2，

but then what?

但是然后情况如何？

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

房间里剩下的人中没有足够的人凑成一对，

so line 2 no longer applies.

所以第二行不再执行。

And so, by this algorithm's end,

所以，到这里算法结束，

n is still 2, which isn't correct.

这里n仍然是2，这是不正确的。

Indeed this algorithm is said to be buggy

事实上，这样的算法就是被称为有缺陷的，

because it has a mistake.

因为它有一个错误。

Let's redress with some new pseudocode.

让我们用新的伪代码来纠正这一错误。

Let n equal zero.

让n等于0。

For each pair of people in room,

对于房间中的每一对人，

set n = n + 2.

设n=n+2。

If 1 person remains unpaired,

如果有一个落单的人，

set n = n + 1.

设n=n+1。

To solve this particular problem,

为了解决这个特别的难题，

we've introduced in line 4 a condition,

我们在第四行引入了一个条件，

otherwise known as a branch,

或称为一个分支，

that only executes if there is one person

当只有一个人

we could not pair with another.

无法配对时执行。

So now, whether there's 1 or 3

所以，现在无论是1或3，

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 3's or 4's or even 5's and 10's,

我们可以3个、4个或甚至5个、10个的数，

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?

你会用算法解决什么问题？