B1 中級 13418 分類 收藏
開始影片後,點擊或框選字幕可以立即查詢單字
字庫載入中…
回報字幕錯誤
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:
1, 2, 3, 4 and so forth.
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.
For each person in room, set n = n + 1.
How to interpret this pseudocode?
Well, line 1 declares, so to speak,
a variable called 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.
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.
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.
For each of these two people,
we then increment n by 1.
So, in the first trip through the loop,
we update n from zero to 1,
on the second trip through that same loop,
we update n from 1 to 2.
And so, by this algorithm's end, n is 2,
which indeed matches the number of people in the room.
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.
This time, though, line 3 doesn't execute at all
since there isn't a person in the room,
and so, n remains zero,
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,
why not count
2, 4, 6, 8, and so on?
It even sounds faster, and it surely is.
Let's express this optimization in pseudocode.
Let n equal zero.
For each pair of people in room,
set 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.
For that one pair of people, we then increment n by 2.
And so, by this algorithm's end, n is 2,
which indeed matches the number of people in the room.
Suppose next that there are zero people in the room.
In line 1, we initialize n to zero.
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,
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,
we then increment n by 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.
Indeed this algorithm is said to be buggy
because it has a mistake.
Let's redress with some new pseudocode.
Let n equal zero.
For each pair of people in room,
set n = n + 2.
If 1 person remains unpaired,
set 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
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,
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?
提示:點選文章或是影片下面的字幕單字,可以直接快速翻譯喔!

載入中…

【TED-Ed】天哪!什麼是演算法? What's an algorithm? - David J. Malan

13418 分類 收藏
VoiceTube 發佈於 2013 年 10 月 19 日
看更多推薦影片
  1. 1. 單字查詢

    在字幕上選取單字即可即時查詢單字喔!

  2. 2. 單句重複播放

    可重複聽取一句單句,加強聽力!

  3. 3. 使用快速鍵

    使用影片快速鍵,讓學習更有效率!

  4. 4. 關閉語言字幕

    進階版練習可關閉字幕純聽英文哦!

  5. 5. 內嵌播放器

    可以將英文字幕學習播放器內嵌到部落格等地方喔

  6. 6. 展開播放器

    可隱藏右方全文及字典欄位,觀看影片更舒適!

  1. 英文聽力測驗

    挑戰字幕英文聽力測驗!

  1. 點擊展開筆記本讓你看的更舒服

  1. UrbanDictionary 俚語字典整合查詢。一般字典查詢不到你滿意的解譯,不妨使用「俚語字典」,或許會讓你有滿意的答案喔