Placeholder Image

字幕列表 影片播放

已審核 字幕已審核
  • What's an algorithm?

    演算法(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.

    然後將它設成 0 作準備 (又稱初使化)。

  • This just means that at the beginning of our algorithm,

    這意思是我們的演算法,

  • the thing with which we're counting

    也就是我們的計數

  • has a value of zero.

    會從 0 開始。

  • 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,

    N 從 0 開始,

  • 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 初使化為 0。

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

    這數字正好符合這房間的人數。

  • So far, so good.

    到目前為止還不錯。

  • How about a corner case, though?

    不過如果看看極端的例子呢?

  • Suppose that there are zero people in the room,

    假設房間裡只有 0 個人,

  • besides me, who's doing the counting.

    當然在算人數的我不算在內。

  • In line 1, we again initialize n to zero.

    第一行裡我們還是將 N 初始化為 0。

  • 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 維持是 0,

  • 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 = 0。

  • 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 初使化為 0。

  • 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 初使化為 0。

  • 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 維持是 0,

  • which indeed matches the number of people in the room.

    這也符合房間裡的人數。

  • But what if there are 3 people in the room?

    但如果房間裡有 3 個人呢?

  • How does this algorithm fair?

    這演算法會如何?

  • Let's see.

    來看看。

  • In line 1, we initialize n to zero.

    第一行裡,我們將 N 初使化為 0。

  • For a pair of those people,

    每指到這裡面的一對人,

  • 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

    事實上我們會說 這個演算法有錯誤(bug),

  • 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,

    如果還有 1 個人沒辦法成對,

  • 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

    它只有在有 1 個人沒有被配對的情況下 才會執行。

  • we could not pair with another.

    它只有在有 1 個人沒有被配對的情況下 才會執行。

  • So now, whether there's 1 or 3

    所以現在,不管房間裡

  • or any odd number of people in the room,

    有 1 個或 3 個人、或是任何奇數個人,

  • 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?

    而你想要用演算法解決什麼問題呢?

What's an algorithm?

演算法(algorithm) 是什麼?

字幕與單字
已審核 字幕已審核

影片操作 你可以在這邊進行「影片」的調整,以及「字幕」的顯示

B1 中級 中文 TED-Ed 演算法 房間 人數 執行 重覆

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

  • 2058 279
    VoiceTube 發佈於 2013 年 10 月 19 日
影片單字