[音樂播放] 國寶馬蘭所有權利。好吧，歡迎回來。因此，這是第4週，開始其已經。你還記得，上週，我們把編碼一旁只是一點點我們開始交談多一點高層次，一樣的東西搜索和排序，這雖然有些簡單的想法，代表的一類問題你將開始解決特別當你開始思考最終項目和有趣的解決方案可能有現實世界的問題。現在是一個最簡單的冒泡排序這樣的算法，它通過這些小的數字工作在一個列表中，或在一個數組中種泡自己的方式到頂部，大的數字移動一路下跌至該列表的末尾。記得我們可以想像一點點的冒泡排序這樣的事情。所以，讓我繼續前進，單擊“開始”。我預選冒泡排序。如果你還記得，高大的藍色線代表大號碼，小藍線代表小數字，我們通過這一而再，再而再次，比較相鄰的兩間酒吧紅色，我們要交換最大的和最小的，如果他們秩序。因此，這會去，去，去，你會看到，較大的元素使他們的方式的權利，而較小的元素是使他們的方式到左邊。但我們開始量化效率，在此算法中的質量。和我們說，在最壞情況下，該算法採取了大約多少步？因此n的平方。什麼是N？觀眾：元素數目。國寶馬蘭因此n 數目的元素。所以我們經常這樣做。任何時候，我們要談論的大小一個問題或大小的輸入，或花費的時間量以產生輸出，我們只廣義的任何輸入為n。因此，早在第0週，數頁在電話簿為n。學生人數在房間裡為：N。所以在這裡，太，我們繼這個模式。現在Ñ平方是不是特別快，所以我們試圖做的更好。因此，我們看著一對夫婦其他的算法，其中選擇排序。所以選擇排序有一點不同。這幾乎是簡單的，我敢說，由此開始的開始我們的志願者名單，我只是再次一次又一次經歷列表，採摘最小在一個時間元素，並把他或她在列表的開頭。但是它也同樣，一旦我們開始思考通過數學和更大的圖片，想過多少次我正想來回和背部奔波，我們說，在最壞的情況下，太多，選擇排序，那是什麼？擺正Ń。現在，在現實世界中，它可能實際上是稍快。因為再次，我沒有保持回溯一旦我排序最小的元素。但是，如果我們想想n很大，如果你的，做出來的數學我在黑板上，與n的平方減去的東西，一切除了n個平方，一旦N 變得非常大，不真正的問題一樣多。因此，作為計算機科學家，我們的排序視而不見較小因素和只注重的因素一個表達式，將會使最大的區別。好了，最後，我們看了在插入排序。這是類似的精神，但而不是通過迭代選擇最小的元素之一，在的時間，我只花了我的手處理，我決定，所有沒錯，你屬於這裡。然後我轉移到下一個元素並決定，他或她屬於這裡。然後，我和移動。我可能會，一路走來，以這些傢伙轉移為他們騰出空間。所以這是樣的心理逆轉選擇排序，我們所謂插入排序。因此，這些主題發生在現實世界中。僅僅在幾年前，當達到一定參議員競選總統，，在當時的CEO埃里克·施密特（Eric Schmidt）谷歌，居然有機會採訪他。我們認為我們會分享此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戲劇]