>> [音樂播放]
國寶馬蘭所有權利。
好吧，歡迎回來。
因此，這是第4週，開始 其已經。
你還記得，上週，我們把 編碼一旁只是一點點
我們開始交談多一點 高層次，一樣的東西
搜索和排序，這雖然 有些簡單的想法，
代表的一類問題 你將開始解決特別
當你開始思考最終 項目和有趣的解決方案
可能有現實世界的問題。
現在是一個最簡單的冒泡排序 這樣的算法，它
通過這些小的數字工作 在一個列表中，或在一個數組中種
泡自己的方式到頂部， 大的數字移動一路下跌至
該列表的末尾。
>> 記得我們可以想像 一點點的冒泡排序
這樣的事情。
所以，讓我繼續前進，單擊“開始”。
我預選冒泡排序。
如果你還記得，高大的藍色 線代表大號碼，小
藍線代表小數字， 我們通過這一而再，再而
再次，比較相鄰的兩間酒吧 紅色，我們要交換
最大的和最小的，如果 他們秩序。
>> 因此，這會去，去，去 ，你會看到，較大的
元素使他們的方式 的權利，而較小的元素是
使他們的方式到左邊。
但我們開始量化 效率，
在此算法中的質量。
和我們說，在最壞 情況下，該算法採取了
大約多少步？
>> 因此n的平方。
什麼是N？
>> 觀眾：元素數目。
>> 國寶馬蘭因此n 數目的元素。
所以我們經常這樣做。
任何時候，我們要談論的大小 一個問題或大小的
輸入，或花費的時間量 以產生輸出，我們只
廣義的任何 輸入為n。
因此，早在第0週，數頁 在電話簿為n。
學生人數 在房間裡為：N。
所以在這裡，太，我們繼 這個模式。
>> 現在Ñ平方是不是特別 快，所以我們試圖做的更好。
因此，我們看著一對夫婦 其他的算法，其中
選擇排序。
所以選擇排序 有一點不同。
這幾乎是簡單的，我敢說， 由此開始的開始
我們的志願者名單，我只是再次 一次又一次經歷
列表，採摘最小 在一個時間元素，並把他或
她在列表的開頭。
>> 但是它也同樣，一旦我們開始思考 通過數學和更大的
圖片，想過多少次 我正想來回和背部
奔波，我們說，在最壞的情況下， 太多，選擇排序，那是什麼？
擺正Ń。
現在，在現實世界中，它可能 實際上是稍快。
因為再次，我沒有保持 回溯一旦我排序
最小的元素。
但是，如果我們想想n很大， 如果你的，做出來的數學
我在黑板上，與n的平方 減去的東西，一切
除了n個平方，一旦N 變得非常大，不
真正的問題一樣多。
因此，作為計算機科學家，我們的排序 視而不見較小
因素和只注重的因素 一個表達式，將會使
最大的區別。
>> 好了，最後，我們看了 在插入排序。
這是類似的精神，但 而不是通過迭代
選擇最小的元素之一，在 的時間，我只花了我的手
處理，我決定，所有 沒錯，你屬於這裡。
然後我轉移到下一個元素 並決定，他或
她屬於這裡。
然後，我和移動。
我可能會，一路走來， 以這些傢伙轉移
為他們騰出空間。
所以這是樣的心理逆轉 選擇排序，我們
所謂插入排序。
>> 因此，這些主題發生 在現實世界中。
僅僅在幾年前，當達到一定 參議員競選總統，
，在當時的CEO埃里克·施密特（Eric Sc​​hmidt） 谷歌，居然有機會
採訪他。
我們認為我們會分享此YouTube 夾你在這裡，如果我們可以將
音量。
>> [視頻回放]
>> 現在，參議員，你在谷歌， 我喜歡把總統
作為一個工作面試。
>> [笑]
>> 現在它是很難得到 一個工作作為總統。
你要通過 現在的嚴峻考驗。
這也很難在谷歌找到一份工作。
我們有問題，我們要求 我們的候選人的問題。
而這一次是從拉里·施維默。
>> [笑]
你們覺得我在開玩笑嗎？
就是這裡。
這是最有效的方式來 排序一百萬兩位整數？
>> [笑]
>> 嗯，呃 -
>> 我很抱歉。
也許我們應該 -
>> 不，不，不，不，不。
>> 這不是一個 -
確定。
>> 我認為冒泡排序 是錯誤的方式去。
>> [笑]
>> [歡呼和掌聲]
>> 來吧，誰告訴他這個呢？
確定。
>> [END視頻播放]
>> 國寶MALAN：所以你有它。
於是我們開始量化這些運行 倍，所以說話，用的東西
被稱為漸近符號，這是 剛剛提到我們轉向排序
視而不見，那些規模較小的因素， 只盯著運行時間，
這些算法的性能 為n隨著時間的推移變得非常大。
因此，我們介紹大澳大O 代表的東西，我們認為
作為一個上限。
巴里，而實際上，我們可以降低 比話筒一點點？
>> 我們認為這是一個上限。
因此，大O在n的平方手段 最壞的情況下，類似的東西
選擇排序 平方步驟Ń。
或類似的東西插入排序 將Ñ平方步驟。
現在像插入 排序，最壞的情況是什麼？
給定一個數組，什麼是最糟糕的 可能發生的情況，你可能會發現
自己面臨著？
>> 它是完全向後，對不對？
因為如果它是完全向後， 你所要做的一大堆工作。
因為如果你完全向後， 你要找到
這裡最大的元素，即使 它屬於那裡。
所以，你說，所有的權利， 時間在這一刻，你屬於這裡，
所以你離開單幹。
>> 然後你意識到，哦，該死的，我要 移動這種略小的元素
左側。
然後我再這樣做 一遍又一遍。
如果我來回走了，你 會有點感覺的表現
這個算法，我因為不斷 其他人倒在洗牌
陣列，以騰出空間。
因此，這是最壞的情況。
>> 與此相反 -
這是一個扣人心弦的最後一次 -
我們說，插入排序 是歐米茄的什麼？
什麼是最好的情況下運行 插入排序的時間嗎？
所以它實際上ñ。
這是我們離開的空白 在黑板上的最後一次。
>> 歐米茄的n，因為為什麼呢？
那麼，在最好的情況下，有什麼 插入排序將要移交？
好了，完全排序的列表 已經最小的工作要做。
但是，什麼是整齊插入排序 是，由於開始
決定，哦，你的號碼 一，你屬於這裡。
哦，什麼好運。
>> 你兩個數。
你也屬於這裡。
三，甚至更好， 你屬於這裡。
只要它得到的末尾 列表中，每次插入排序的偽代碼
我們走過口頭 最後一次，它的工作要做。
但選擇排序，相比之下， 不停地做什麼？
>> 持續通過列表 一遍又一遍。
因為關鍵的洞察力，只有 一旦你看了一路
列表末尾您可以肯定 選定的元素
確實是目前最小的元素。
因此，這些不同的心智模式結束 高達產生一些很現實世界
為我們的差異，以及這些 理論漸近差異。
>> 因此，只要回顧一下，然後，大O的n 平方，我們已經看到了一些這樣的
迄今為止算法。
大OŃ？
什麼是算法， 可以說是大O的n？
在最壞的情況下，它需要 一個線性的步數。
>> OK，線性搜索。
而在最壞的情況下，其中是 你要找的元素時，
應用線性搜索？
>> 行，在最壞的情況下， 它甚至不存在。
或者在最壞的情況下，它 一路到底，這是
加或減去一個單步的差異。
因此，在一天結束時， 我們可以說，它是線性的。
大O n的線性搜索， 在最壞的情況下，因為
元素甚至不存在，或者它 所有的方式在結束。
>> 嗯，大O n的日誌。
我們沒有講的很詳細，關於 這一點，但我們已經看到了這一點。
運行在所謂的對數 時間，在最壞的情況下？
>> 是啊，所以二進制搜索。
在最壞的情況下，和二進制搜索 可能具有元素中某處
中間，或某處 陣列內。
但你只找到它，一旦你 將列表的一半，在
半，一半的一半。
然後瞧，它的存在。
再或者，最壞的情況下， 它甚至不存在。
但你不知道它不存在 ，直到你達到這最後
最底層的元素減半 和減半減半。
>> 大O 1。
因此，我們可以大O 2，大O 3。
任何時候你想只是一個常數， 我們僅僅只是簡化排序
，大O 1。
即使如果現實的，它需要 2甚至100步，如果它是一個
恆定數量的步​​驟， 我們只是說大O 1。
什麼是算法， 在大O 1？
>> 觀眾：查找長度 一個變量。
>> 國寶馬蘭：尋找 一個變量的長度？
>> 觀眾：沒有，長度 如果它已經排序。
>> 國寶馬蘭：好。
OK，所以尋找的東西的長度 如果長度的東西，如
被存儲在一個數組中，一些變量。
因為你可以讀取該變量， 或打印變量，或
只是一般訪問該變量。
瞧，這需要恆定的時間。
>> 相比之下，回想起劃傷。
回想第一週的C， 僅調用printf和打印
屏幕上的東西可以說是 恆定的時間，因為它只是需要
一些CPU週期數顯示 該屏幕上的文字。
或等待 - 它嗎？
否則怎麼可能我們模型 printf的表現？
有人會不以為然， 也許這不是真的恆定的時間嗎？
在什麼意義上的printf可能運行 時間，實際打印字符串
屏幕，是 不變以外。
>> 觀眾：[聽不清]。
>> DAVID馬蘭：是啊。
因此，它取決於我們的角度來看。
如果我們真的想輸入 作為字符串的printf，
因此，我們測量的大小， 輸入的長度 - 所以姑且稱之為
該長度為n，以及 -
可以說，printf是本身的n大O 因為它會帶你n步
打印出與N 字符，最有可能的。
至少，我們假設的程度 也許它使用for循環
引擎蓋下。
>> 不過，我們將不得不看 編寫更好地理解它。
而事實上，一旦你們開始 分析自己的算法，你會
從字面上做到這一點。
眼球排序的代碼，並認為 - 所有的權利，我有這樣的循環
否則我這裡有一個嵌套循環， 做N事物n次，
可以按自己的方式的原因 通過代碼，即使它是
偽代碼，而不是實際的代碼。
>> 那麼歐米茄n的平方？
這是一個算法，在最好的 的情況下，仍然採取Ñ平方的步驟嗎？
是嗎？
>> 觀眾：[聽不清]。
>> 國寶馬蘭：所以選擇排序。
因為在這個問題確實減少 這樣的事實，再次，我不知道
我發現目前最小的，直到 我檢查了所有的混賬元素。
因此，歐米茄，我們說，正 只是想出了一個。
插入排序。
如果列表進行排序發生 已經在最好的情況下，我們只需要
通過一次， 在這一點上，我們肯定。
然後，可以說 是線性的，是肯定的。
>> 什麼歐米加1？
什麼，在最好的情況下，可能需要 固定數量的步​​驟？
所以線性搜索，如果你只是很幸運 和你要找的元素
在列表的開頭是正確的， 如果這是您在何處開始
線性遍歷該列表。
>> 而這，是真正的 一些東西。
舉例來說，即使二進制 搜尋歐米加1。
因為如果你得到真正的織補 幸運和咂嘴-DAB的中間
您的陣列是多少 你要買什麼？
所以，你可以得到幸運，以及。
>> 這其中，最後，ωn日誌n。
因此n日誌n，我們並沒有真正 談談，但 -
>> 觀眾：合併排序？
>> 國寶馬蘭：合併排序。
這是扣人心弦的最後時間， 我們提出，我們發現
視覺上，有算法。
並合併排序只是一個這樣的 基本上是更快的算法，該算法
一些這些傢伙。
事實上，合併潛在不僅在 當n日誌N，在最壞的
當n日誌Ń的。
而當你有這樣的巧合 歐米茄和大O是同樣的事情？
事實上，我們可以描述什麼 稱為θ，然而它是一個
少一些常見的。
但是，這只是意味著兩個界限， 在這種情況下是相同的。
>> 所以合併排序，這是什麼 真正歸結到我們嗎？
嗯，記得的動機。
讓我拉起另一個動畫 我們沒有看最後一次。
這一次，同樣的想法，但 它是一個更大一點。
而且我要繼續前進並指出 第一 - 我們有插入排序
左上角，然後選擇排序， 冒泡排序，一對夫婦的其他種類 -
外殼和快速 - 我們沒有談到 ，堆和歸併排序。
>> 因此，至少盡量集中你的眼睛 頂端3的左邊，然後
歸併排序，當我點擊 這個綠色的箭頭。
不過，我就讓所有的人都跑，只是 讓你感受到的多樣性
在世界上存在的算法。
我打算讓這個運行 短短的幾秒鐘。
如果你專注於你的眼睛 - 挑 算法，它只是一個專注於
秒 - 你將開始看到了 模式，它的實施。
>> 歸併排序，通知，就完成了。
堆排序，快速排序，殼 -
如此看來，我們推出三 最差算法上週。
但是，這是很好的，我們今天在這裡 看歸併排序，這是一個
容易的是看，甚至 雖然它可能會彎曲你的心
只是一點點。
在這裡我們可以看到多少 選擇排序吸。
>> 但在另一面，它是 確實很容易實現。
也許P設置3，這是一個 算法選擇實施
標準版。
完美的罰款，完全正確的。
>> 但同樣，當n變大，如果你 選擇來實現更快的算法
喜歡歸併排序，賠率是較大且 更大的投入，你的代碼僅僅是
要跑得更快。
您的網站更好的工作。
你的用戶會更快樂。
因此，有這些效果 實際上是給
我們一些更深層次的思考。
>> 因此，讓我們來看看什麼合併 排序實際上是一回事。
很酷的事情是，合併 排序僅僅是這一點。
再次，這是我們稱為什麼 偽代碼，偽代碼的存在
類似英語的語法。
和簡單 迷人的排序。
>> 所以輸入n個元素 - 只是意味著，這裡是一個數組。
它有著N個東西。
這就是我們說有。
>> 如果n小於2時，返回。
所以，這只是微不足道的情況下。
如果n是小於2，那麼它顯然 1或0，在這種情況下的事情
已經排序或不存在的， 所以剛剛返回。
有什麼可以做。
因此，這是一個簡單的情況下拔掉。
>> 否則，我們有三個步驟。
的左半部分的元素進行排序，排序 的右半部分的元素，
然後合併排序的一半。
這裡，有趣的是， 我樣的撐船，對不對？
有一種循環定義 該算法。
在什麼意義上是這樣的算法 定義圓？
>> 觀眾：[聽不清]。
>> 國寶馬蘭：是啊，我的排序算法， 它的兩個步驟“排序
東西。“於是引出了一個 的問題，以及什麼我要使用
排序的左半 和右半邊？
而這裡的美景，即使 再次，這是心態彎曲
一部分潛在的，你可以使用相同的 算法排序的左半。
>> 但是且慢。
當有人告訴你排序 左前衛，什麼是兩個
步驟將成為下一個？
我們將左半部分進行排序 左半邊和右
一半的左半邊。
該死，我怎麼排序，這兩個 半，或宿舍，現在呢？
>> 但是，這是確定的。
我們這裡有一個排序算法。
即使你可能會擔心 首先，這是一種無限
循環，這是一個週期，這是從來沒有的 將要結束 - 它是將
最後一次發生了什麼？
當n是小於2。
最終將要發生， 因為如果你繼續減半
減半在減半這些半，肯定 最終，你要結束
與僅有1或0個元素。
在這一點上，這種算法 說，你就大功告成了。
>> 所以，真正的魔力在這 算法似乎是在
這最後的一步，合併。
那個簡單的想法，只是合併兩個 的東西，這就是最終的
讓我們對數組進行排序， 比方說，8個元素。
所以，我有八個壓力球 在這裡，8個紙片，和一個
谷歌玻璃 -
這是我得到保持。
>> [笑]
>> DAVID馬蘭：如果我們可能需要8 志願者，讓我們來看看，如果我們能
玩這個了，所以。
哇，好。
計算機科學是越來越有趣。
好的。
所以如何你三， 最大的手在那裡。
四個在後面。
怎麼樣，我們會做你 三此行？
四個在前面。
所以，你八，上來吧。
>> [笑]
>> 國寶馬蘭：我其實 不知道它是什麼。
它是壓力球？
檯燈？
該材料？
在互聯網上？
>> 確定。
所以來了。
誰願意 -
保持上來。
讓我們來看看。
這使你的位置 -
你在第一的位置。
嗯，哦，等一下。
1，2，3，4，5，6，7 - 哦，好。
好吧，我們是很好的。
好吧，所以大家有一個座位， 但不是谷歌的玻璃上。
讓我排隊這些了。
你叫什麼名字？
>> 米歇爾：米歇爾。
>> 國寶馬蘭：米歇爾？
好吧，你得到的樣子 怪胎，如果這是確定的。
嗯，我也這樣做，我想， 只是一瞬間。
所有權利，備用。
我們一直試圖想出一個 使用的情況下，我們對Google玻璃
認為這將是有趣的只是做 當人們在舞台上。
我們會記錄世界 從他們的角度。
好的。
可能是谷歌意。
好吧，如果你不介意穿 這下一尷尬分鐘​​，
那將是美好的。
>> 所有的權利，所以我們這裡有一個數組 元素，該陣列，每
紙片在這些人“ 手，是目前排序。
>> 米歇爾：噢，那是太怪異了。
>> DAVID馬蘭：這是非常隨機的。
在短短的時刻，我們要嘗試 實施合併排序
看到這一關鍵洞察力。
這裡的技巧與歸併排序 的東西，我們沒有假設。
我們確實需要一些 額外的空間。
那麼，這是怎麼回事要特別 有趣的是，這些
附近有一座小傢伙要移動 位，因為我將假設
有一個額外的數組空間， 也就是說，在他們身後。
>> 所以，如果他們自己的椅子後面， 這是輔助陣列。
如果他們坐在這裡，這是 主陣列。
但是，這是一種資源，我們有 迄今沒有利用泡沫
排序，選擇排序， 用插入排序。
回想上週，每個人都只是 樣的洗牌。
他們沒有使用任何額外的內存。
我們的空間讓人們 移動周圍的人。
>> 因此，這是一個關鍵的洞察力。
有這種權衡，一般在 計算機科學，資源。
如果你想加快東西 如時間，你要
必須付出一定的代價。
那些價格是非常頻繁 空間的內存量或硬
您正在使用的磁盤空間。
或者，坦率地說， 程序員的時間。
多少時間，它需要你，人類， 真正實現多一些
複雜的算法。
但今天，權衡 是時間和空間。
>> 所以，如果你們能托起你 數字，所以我們可以看到，你
確實匹配4，2，6，1，3，7，8。
優秀的。
所以我要去嘗試，以協調 的東西，如果你們可以只
跟隨我的領導在這裡。
>> 所以，我要實現，首先， 第一步驟的偽代碼，這是
在輸入n個元素，如果n是 小於2，然後返回。
顯然，這不 適用，因此我們繼續前進。
因此，排序的元素的左半部分。
因此，這意味著我要專注我 這些只是一瞬間的關注
四個傢伙在這裡。
好吧，接下來我該怎麼辦？
>> 觀眾：排序的左半邊。
>> 國寶馬蘭：所以現在我有排序 這些傢伙的左半邊。
因為再次，假設自己的 的目標是要排序的左半邊。
你怎麼做到這一點呢？
只要按照上面的指令，即使 雖然我們做了一遍。
因此，排序的左半邊。
現在，我這兩個傢伙排序。
下一步是什麼？
>> 觀眾：排序的左半邊。
>> 國寶MALAN：排序的左半邊。
所以，現在這些，這個座位在這裡， 是一個大小為1的列表。
你叫什麼名字呢？
>> 公主DAISY：黛西公主。
>> 國寶馬蘭：黛西公主就在這裡。
於是她，因為已經排序 該列表是大小為1。
接下來我該怎麼辦？
OK，返回，因為該列表 大小為1，小於2。
那麼什麼是下一步？
現在你有樣的 原路返回，在你的心中。
>> 排序的右半​​邊，這是 -
你叫什麼名字？
>> LINDA：琳達。
>> 國寶馬蘭：琳達。
因此，我們應該做些什麼，現在 我們有一個列表的大小為1？
>> 觀眾：返回。
>> DAVID馬蘭：小心。
我們先回來了，現在的第三 一步 - 如果我描繪
現在擁抱的兩個席位，現在我 合併這兩個元素。
所以，現在不幸的是，元素 秩序。
但是，這就是合併過程 開始引人注目。
>> 所以，如果你們能站起來，只是 片刻，我需要你，在一個
此刻，加強你的椅子後面。
並且如果琳達，因為圖2是 小於4，你為什麼不
首先你來到我身邊嗎？
呆在那裡。
所以，琳達，你過來先。
>> 現在，在現實中，如果它只是一個數組 我們可能只是她的實時移動
這把椅子到這個地方。
所以，想像一下，採取了一些常數 步驟1的數。
而現在 -
但我們需要把你的 這裡的第一個位置。
>> 而現在，如果你能來到我身邊， 好了，我們要去
在位置2。
即使這感覺像 服用了一段時間，什麼是好的現在是
的左半部分 現在左半排序。
是下一步驟中，如果我們現在 進一步倒轉的故事？
>> 觀眾：右半邊。
>> DAVID馬蘭：排序的右半​​邊。
所以，你們必須這樣做，以及。
所以，如果你能站起來 只是一瞬間嗎？
你叫什麼名字？
>> JESS：傑西。
>> 國寶馬蘭：傑西。
OK，所以Jess是現在的左 的右半部分的一半。
所以她的大小為1的列表。
她顯然排序。
和你的名字嗎？
>> 米歇爾：米歇爾。
>> 國寶馬蘭：米歇爾顯然是 大小為1的列表。
她已經排序。
所以現在發生的魔力， 合併過程。
那麼，誰將會第一次來嗎？
顯然，米歇爾。
所以，如果你能過來。
我們現在為她提供空間 後面這把椅子在這裡。
而現在，如果你能回來， 我們現在有，是明確的，兩個
半，每個的大小為2 -
剛剛描繪的緣故，如果你 可以使一點點的空間 -
一個左半在這裡，其中一個 右半這裡。
>> 故事倒帶進一步。
什麼樣的步驟是下一個？
>> 觀眾：合併。
>> 國寶馬蘭：所以現在我們必須進行合併。
這樣就OK了，所以現在，令人欣慰的是，我們 剛剛釋放了四把椅子。
因此，我們已經兩次使用盡可能多的內存，但 我們可以給之間倒裝假摔
兩個數組。
因此，這數字是先來？
因此，米歇爾，很明顯。
所以來到我身邊，並採取 您的座位在這裡。
然後數字2是明顯 接下來，你來這裡。
第4號，6號。
再次，即使有一個 點點步行涉及，
說真的，這些可能發生的瞬間， 移動 -
OK，很好的發揮。
>> [笑]
>> 國寶馬蘭：現在我們 在相當良好。
的左半部分的整個 輸入現在已經被排序。
所有的權利，讓這些傢伙 我的優勢 -
它是怎麼結束了所有女孩子對 離開和所有的男孩在右邊？
>> OK，這樣的傢伙現在輪到。
所以，我不會走你通過 這些步驟。
我們可以看到，如果我們可以重新 相同的偽代碼。
如果你想提前去站起來， 你們這些傢伙，讓我給你話筒。
如果你不能複製什麼 我們在這裡只是做
列表中的另一端。
誰需要先發言， 基於該算法？
因此，解釋你在做什麼之前， 你做任何腳的動作。
>> 揚聲器1：好吧，這樣以來 我的左半部分
左前衛，我返回。
對嗎？
>> 國寶馬蘭：好。
>> 揚聲器1：然後 -
>> 國寶馬蘭：誰做 麥克風去下一個？
>> 揚聲器1：下一個號碼。
>> 揚聲器2：所以我的右半邊 的左半部分
左半邊，而我回來。
>> 國寶馬蘭：好。
你回來。
所以，現在你們兩個什麼是下一個向上？
>> 揚聲器2：我們希望看到誰較小。
>> DAVID馬蘭：沒錯。
我們要合併。
我們要用來合併空間 你進入，即使它們
顯然已經排序，我們將 遵循相同的算法。
那麼，誰去先回來？
因此，心情，和7。
現在的麥克風去 這些傢伙，好不好？
>> 揚聲器3：所以我的右半邊 左半邊，我Ñ小於
1，所以我只是要通過 -
>> 國寶馬蘭：好。
>> 揚聲器4：我的右半部分 右半邊的右半邊，而我
還一個人，所以我 要返回。
所以，現在我們合併。
>> 揚聲器3：所以，我們回去吧。
>> DAVID馬蘭：所以，你到後面去。
所以第一，然後按8。
而現在的觀眾，這是 步驟我們現在倒帶
備份在我們的腦海中？
>> 觀眾：合併。
>> 國寶馬蘭：合併左半邊和右 一半的原始左半。
所以，現在 -
只是為了讓這一點， 一點點的空間
你們之間的兩個傢伙。
所以，現在的兩個列表， 左，右。
那麼我們怎麼現在合併你們到 前排座椅嗎？
>> 3先行。
然後，很明顯。
然後，7，8。
OK，現在我們是誰？
>> 觀眾：沒做過。
>> 國寶馬蘭：沒做過，因為 顯然，有一個剩餘步驟。
不過，我之所以要使用這 像“倒帶在你的心中，行話”
這是因為這是真的 發生了什麼。
我們將通過所有這些步驟， 但我們暫停一排序
的時刻，潛水深入到 算法，停頓了一會兒，
潛水深入算法，並 現在我們要排序退我們
頭腦和撤消所有這些層 排序，我們已經暫時擱置。
>> 所以現在我們有兩個列表大小為4。
如果你們能站起來，最後一次 和這裡一點空間
清楚，這是左 原來，一半
右原來的一半。
誰是第一個數字，我們 需要拉進後面？
米歇爾，當然。
>> 所以我們把這裡的米歇爾。
2號？
2號上回好。
編號3？
優秀的。
4號，5號，6號， 7號和8號。
>> OK，所以覺得好像有很多 步驟，是肯定的。
但現在讓我們來看看，如果我們不能確認 那種直觀的，這
算法從根本上，特別是作為 n變真的大，正如我們已經看到的
與動畫，是 從根本上更快。
因此，我要求這個算法，在最壞的 的情況下，即使在最好的情況下，
是大O n次日誌n。
即，存在的一些方面，這 算法需要n個步驟，但
還有另一個方面某處 該迭代循環，
需要記錄n步。
我們可以把我們的手指放在什麼那些 兩個數字是指什麼？
嘛，哪裡 -
麥克風到哪去？
>> 揚聲器1：將日誌n是 我們一分為二 -
除以二，本質上。
>> DAVID馬蘭：沒錯。
我們看到在任何時候，任何算法，從而 目前為止，這種模式
分裂，分化，分裂。
它一般會降低 東西是
對數，底數2。
但是，真的有可能是任何東西， 但登錄基地2。
>> 現在什麼的n？
我可以看到，我們把你 傢伙 - 你分，分，
分，分。
哪裡到底從何而來？
>> 因此，它的合併。
因為去想它。
當你合併在一起，八人 其中一半是一套四
，而另一半是另一種 四，你怎麼去
做合併？
好了，你們做到了 相當直觀。
>> 但是，如果我不是做這一點更 有條不紊，我可能已經指向
最左邊的人先用我的左手 手，指著最左邊的人
用我的右手，有一半 只是後來走過
名單，指著最小的元素 每一次，我的手指移動和
超過所需要的整個列表。
但是，什麼是這個合併的關鍵 過程是我比較這些對
的元素。
從右側的一半，從左邊 半，我從來沒有一次回溯。
>> 因此，合併本身正 不超過n個步驟。
多少次我有 合併做到這一點呢？
嗯，不超過n，我們只是 看到最終的合併。
因此，如果你做的東西，需要 日誌n步n次，反之亦然，
這將會給我們日誌n n次。
>> 這是為什麼更好？
那麼，如果我們已經知道該日誌 n是大於n - 對嗎？
我們看到在二進制搜索，電話簿 例如，日誌n為絕對
優於線性。
因此，這意味著Ñ次日誌n是 肯定比n倍另一個
N，又名Ń平方。
這就是我們最終的感覺。
>> 這麼大的掌聲，如果 我們可以為這些傢伙。
>> [掌聲]
>> 國寶馬蘭：你的臨別禮物 - 你可以保留的數字，
如果您想。
和你的臨別禮物，像往常一樣。
哦，我們會送你 的畫面，米歇爾。
謝謝。
好的。
幫助自己的應力球。
>> 讓我拉起來，在此期間， 我們的朋友羅布·鮑登提供
有些不同的觀點，在此， 因為你可以想想這些
步驟發生在一個有點 不同的方式。
事實上，建立羅布的 向我們展示了，假設我們
已經做了瓜分 大名單分為八個小名單，
每個大小為1。
>> 所以，我們要改變一個偽代碼 點點得到的只是排序
如何合併工程的核心理念。
但運行時間是什麼 他做的仍然是
將是相同的。
再次，在這裡設置的是，他的 開始有八個列表的大小為1。
所以你錯過了他的部分 實際上做日誌日誌N，N，日誌N
除以輸入。
>> [視頻回放]
>> 這是它的第一個步驟。
步驟二，反复 合併成對的名單。
>> 國寶馬蘭：嗯。
只有音頻 出我的電腦。
讓我們試一次。
>> 只是隨便挑 - 現在，我們有四個名單。
了解之前。
>> 國寶馬蘭：我們走吧。
>> 合併108和15，我們最終 與列表15，108。
合併50和圖4中，我們 結束與4，50。
合併8和42，我們 結束與8位，42。
和合併23日和16日，我們 結束與16​​，23。
>> 現在我們的名單是大小為2。
請注意，各 四個列表進行排序。
因此，我們就可以開始合併 再次對列表。
合併15和108和4和50，我們 先取4，然後15，然後
50，那麼108。
合併8，42，16，23，我們先來 8，然後16，然後23個
然後42。
>> 所以，現在我們只有兩個列表大小 4，其中每一個進行排序。
所以，現在我們合併這兩個列表。
首先，我們4，然後我們把 8，然後我們採取了15，然後16，然後
23，42，50，108。
>> [END視頻播放]
>> 國寶馬蘭：同樣，請注意，他從來沒有 觸動了杯一次以上
之後超越它前進。
所以他從來不重複。
所以他總是移動到一邊， 這就是我們得到了我們的Ñ。
>> 為什麼不讓我拉起一個動畫 我們前面看到的，但是這一次
只專注於合併排序。
讓我繼續前進，放大 在此。
首先，讓我選擇一個隨機輸入， 放大這一點，你可以看到排序
我們採取了什麼是理所當然的，早些時候， 合併排序，實際上做。
>> 因此，發現，你得到這些半或 這些宿舍或這些八分之
問題一下子 開始採取良好的形狀。
然後，最後，你看到 最末端，咣當，
一切都合併在一起。
>> 所以這些都只是三種不同 採取同樣的想法。
但關鍵的洞察力，就像鴻溝 和征服的第一類，
是我們決定以某種方式劃分 問題變成大的東西，進入
排序相同的精神的東西， 但更小的和更小的和更小的
和更小的。
>> 現在，另一個有趣的方式來排序認為 這些，即使它不是
打算給你相同的直觀 理解，是
下面的動畫。
所以這是一個視頻的人放在一起 相關不同
與各種不同的操作的聲音 插入排序，歸併排序，
其他幾個。
因此，在某一時刻，我會打遊戲。
它是大約一分鐘長。
即使你仍然可以看到 發生的模式，這時候你可以
也聽到這些算法如何 不同的執行與
有所不同的型態。
>> 這是插入排序。
>> [提示音播放]
>> 國寶馬蘭：再次嘗試 每個元素插入
到屬於它的地方。
這是冒泡排序。
>> [提示音播放]
>> 國寶馬蘭：您可以排序的感覺 如何相對較少的工作，它在做什麼
對每一個步驟。
這是沉悶聽起來像。
>> [提示音播放]
>> 國寶馬蘭：這是選擇排序， 我們選擇我們想要的元素
再次經歷一次又一次 並把它的開始。
>> [提示音播放]
>> 國寶馬蘭：這是歸併排序， 你可以真正開始感覺。
>> [提示音播放]
>> [笑]
>> 國寶馬蘭：名為gnome的東西 排序，我們沒有看過。
>> [提示音播放]
>> 國寶馬蘭：所以讓我看，現在， 你希望是由分心
音樂，如果我能稍有閃失 數學位在這裡。
因此，還有第四種辦法，我們可以 想想這意味著什麼
功能比那些快 我們已經看到過。
如果你未來在課程 數學的背景，你
其實也許已經知道，你 這種技術可以一巴掌長期 -
即遞歸函數 以某種方式調用自身。
>> 再次，記得歸併排序 在這個意義上的偽代碼是遞歸
一個合併排序的步驟 是打電話排序 -
也就是說，本身。
但令人欣慰的是，因為我們一直 呼叫排序，歸併排序，
具體地，在一個較小的和更小的 和較小的名單，我們最終
走出谷底，感謝我們就這麼叫 基地的情況下，硬編碼的情況下，
說，如果列表很小，不到2 在這種情況下，就立即返回。
如果我們沒有這種特殊情況， 算法絕不會走出低谷，
事實上，你會進入一個 無限循環，真正的永遠。
>> 但是假設我們希望現在就把 在此，再次一些數字，使用n
作為輸入的大小。
我想問問你，有什麼 涉及的總時間
執行合併排序？
或更普遍的，有什麼 它的成本的時間嗎？
>> 那麼這是很容易衡量。
如果n是小於2時，所涉及的時間 在n個元素進行排序，
其中n為2，為0。
因為我們剛剛返回。
有沒有工作要做。
現在可以說，也許這是一個兩步 步驟弄清楚的金額
工作，但它足夠接近0 我只是說沒有工作
如果需要的名單是如此之小 無趣。
>> 但有趣的是，這種情況下。
遞歸分支 別人說的偽排序
的左半邊，排序的權利 一半，合併的兩半。
為什麼會發生這種表達 表示該費用？
嗯，T為n的意思是， 時間排序​​n個元素。
然後在右手側的 等號，劃分為n的T
2是指，以什麼樣的成本？
排序的左半。
其他T除以2的n 大概是指的成本
排序的右半​​邊。
>> 然後加N？
被合併。
因為如果你有兩個列表，一個是 大小為n超過2和其他大小為n
2，你必須基本上觸摸 這些元素，就像羅布
感動每個杯子，只是 正如我們在每個
志願者們在舞台上。
因此，n是合併的費用。
>> 不幸的是，現在這個公式 本身也是遞歸的。
所以，如果問的問題，如果n是說， 16，如果有16人在舞台上
在視頻或16杯，總共有多少個 步驟，它需要對它們進行排序
歸併排序？
它實際上不是一個明顯的答案， 因為現在你有排序
遞歸地回答這個公式。
>> 不過沒關係，因為讓我提出 我們做到以下幾點。
所涉及的時間，16人進行排序或 16杯將要被表示的
一般為T 16。
但是，這等於，根據我們的 前面的公式，2倍量
所花費的時間進行排序 8杯加16。
再次，加16是合併的時候， 兩個時間T 8是
左半邊和右半邊的時間進行排序。
>> 但是，這是不夠的。
我們必須在更深的潛水。
這意味著我們必須回答 問題，什麼是T的8？
T的8井僅2 4加8的時間T。
那麼，什麼是T的4？
僅有2 2加4倍t T的4。
那麼，什麼是T的2？
僅有2倍的T 1加2的T 2。
>> 再次，我們是一種越來越 在這個循環中卡住。
但它即將襲來 所謂的基本情況。
因為什麼是T的1，我們要求？
0。
所以，現在我們終於可以倒退。
>> 如果T 1是0，我現在可以回去最多一個 這個傢伙在這裡排隊，我可以
插頭為T 0 1。
因此，這意味著它等於2倍零， 否則被稱為0，加2。
使整個表達式為2。
>> 現在，如果我走T 2，其答案 2，將其插入中間線，T
4，給我的2倍 2加4，所以8。
如果我再插在8到前 行，這給了我2次，8，16。
而如果我們再繼續，隨著 24，增加16，我們終於得到一個
值64。
>> 現在，本身並排序講 無關的符號n，
大O，歐米茄，我們已經看到 一直在談論。
但事實證明，64確實是 如圖16所示，輸入大小，
登錄基地2 16。
如果這是一個有點陌生，只是 回頭想想，它會回來
你最終。
如果這是2為底，它就像2 提出了什麼給你16？
哦，那是4，所以它的16倍4。
>> 再次，它不是一個大不了的，如果這 現在是那種朦朧的記憶。
但現在，信仰 16日誌16是64。
因此，事實上，這個簡單的理智 檢查，我們確認 -
但沒有正式證實 -
運行時間合併 排序的確是N個記錄Ñ。
>> 所以不壞。
這絕對是優於 到目前為止，我們已經看到，算法
這是因為我們已經利用，一， 一種技術，稱為遞歸。
但比這更有趣， 概念的分裂和征服。
再次，真正實現0週的東西， 即使現在是反复出現在
更引人注目的方式。
>> 現在一個有趣的小運動，如果你 從來沒有做過這樣的 - 你可能
不會有，因為正常排序 人們不認為做到這一點。
但是，如果我去google.com和 我想了解一些有關
遞歸，回車。
>> [笑]
[笑聲]
國寶馬蘭：糟糕的玩笑慢慢蔓延。
[笑]
國寶MALAN：以防萬一，它的存在。
我沒有拼寫錯了， 的笑話。
好的。
解釋一下你旁邊的人，如果 但相當點擊只是還沒有。
但是，遞歸，更一般地，是指 的過程中的函數調用
本身，或者更一般地，將一個 到東西，可以是問題
頭痛醫頭，腳痛醫腳的解決解決相同 代表性的問題。
>> 好吧，讓我們改變齒輪 只是一瞬間。
我們喜歡在某些懸念結束， 讓我們開始設置
在舞台上，幾分鐘， 一個非常簡單的想法 -
交換兩個元素，對不對？
所有這些算法，我們已經 談論過去幾
講座涉及到一些 交換排序。
今天，它是用他們得到 出自己的椅子，
走動，但在代碼中，我們將 只是從一個數組元素
撲通到另一個。
>> 那麼，我們如何去這樣做呢？
好吧，讓我繼續寫 這裡的快速程序。
我要繼續做 這是以下。
讓我們把這個 -
我們要調用這個什麼？
>> 事實上，沒有。
讓我快退。
我不想這樣做 吊人胃口。
它會破壞其中的樂趣。
讓我們做到這一點，而不是。
>> 假設我想寫一點 現在方案，並擁抱
遞歸的想法。
我種了自己。
我要做到以下幾點。
>> 首先，快速包括標準io.h 以及包括cs50.h.
然後我要繼續前進 並宣布INT主要無效
在通常的方式。
我意識到我已經名不副實的文件，所以 我想補充的擴展名，在這裡，所以
我們可以正確編譯。
啟動此功能。
>> 的功能，我想寫點什麼，相當 簡單地說，就是要求
用戶輸入一個數字，然後添加 之間的數字
數，並說，0。
所以，首先我要繼續前進 並宣布INT N。
然後我複製一些代碼， 我們已經使用了一段時間。
雖然東西是真實的。
我會回來在某一時刻。
>> 我想要做的是什麼呢？
我想說的printf積極 請整數。
然後我要去 說N變得到詮釋。
如此反复，一些樣板代碼 我們以前用過的。
我要做到這一點 而n是小於1。
因此，這將確保用戶 給我一個正整數。
>> 現在我要做到以下幾點。
我想補充的所有號碼 介於1和n或0且n
等價地，得到的總和。
所以大的sigma符號 您可能還記得。
所以我要做到這一點首先調用 一個函數調用西格瑪，
在n傳遞給它，然後我要去 printf的說，答案是正確的。
>> 因此，在短期，我得到 int的來自用戶的。
我保證它的正面。
我聲明了一個變量叫做答案 int類型，存儲在它的回報
西格瑪值作為輸入，通過在n。
然後，我打印出這個問題的答案。
>> 不幸的是，即使西格瑪的聲音 喜歡的東西，可能是在
math.h的文件，它的聲明， 它實際上不是。
所以，這是確定的。
我可以實現自己。
我要去執行一個函數調用 標準差，它會採取
參數 -
讓我們只是把它M，只是 所以它是不同的。
然後在這裡，我要說的話， 以及，如果m是小於1 - 這是一個
很無趣程序。
所以，我要繼續前進， 立即返回0。
它只是無厘頭加起來 如果m 1和m之間的數
本身是0或負數。
>> 然後我要繼續前進 做到這一點非常迭代。
我會做這樣的老派， 我要繼續前進
並說，我要去 聲明總和為0。
然後，我將不得不 一個循環的int -
並讓我這樣做符合我們的 分銷代碼，讓您擁有一個副本
在家裡。 INT I上得到1 i是小於或等於m。
我+ +。
然後將裡面的for循環 -
我們幾乎沒有 -
總和得到的總和加上1。
然後我要返回的總和。
>> 所以我這樣做很快， 誠然相當。
但同樣，主要功能是相當 簡單的，基於代碼我們已經
書面迄今。
採用雙循環，得到了肯定 int的來自用戶的。
然後，我通過這個int到一個新的功能 叫西格瑪，調用它，再次，正。
我存儲的返回值，得到的答案 從目前黑盒子
已知作為σ，在一個變量中 叫的答案。
然後，我打印出來。
>> 如果我們現在繼續的故事， 西格瑪是如何實施？
我建議如下推行。
首先，一點點的錯誤檢查 以確保該用戶的不
梅辛與我並傳入 一些負面或0值。
然後我聲明了一個變量 綜上所述，將它設置為0。
>> 現在，我開始從i等於 1所有的方式，包括米，
因為我想包括所有 數字從1到m，首尾。
這裡面的for循環，我只是做 總和得到現在不管它是什麼，再加上
i的值。
加上i的值。
>> 順便說一句，如果你沒有看到這 之前，有一些語法糖
此行。
我可以改寫為加等於I， 只是為了保存自己敲幾下鍵盤
看起來有點涼。
但是這一切。
它的功能同樣的事情。
>> 不幸的是，這種代碼的 不會還編譯。
如果我運行make的西格瑪0，怎麼我 我大叫？
什麼是它不喜歡呢？
>> 觀眾：[聽不清]。
>> 國寶馬蘭：是啊，我沒有申報 向上頂，右邊的功能？
C是一種愚蠢的，它僅 做什麼你告訴它的事情，而你
必須這樣做的順序。
所以如果我打在這裡輸入，我要 關於Sigma隱警告
聲明。
>> 哦，不是一個問題。
我可以去到頂部，我可以 說，沒事的，請等待一分鐘。
六西格瑪是一個函數，返回 一個int，並預期
int作為輸入，分號。
或者，我可以把整個功能 上述主要的，但在一般情況下，最好
針對該建議，因為它是 很高興上面的頂部，所以總是有主
可以潛水的權利，並知道什麼是 程序首先通過閱讀主要做。
>> 所以，現在讓我清楚的畫面。
重拍0西格瑪。
所有似乎退房。
讓我跑SIGMA 0。
正間。
我給它的數量 3，以保持它的簡單。
所以，應該給我3 加2加1，所以6。
回車，我確實得到6。
>> 我可以做更大的東西 -
50，12，75。
正如切線，我要做的 可笑的東西像一個真正的大
號，呵呵，那實際工作 -
誒，我不認為這是正確的。
讓我們來看看。
讓我們真的惹它。
>> 這是一個問題。
這是怎麼回事呢？
該代碼是沒有那麼糟糕。
它仍然是線性的。
吹口哨是一個很好的效果，雖然。
這是怎麼回事呢？
>> 不知道如果我聽到它。
因此，原來 - 這是作為一個旁白。
這不是核心到 遞歸的想法。
事實證明，是因為我試圖 代表這樣一個大的數字，最
它可能被誤解 C作為一個並不樂觀的數字，
但負數。
>> 我們還沒有談到這一點，但它 原來有負數
在世界上除了 正數。
和手段，通過它可以 表示負數
基本上是，你使用一個 特殊的位來指示
正面負面以上。
這是一個有點比這更複雜， 但是這是最基本的想法。
>> 不幸的是，如果C是混亂的一個 那些位作為實際意義，
哦，這是一個負號，我的循環 在這裡，例如，實際上是從來沒有
要終止。
所以，如果我實際打印的東西 一遍又一遍，我們會
看到一大堆。
但是，這是除了點。
這是真的只是一種 對知識的好奇心，我們還會回來
最終備份。
但現在，這是一個正確的 如果我們假設執行
用戶將提供整數 適合內整數。
>> 但我要求這個代碼，坦率地說， 可以做簡單得多。
如果在手的目標是採取多項 像米，加起來所有的
之間的數字，並且1，或反過來 介於1和它，我要求
我可以借用這種想法，合併 排序了，這是一個問題
這種規模和分割 成更小的東西。
也許不是一半，但規模較小，但 代表性地是相同的。
同樣的想法，但一個較小的問題。
>> 因此，實際上，我 - 讓我好好保存這個文件 不同的版本號。
我們稱這個版本 1而不是0。
我要求其實我可以 這種重新實現此
心態彎曲方式。
>> 我要獨自離開它的一部分。
我會說，如果m是 或者甚至等於0 -
我只是要一點點 肛門
我的錯誤檢查 -
我要繼續前進，返回0。
這是任意的。
我只是簡單地決定，如果用戶 我給了我一個負數，
返回0，他們應該已經讀過 的文檔更加緊密。
>> 其他 -
注意什麼，我要做的事情。
否則，我要返回米加 -
什麼是西格瑪米？
那麼，Σ的m加m減1， 加m的負2，加m零下3。
我不想寫出來。
我為什麼不只是撐船？
遞歸調用自己稍微 規模較小的問題，分號，
收工？
>> 對嗎？
現在在這裡，太，你可能會感到或擔心 這是一個無限循環，我
誘導，由此我實現 西格瑪致電西格瑪。
但是，這是完全確定的，因為我 想提前增加了哪條線路？
>> 觀眾：[聽不清]。
>> 國寶馬蘭：23日至26日， 是我的，如果條件。
因為關於什麼是好的 減法這裡，因為我保持
交給西格瑪小問題，小 的問題，更小的 - 它不是
的一半大小。
這只是一小步， 不過沒關係。
因為最終，我們將繼續努力 我們一路下跌為1或0。
一旦我們打0，Sigma的不 會調用本身了。
這將立即返回0。
>> 所以效果，如果你樣的風 在你的心中，是增加M PLUS
M減1，加m減2，加m減 3，加點，點，點，M減
米，最終給你0， 最終效果添加的所有
這些東西放在一起。
所以，我們還沒有，用遞歸 解決了這個問題，我們
之前沒能解決。
事實上，版本0，每 問題到今天為止，已經解
只需使用循環或在 循環或類似的結構。
>> 但是，遞歸，我敢說，給我們 以不同的方式思考
問題，因此如果我們可以採取一個 問題，除從東西
到有些東西有點大 較小的，我要求，我們可以解決這個問題
也許是多了幾分優雅條款 設計，用更少的代碼，
甚至解決的問題，會 更難，因為我們最終會
看到，解決純屬迭代。
>> 但扣人心弦的，我沒有 要離開我們是這樣的。
讓我繼續前進，打開 一個文件 -
其實，讓我去 這樣做真正的快。
讓我繼續前進，並提出 以下。
其中今天的代碼是這樣的文件在這裡。
在這裡，這一個noswap。
>> 所以這是一個愚蠢的小程序， 我掀起了要求做
以下。
在main中，它首先聲明 為int，名為x和分配
為1的值。
然後，它聲明int y和 分配值2。
然後打印出x和y是什麼。
然後，它說，交換，點點點。
>> 然後，它聲稱要調用一個函數 稱為交換，傳遞x和
Y，其中的想法是，希望 x和y會回來
不同的，相反的。
然後，它聲稱交換！
一個驚嘆號。
然後打印出x和y。
>> 但事實證明，這很 簡單的演示下來
這裡是實際馬車。
即使我宣布一個臨時的 變量和暫時把
它，然後我重新分配 一個b的值 -
覺得合理，因為我 保存副本的溫度。
然後我更新b等於 無論是在溫度。
這類殼移動遊戲 到b和b成通過使用該
中間人名為temp的感覺 完全合理的。
>> 但我要求當我運行這個 代碼，我現在要做的 -
讓我繼續前進，將其粘貼在這裡。
我會打電話給這個noswap.c。
顧名思義，這是不 將是一個正確的程序。
讓noswap /無掉。
x是1，y是2，交換，交換。
x為1時，y是2。
這是從根本上是錯誤的，甚至 雖然這似乎是完美的
合理的，我。
還有一個原因，但我們不 要揭示的原因，只是還沒有。
>> 現在我想的第二個扣人心弦的 離開你，
公佈各種優惠券代碼。
今年我們的創新與已故天 激起了不平凡的數字
的問題，這是 不是我們的本意。
這些優惠券代碼的意圖， 據此，如果你這樣做是問題的一部分
提前設置，從而獲得一個額外的一天， 真的幫助你們有所幫助
自己年初開始，排序 激勵你。
有助於我們之間分配負載 辦公時間更好地使
它的排序共贏。
>> 不幸的是，我覺得我的指示 沒有，到今天為止，已經很清楚，所以
我又回到這個週末更新 規格更大，更大膽的文字
解釋這些子彈。
只是說它更公開， 默認情況下，問題集將於週四
日中午，按照教學大綱。
如果你起步早，完成一部分 週三12:00設置問題
下午，部分，涉及到的優惠券 代碼，這個想法是，你可以擴展
您的截止日期為 P設定至週五。
也就是說，咬下一小部分的P 設置通常是相對
更大的問題，你買 自己一個額外的一天。
再次，它可以讓你思考 設置的問題，讓你去
辦公時間越快。
但優惠券代碼的問題仍是 必需的，即使你不提交。
>> 但更令人信服的是這樣的。
（舞台WHISPER），而那些人離開 早期是會後悔的。
鄉親在陽台上。
我提前給鄉親道歉 陽台上的原因，這將是
清除在短短的時刻。
>> 因此，我們很幸運，有一個 CS50的前任主管教學研究員
一家名為dropbox.com。
他們非常慷慨地捐出了 優惠券代碼，這裡這麼大的空間，
這是從 平時的2千兆字節。
所以我想我們會做這個 最後要注意的是做一點的贈品，
在短短的時刻，我們將揭示 贏家有優惠券
代碼，然後你可以去他們的 網站，鍵入它，瞧，得到了
一大堆更多的Dropbox空間為您的 家電和您的個人文件。
>> 第一，誰願意參加 在該圖中？
OK，現在這使得它更有趣。
人誰收到這25千兆字節 優惠券代碼 - 這是遠遠
更引人注目的莫過於後期 現在，也許是 -
是一個誰是坐在最重要的一個 座墊下方有
該優惠券代碼。
現在，您可以看下面 您的坐墊。
>> [視頻回放]
>> 一個，兩個，三個。
>> [尖叫]
>> 你得到一輛車！
你得到一輛車！
>> 國寶馬蘭：我們將看到 上週三。
>> 你得到一輛車！
你得到一輛車！
>> 國寶馬蘭：陽台鄉親，來 這裡到前面，
在那裡我們有演員。
>> - 每個人都得到一輛車！
人人都有車！
>> [END視頻播放]
>> 旁白：在未來CS50 -
>> 揚聲器5：哦，我的天哪天哪天哪天哪 天哪天哪天哪天哪天哪天哪 -
>> [UKELELE戲劇]