[Powered by Google Translate] 第3週，續]
>> [戴維·J·馬蘭 - 哈佛大學]
>> [這是CS50。 - CS50.TV]
>> 好的。歡迎回來。這是CS50，這是第3週的結束。
>> 因此，對於那些不熟悉的，去年哈佛推出什麼所謂的創新實驗室，
我的實驗室，這是一個美妙的河對岸的哈佛商學院的校園建設
這是大學生，GSAS學生，學生來自全國各地的校園，
包括教師，這是一個地方走到一起，工作創新的事情，
尤其是創業的事情
如果你和0個或更多的朋友所思所想，做一些創業
無論是在這一類，這個類後，或超越。
>> 所以，他們做了Ĵ長期的事情之一是這些行程，
其中一個是紐約，其中之一是矽谷。
空間是非常有限的，但它是一個擁有MBA學位的機會擦肩
和研究生的學生在校園裡，實際上花時間在這些各自領域
聊天的初創公司，聊天企業家等。
因此，如果感興趣的話，看看這個網址。
它也可以用網上的幻燈片。
>> 我們可以淡化房子的音頻只是一點點嗎？
如果你想和我們一起吃午飯，這個星期五​​，下午1:15在火與冰，頭上有。
道歉，如果已經填寫的表格的時候，當你到達那裡的。
但是，我們將繼續這一傳統開始。
>> 今天，我們繼續，我們能夠解決的各種問題的高級別討論會，
重點要少得多，至少今天，代碼和更多的想法。
所以想回0週時，我們撕了電話簿中的一半，
該計劃的目的是做什麼的，誠然，一點點戲劇性的
但發送的點，搜索不必須是，必然，
乍一看，你可能認為很明顯。
一般的解決問題的可能不一定永遠是最好的 -
最明顯的解決方案不一定是最好的。
因此，我們必須電話簿，坦率地說，我們所有的人在這個房間裡的本能，
最有可能的是，開始時，尋找麥克·史密斯在中間，然後向左走還是向右
根據我們發生任何字母結束。
>> 但是，簡單的想法，我們人類已採取了這麼久授予
真的應該開始你的頭腦來的最前沿
因為所面臨的問題複雜得多比一本電話簿，
那些同樣簡單，卓越的見解是什麼，讓我們
解決更複雜，更有趣的問題，
其中的一些事情，我們需要對已經授予這些天。
數十億的網頁在那裡，但谷歌和Bing之類的
能找到東西對於我們這樣的。
這不會發生使用線性搜索，通過搜索所有可能的網頁。
Facebook是能夠告訴你是誰，你所有的朋友或者朋友的朋友，
而且也可以做似乎是在瞬間，這些天
即使他們擁有數百萬用戶。
>> 因此，我們實際上如何解決規模問題上，最終將減少
我們的想法看著在0週，多一點。
我們不會重新執行該算法，但記得，我們​​也做了這個練習在0週
我們每個人都站起來，拿上1號，
然後我們每個人都自我計數的配對過，一起加入你的號碼，
然後上坐了下來，該團伙每次迭代的一半。
因此，我們從500名學生，250至125，等等。
但是，正如我們週一表示，有強大的思想
是，如果我們對這個問題的規模增加一倍
由律政司司長或EC 10和所有的孩子都回來進了房間，加入我們，
好了，我們可以大概算，整個聚合組
更多的大循環迭代，因為他們只可能會增加一倍的大小
或在EC 10的情況下多一點的兩倍大小。
因此，我們將不得不多花一點點的時間，
但我們不會花400或700以上的步驟。
>> 只是為了畫這幅畫，這是一個少一些抽象的方式，讓我們無法讓每個人都站起來。
但是，如果你選擇了坐今天的樂隊不會介意站了起來，
讓我們看看我們可以計算出在你們中間誰是最高的人是
做同類型的比較算法。
所以，如果你坐在樂隊，我的道歉，但第1步，站起來;
第2步，對附近你與任何人，
找出誰是高了，坐下，如果你是短的。
然後重複。
[學生口中念念有詞]
>> 好吧。
好吧。一個放置。你叫什麼名字？ “安德魯。
>> 安德魯，你是最高的人今天在樂隊的部分。
>> 恭喜你。 [掌聲和歡呼]好吧。有一個座位。因此，我們發現安德魯。
但是，如何將它已採取了我，例如，找到安德魯
在這個樂團節50 +左右的人嗎？
我可以採取一個非常簡單的方法，並從這裡開始。
而我有2人站起來和我只是對它們進行比較，
然後我說誰是略短，“好了，你坐下。”
我會記住這位高個子的人。
然後，我再說一遍，再說一遍，再說一遍，我掛在最高的人
直到我發現有人比他們稍微高一點，在這一點
略短的人，然後坐下。
但是，在這個樂隊部分的算法，如果你的N，
該算法要採取的步驟是多少？ >> [學生]。
>> 要取n，正確的，因為在最壞的情況下，可以這麼說，
最高的人是最後的人，我只是隨機的運氣不好。
因此，在最壞的情況下，該算法的運行時間是線性的，它是N，
其中n是總數的人在該空間的大小的問題。
有關此算法呢？
事實上，你都站了起來，然後你再一半的坐了下來，
你一半的坐了下來，你一半的坐了下來。
多少步，如果你在這裡的N？
[學生] n日誌n。 “這將是更糟糕。登錄N。
>> 因此，日誌N，即使你不記得什麼是對數，
現在，只要明白，不知怎麼的，涉及此減半減半，並減少一半。
它不必是2的因數。 3，它可能是一個因素。
但它的這種重複的因子，例如同種大小的問題，從這裡開始
但隨即在這裡，那麼在這裡，然後在這裡，然後在這裡。
你不採取小咬出了問題，你真的砍個不停。
有一個大一舉每個時間。
因此，我們有50人，然後25，然後12½或13人站立，
6½依此類推，直到最後只是安德魯罰站。
因此，我們將調用該日誌的n，你可以想像如下。
回憶這幅畫在這裡就像是一個線性算法紅線，
黃線是2的計數算法，用於計算學生
在過去，但今天的制勝法寶是要保持這個綠色的線
如果我們在樂隊部分人的數量增加一倍，或只是說，
地獄，讓整個房間中的每個人都站起來，而不是什麼大不了的
因為我們的兩倍，有多少人在這裡，
更多的迭代，而不是一個問題。
>> 我們發現安德魯或任何人恰好是身高超過安德魯
在夾層或在陽台上。
因此，這個簡單的想法，我們花了這麼多是理所當然的在電話簿中，
認識到有這麼多不同的地方，我們也可以將它。
我一巴掌一些術語 - 事實上，而不是行話第一，
讓我去給你的圖片在這裡。
現在，我們談到n和n / 2，然後登錄的n，
，但我們可以肯定是，我們將在本學期，
其他類型的數學公式來描述這個一般概念的運行時間。
這些都是現在的內容，因為我們將看到不久
算法，這實際上代表。
>> 但是請注意，這裡的直線n，則直線，其實是非常低的指向右側。
這是一種錯覺，因為我們只需要改變，X軸代表什麼樣
和y軸，並且我們可以使我們想要在任何方向上的直線點。
但原因，它是如此看似平坦
是因為我們需要在這個圖表上的運行時間要慢得多，以騰出空間。
現在，知道有一些很糟糕的算法，在生活中，
其中一些不取n個步驟，或者更好的，記錄n個步驟，但更多。
所以，上面的線N在底部的通知n的n次日誌，
我們會看到，這是什麼意思不久。
以上說的是n的平方，我們還沒有看到任何n的平方算法，但我們要的。
這看起來真的很糟糕。
有2到n，一些指數，感覺更糟糕。
然而，奇怪的是，那麼那裡的N立方，如果你是那種超前的思維，
如果你有種做數學題，2的n其實變得更加截彎取直，
高得多的比n的三次方，如果你足夠遠的軸。
所以注意到現在這些軸是任意2〜10的在x軸上。
>> 這是什麼意思呢？
這意味著，在房間內的2人到10人。
這是所有的x是指：的背景下，無論是大小的問題。
和垂直軸現在是秒或步驟數目的數 -
一些單位的時間。
但是請注意，它的0〜60和0〜10。
但是，如果我們種縮小時，你可能會在Excel或一些看圖軟件，
我們去了20萬，看到的東西，如2的n
要完全壓倒的n的平方的運行時間，
Ň立方，n日誌n - 我們已經談了迄今為止的一切。
但美中不足的是，當你開始談論的東西，如Facebook
在那裡你有很多，很多，很多人都相互聯繫，
你有N人，每個人都可能有許多為n的朋友
如果每個人都在世界排序的哥們哥們，
，這是n次，Ň了，所以，可能的N平方友誼，
至少在1個方向，N的平方可能的友誼。
所以這已經表明，搜索Facebook的社交圖，可以這麼說，
可以從在這些種的公式來表示。
>> 我們會回來，並更加具體，
但就目前而言，客觀上為接下來的幾個星期
將是肯定不會去執行的算法或代碼
為此佔用了盡可能多的時間，這樣的事情。
但令人不可思議的事情有關計算機科學，如果你繼續在這一領域
類，如CS121，CS124，這兩者都是理論課，
其實是有在這個世界上存在的一些問題，
，從根本上說，據我們所知，也沒有得到解決得更快
比最壞的這些圖實際上建議。
所以這是一個開放的問題，在這個世界上做的更好，比人類迄今為止很多。
>> 所以，讓我們開始這個例子。
我們看到肖恩這對相機的鬥爭，太笨拙視頻。
但現實情況是，當肖恩的任務是找到這樣的板7號，
記得，我說：“有這些紙片或白色的門背後的地方
“7。肖恩，我們找到它。”
這是奇妙的尷尬觀看
因為他真的在努力解決這個問題。
但現實情況是，肖恩以及在房間裡的任何人都可以做的。
他花了一點時間比一般的人可能有，
但他認為有一些技巧，這個問題，
他認為他失去了一些東西。
它並沒有幫助數以百計的眼睛，軸承在他身上。
>> 但現實的問題是，如果輸入一串隨機數
你被要求找到1號，
你可以做的最好的是線性搜索。
開始在左邊移動到右邊，開始在右邊移動到左邊。
追溯，我們可能會想，“肖恩，為什麼你不只是從另一端嗎？”
7可能很容易地在這裡隨機的，
但我刻意把它放在那裡，因為我想他也不會在年底開始。
所以，我種操縱的情況，但可以是任何地方偶然的機會7。
因此，從右端開始，然後可能是更好的，
但如果明年我謹7其他地方嗎？
這不是從根本上解決問題的辦法 -
從1月底或其他 - 當你沒有其他的假設。
所以，肖恩開始尋找通過數字，他說：“10，這是不是在這裡。”
然後，他來到這裡，看到19，然後他停約20秒，
然後他打開了13，然後它變得明顯
有沒有這裡似乎有一種模式。
它不是1，2，3，4或等。在數字的差距，這並沒有幫助。
過，事實上，我用這些廉價的紙片覆蓋上的數字
其實是故意的，因為如果我刪除了所有這些紙片，
對我們大多數人，肖恩包括，可能會掃了一眼樣的宏觀
在黑板上，說：“哦，7顯然是正確的。”我們這樣做是瞬間。
>> 而這可能會對人類大腦工作的方式在一定程度上，
但在現實中，可能是他的眼睛或心靈掠過數字由右至左，
左到右，中間就出來了 - 這是怎麼回事生理
這樣，感覺就像是瞬間發生的，
但賠率是即使內部有一些方法，發現7種。
事實上，現在我們談論陣列和數據結構
的計算機的內存裡面，只有我們人類的事情可以做
是看在個人記憶體位置的時間。
>> 因此，所有其他的位置可能被掩蓋了一些一張紙
因為我們看不到也無妨。我們只能做一件事，那就是在一個時間。
因此，在這種情況下，在Sean的情況下，我們來到這裡，然後我們就在這裡
然後我們就在這裡，這裡，這裡，這裡，得到了年底聰明
只是種跳過這個任意，發現7有。
這一次是沒有特別突出的。它也壞了。
但他終於找到了7。
但是，現在的外賣真的是最好的，你可以做的時候沒有信息
隨機排序的數字是從左側或從右側開始。
哎呀，你可以隨意打開門，但即使如此，這是什麼意思是隨機的？
那麼，我們就必須以某種方式正式化意味著什麼，從這裡開始，
然後到了這裡，然後在這裡。肖恩做了偉大的，它是看著很有趣。
我們改變什麼，如果不是一點點的問題，並提出了今年的肖恩，如果你願意嗎？
會有人舞台上，解決一個稍微不同的問題
出現在相機？
>> 讓我們超越的樂隊，因為你們已經相當複雜，今天已經。
怎麼樣，在粉紅色的帽子嗎？下來吧。你叫什麼名字？ “亞歷克斯。 “亞歷克斯。好吧。
因此，亞歷克斯將是今年的Sean，並在未來幾年內將出現在
價值CS50講座。
亞歷克斯，認識你很高興。 >>也很高興見到你。
面臨的挑戰是，你必須在你的手稍微輕鬆一點兒
我告訴你相同的號碼在這裡，但他們現在排序。
所以，現在你的目標是找到7號。
實際上，我們真的應該讓這個 - 你們種作弊行為，就像一台計算機不會，
在看什麼，剛才的數字。
用粉筆，這實際上是要幫助所有的東西，
但讓​​我們假設，你不知道原來的數組。
你現在知道的是，你有一個數組排序的數字
可能有它們之間的差距，你的目標是要找到7號。
你會怎樣，一個合理的人，去發現7號呢？
>> 從低到高嗎？ “好了。轉到低到高。
也不可撕裂他們。讓剛抬起起來，所以我們可以重複使用。
好了，所以1。等待。在你堅持下去，這是1，顯然是錯誤的。
所以通過你的頭腦是怎麼回事呢？你的下一步行動是什麼？
下一個。 “好了。下一個。好。 3，那麼不正確。你的下一步行動是什麼？
繼續下去。 >>所有權利。繼續下去。 5。
因此，保持下去，並讓我交給你為後人。
7。 >>太優秀了。非常好。找到了7號。 [掌聲]
所以這是很好的，但肖恩也發現7號。
我說，你還沒有真正利用這個額外的資料片，
這是，這些數字的排序條件。
因此，我們可以做的更好？任何建議嗎？是啊，在後面。
[學生]二進制搜索。 >>我不知道什麼是二進制搜索。
>> [學生]開始在中間。 “開始在中間。好吧。因此，讓我們看看我們是否能到達那裡。
所以，如果不是有人告訴你從中間開始，去進取，不斷開拓中間的門。
有8人，所以你將有任意選擇一個
稍微向左或向右。好吧。 7！ [掌聲]非常不錯的。
好了，但在我們這個嗎？
讓我們假設只是為了打破平局，你已經開始在這裡
因為，同樣可以發生。
我們正好知道7。因此，這是13。
所以，如果他們排序，我們才剛剛開始在中間，
會是什麼最佳下一步的行動了嗎？
轉到左邊。所以來這裡的電話簿的例子。
如果13是在這裡，我們知道對列表進行排序，
所有這些紙片是無趣的，我們現在
因為我們已經知道，必須向左側
如果這些數字進行排序，我們發現有13。
>> 那麼，什麼是你的下一步行動在這裡？ >>跳轉到左邊。 >>好，好。
所以，去到左邊， - 等待，嘿，嘿，嘿。這是一種欺騙行為。
所以，你發現7，但我們剛剛申請的算法是什麼？
開始在中間。 >>好。那麼什麼是合乎邏輯的延伸，同樣的想法嗎？
哦，不僅僅是這些。 “沒錯。 “等我從這裡開始。 >>好。
所以，現在我們就略向左側。這是3。
但有趣的外賣現在是哪一個你不關心嗎？
這2個。 >>這2個。所以，現在這個可以走，這一次可以走。
這是8，然後現在的問題是，現在是大小尺寸為4 2。
我們已經很接近了。同樣，到中間的這2個元素。
>> 好吧。因此，這是不幸的，現在我們總是要離開了，因為我們是向下舍入。
但是，這很好，因為我們現在拋出這個遠離一切，留給我們的只有7。
讓我們掌聲雷動。我們再次發現了7。 [掌聲]好吧。當然。
掛在1秒鐘。
儘管這過程中種了一點點的時間比我們認為這將
坦率地說，你的第一直覺是最好的，對不對？我們發現瞬間。
但我們會發現7的速度，無論什麼時候，在這個例子中，而這個
因為，如果所有的數字排序，就像在電話簿的頁面，
事實上，你可以砍一半的問題再，再而三。
這是不是很容易看到這一點只有8個數字
相對於一個1000頁的電話本，你真的看到在視覺上，
但在這種情況下，在這裡，當肖恩搜索7，
多少步驟，在最壞的情況下，它會採取他嗎？ >> [學生] 7。
7在最壞的情況下。那麼，在最壞的情況下，如果有8個門。
他將採取8個步驟。
>> 因此，如果有的n門，它可能已採取肖恩在幾年前n個步驟。
現在，亞歷克斯，你的情況，因為這些數字進行排序 -
我們可以推斷出這一點，我們從那裡一直迄今為止，在這個故事中的一種 -
亞歷克斯的更智能的算法的運行時間
從中間開始，然後重複？
[學生] 3。 “所以，這將是3，粗略地說，如果你去從8日至4以2比1。
因此，3個步驟，或者，更普遍的是，這是日誌n再次。
任何時候，你要減半，減半減半和減半，
這是一個表達這種想法的日誌n。
因此，該會已採取你只有3個步驟，它的確做到了
一旦我們打開門減半減半，
而這一切都採取肖恩約7或8個步驟。
所以，謝謝你為我們今年。 >>謝謝。很高興見到你。
謝謝亞歷克斯。 ，>>類似地。 [掌聲]
>> 那麼真正的含義是什麼？
現在想像一下，這是不是8個門，其中，坦白地說，我們所有能找到的東西
後面8門很快就撕開紙片，與我們的本能。
但是，如果它是一個萬門？如果它是4十億門？
4十億門的情況下，你真的想要去Alex的算法，
二進制搜索，因為我們將開始稱這是“或”分而治之“，更普遍的，
你可以將減半，並減少一半的問題，
因為如果你有4十億門，多少次，你砍四十億一半嗎？
[學生] 32。 >>這是實際上是32。您可以在紙上或在你的頭上。
你去四十億2億至1十億半十億，至250億美元，點，點，點。
如果你做出來的數學，你要確實得到32，
，這實際上涉及到計算機科學，因為我們平時的2的冪數。
2到32恰好是4億美元。
所以有很多的這些權力2種計算機科學相關。
>> 但約8億美元呢？多少個步驟是，將要採取的如果有8十億大門呢？
[學生] 33。 “等33。如果有16十億門？多少個步驟是，將要採取的嗎？
[學生] 34。 >> 34。我們可以繼續令人生厭。但是，這是一個強大的東西。
你可以介紹你的問題，但更多的投入到數十億，沒什麼大不了的，
你只需要1個附加咬了一口，從而為我們提供了類似二進制搜索
“或”分而治之“，更普遍。
但我是那種欺騙在這裡，對不對？
她在Alex的算法的情況下，肖恩的優勢。
她知道，這些數字進行排序，但亞歷克斯沒有自己對它們進行排序。
我提前來到了確保在黑板上種
我畫了他們所有的排序順序，然後我介紹了他們的論文。
但多少工作，這是我嗎？
如果我們已經開始了與這些數字在一些看似隨機的順序 -
在這種情況下，這些簡單的數字，1至8在這裡 -
我們怎麼去排序這些值嗎？
如果你是一個人，這個任務，你會採取什麼樣的直觀的方法
一大堆的數字進行排序？
這些東西拼圖。是啊。
>> [學生]我想每個數字比較，每一個
並保持要左邊。 >>好，好。
所以，每一個數字，它旁邊的一個比較，
，然後就繼續沿著列表，種rejiggering的事情，當您去。
所以，在這裡，我們有一個機會，也許更多的人參與進來。
我們有更多的志願者誰願意上來嗎？
少一點壓力，因為你不是唯一的一個。 1，2，3，4，5，6，7，8。
下來吧。你們都將是數字1到8。
讓我們來看看如果我們不能做到這一點排序亞歷克斯以同樣的方式，我做到了提前。
1，2，3，4。
來吧，如果你願意，舞台上的音樂之間的立場，我在這裡
以相同的順序在屏幕上滑動。
嗯，哦。
我們將工作，你到下一個例子。哦，等等，等等。在這裡，我們走了。等待。
下面的例子是現在。在這裡，你走。第8號。上來吧。
好的。排序自己根據本。
只是一點點滑動側面的音樂站在這裡。
因此，我們有4個，2，6 - 在那裡，在這裡，就在這裡 - 3。
是啊。好吧。你在這裡。不，你呆在那裡。
是的，沒錯。不，我是錯的。就在那裡。好了，非常好。好吧。
現在讓我們來對它們進行排序按遞增順序。
>> 我怎麼能這樣做呢？
剛才提出的算法是，為什麼我們不比較
的人誰種下彼此，然後修復任何錯誤，
移動由左到右。
所以，在這裡，我們有4個和2個明顯的。讓我們交換你。好吧。
所以我現在要向下移動一行。 4和6，沒。 [笑聲]
6和8，很不錯。 8和1，讓我換你們。好的。
因此，8和3，交換你們。
8和7，讓我換你們。 5和8，優良的。
我給你一個排序的列表。
好的。所以不大。
但它是更好，因為更大的數字 - 8點 -
有怎樣的冒了出來，從左邊到右邊。
所以我得到了1對的，但感覺這樣的問題並沒有完全解決。
>> 所以，你會建議我們下一步要做的嗎？ >> [學生]繼續做下去。 >>我們繼續做下去。
而實現，我們再次設置的東西，只是讓所有的人
排序聰明地安排自己的基礎上，圖片，
但現在我們要更加有條不紊。
我們是它的算法，雖然我們編寫代碼 -
在這種情況下，口頭的偽代碼。
所以，讓我們再試一次。這工作得很好。它並沒有解決它。
但是，當它懷疑，嘗試，再嘗試。 SO 2和4，沒有幫助了。
4和6。 “啊！ 6和1，現在稍微好一點。
3，良好的。 6和7，7和5，7和8，良好。
你知道，我也許可以忽略現在，因為他是在列表末尾。
也許我們不必擔心有人路過他。
但是讓我們看看如果這是一個安全的假設。
現在的名單是 - 該死的 - 沒有排序。讓我們再試一次。
因此，2和4，4和1，4和3。
圖4和圖6，良好。 6和5，良好的。
6，7，和8，良好的。但是請注意，我只是停在這裡現在，現在停在這裡嗎？
[學生]是的。 >>呀？
如果你已經一路9號有什麼？
它已排序的。 >>好。這已排序的第一時間。
好。所以，讓我們再回去。我們快到了。
1和2，2和3，3和4，4和5，5和6，6和7，7和8。
>> 我現在所做的，但同樣，我是一個電腦，可以做什麼，我告訴我說，做，
現在是我唯一的回憶，其實我只是做了一點工作。
這裡發生了改變。
所以我沒有視覺或技術上確認確實排序算法，此列表。
所以剛剛好措施，只是肛門約，讓我們這樣做更多的時間。
因此，1和2中，2和3，3和4。你知道嗎？
說的好措施，我要跟踪我的手，這
多少掉期，我只是讓我知道多少工作，其實我已經做了。
3和4，4和5，5和6，6和7，7和8。掉期交易。
所以，現在我將合法是一個白痴再次做到這一點
因為如果我這樣做沒有工作的人通過本通，
那麼顯然會再次發生，如果他們都不是那種隨機
adversarially自己身邊。所以，現在我可以停止。
現在，讓我們問這樣的問題，多少工作，這實際上把我嗎？
多少步驟？ >> N的平方。
是的，所以n的平方。你在哪裡得到n的平方呢？
你必須檢查每一個NUM -
有n個數，並與其他n個數字，你必須檢查每一個數字。
好。 “因此，它的N的平方。 >>好。
>> 所以感覺像它很可能是n的平方，正確的嗎？
這些傢伙的N，8特別是在這種情況下，
但通過這個列表每次我去，我是比較對第二次的第一人，
第二對第三一遍又一遍，
當我到了年底，我做了什麼？我重做了。
因此，如果我們概括這樣的解釋，我們有N多人
，我，很明顯，8個步驟，n個步驟，我每次去通過這個算法。
但我有多少次，在最壞的情況下通過這個列表的人去嗎？
[學生] N倍。 >>大概N，正確的，因為在最壞的情況下，
什麼可能是最糟糕的情況下，安排這些傢伙從一開始就？
如果他們完全相反的順序
因為只是想精神，let's - 你叫什麼名字？ “博文。
博文。好吧。因此，博文，到這兒來，一會兒就好了。
>> 假設鮑恩在算法開始時，在這裡，
我們不知道其他人，但鮑恩在這裡，根據這個算法 -
，如果你想與我漫步 - 要泡了，因為他做的第一時間，
所有的方式結束。
但是，假如博文旁邊的人是7號。
我要回去拿7號，這意味著我必須去所有的方式回到這裡。
現在，我必須有同樣的散步，誰是7號的人。
但是，6號他旁邊的是什麼？
然後，我要回去，並得到6。
所以，再一次，我說的就是這個循環的每個迭代的n每個人，
我可能使n，這些散步，以確保我拉
所有的最大的元素和背部，到了最後的名單。
所以N的n次，n次n或n的平方。
>> 所以在這裡，我們已經有一個算法，不再n，即不再日誌n，
它實際上比我們以前做過的任何事情更糟糕。
因此，亞歷克斯種很幸運，我做了所有的工作顯然她的面前，
所有的昂貴的工作，這樣她就可以享受在這個二進制搜索算法，
這是日誌的n。
但是，這與週一的主題是一致的。
我們給多一點點空間，我們使用的位數越多，為了加快我們的運行時間。
因此，很像有這個時間和空間之間的權衡，
也有可能是權衡之間花費的時間前樣的東西準備去
實際執行的算法，如搜索。讓我們嘗試另一種。
如果你們不介意只是快速地重新安排自己再次匹配，
讓我們嘗試略有不同的東西，這是不是很簡單
作為剛修好的的成對錯誤，這是超級直觀的。
的，而不是讓我們多一點故意做這個。
這一次，我也將提出可能是非常直觀的。
>> 讓我們從列表中選擇最小的人一次又一次地。所以，在這裡，我們走了。
4，你是我見過這麼遠的最小的人，
所以我要精神上記住，只是指著你現在的。
2。哦！忘記4號。我剛剛發現的最小的元素在此列表中。
我要種記住這一點。 6，8。
哦！ 1。再見。所以現在我會記住數字1。
我們知道，1是最小的，但我的電腦。如果有一個0？
如果是-1？我必須繼續下去。
因此，3，7，5，沒了。好吧。因此，數字1是最小的。
讓我從列表中選擇你 - 我們就會走這條路 -
任意把你在年初的列表。
現在，等待一分鐘。我有種上當受騙。
如果這些人不是代表8人，而是一個數組列表，
8的連續內存塊 - 你不介意退一步就一下嗎？
實際上，有沒有空間，你在這裡。
那麼，如何才能使空間 - 你叫什麼名字？ “薩米。 “薩米。
我們如何讓空間為薩米？
>> 我們將n表示在我面前。 “好了。
因此，我們可以把n個人在他面前的人，
所以如果你們想故意的，戲劇性的一步到左邊。
他們都做到步調一致，但我最後一次寫了一些代碼，
你不能排序的移動很多事情都在。
我們可以做一個循環中，每個人都曾經在一段時間移動。
所以，如果你們不介意退一步的權利，
和Sammy，如果你能後退一步，因為還是有沒有為你的房間，
現在讓我們做到這一點。是Sammy剛才？就在那裡。
所以還有一定的差距。所以，你可以移動到Sammy的點。
旁邊的人了，現在旁邊的人，旁邊的人。現在我們有房為薩米。
現在，有人從觀眾 - 這是很好的，這是正確的，
它覺得有點費時的 - 什麼是快？是啊。
[學生]一個新的陣列？ >>那是什麼？ >> [學生]一個新的陣列？ >>好，好。
>> 公正的貿易平衡，符合這個主題，為什麼沒有我只是一個新的數組
然後Sammy將游泳在這些人面前的空間，例如，
我們就可以開始填充一個新的數組。這也是工作。
但我不感興趣花費更多的空間。另一種方法是什麼？
[學生]交換。 “好了。我們可以交換這兩個傢伙。你叫什麼名字？
馬里奧。 “馬里奧。所以，馬里奧，你目前在這裡。
薩米，你可以備份只是一瞬間嗎？馬里奧在這裡。
我們沒有你的空間了，所以，如果你不介意的薩米是，
我們就會把薩米在這裡，現在我要說的是Sammy的交換操作的速度更快。
我們做了的交換操作這些傢伙，也許2交換這些傢伙，
但我們沒有做1，2，3，4，這樣的感覺更好。現在，等待一分鐘。
我種使問題變得更糟，因為4種接近年初。
4號是為此一點點接近，但我真的不知道或關心的。
因此，這只是運氣不好，4號是一點點遠離其注定的地方。
現在讓我們重複這個算法。
>> 總括來說，只要這個故事，所有我們所做的只是遍歷這個列表
尋找最小的人。
所以，現在讓我們再做一次。我們不必擔心薩米了。
我們可以去這裡。哦！編號2。這是一個非常小的數字。
6，8，4，3，7，5。好，好。
幸運的是，巧合的是，我沒有動 - >>威利。
威利，因為他是在他的正確的地方。
讓我們再這樣做，而忽略這兩個傢伙。
6。這是一個非常小的數字。哦！ 8肯定是更大的。
4。讓我們把注意力集中在4。哦！ 3，甚至更好。
7和5。那麼，我們該怎麼辦 - >>羅傑。 “羅傑？
讓我們來交換他的6號。
所以，如果想6和3交換，
我們現在已經種得到幸運的，6是接近的地方，她應該是，
但在這裡只是巧合。現在讓我們去這裡。
圖8是一個非常小的數字。哦！圖4是較小的。
6，7，5。什麼我們現在做的嗎？ >>交換。 “沒錯。
所以，現在讓我們做這種快。
8，6，7，5。哪裡5去了？好。好吧。
6，7，8。 6到留在她。你叫什麼名字？ “羅莎莉。
羅莎莉可以留在她。 7到 - 讓我們來看看。 7，8。好吧。
所以得到保持，她是。你叫什麼名字？ >> Amna。 >> Amna。
>> 所以Amna可以留在她的是，與已經在那裡他現在應該是8號。
好，好。感覺就像我們剛剛為自己創造工作，在這裡，雖然。
最後該算法的運行時間？
如果我們認為這些人不為8，但為n？ >>的n。
它的n個步驟，但我們每一次檢查。
好吧。 N而你每一次檢查？
好的，但如果它的n個步驟，不應該我已經能夠為您解決您正要1，2，3，4？
哦！好了，這是一個很大的區別。
因此n的平方為什麼呢？到底發生了什麼？
在此列表中有n個人，而是要找到列表中的最小的人
在最壞的情況下，我要採取許多步驟？ >> N.
>> N，對了，因為在最壞的情況下，1號是一路那邊，
所以我必須去得到他或她的。
然後當我終於實現1是最小的，那麼它是相當快的交換。
但現在我必須從頭開始，看是誰嗎？
下一個最小的人，這是2。凡在最壞的情況下為2？
哦，我的上帝。這一切都在這裡結束的方式。
所以，現在我只是做了另一種n步，另一個n個步驟。
如果我們有n個人，在最壞的情況下，最小的人是n步之遙，
這再次n次，n，且讓我們再次有n個平方。
這是不是感覺這麼好。
而事實上，即使在最好的情況下 - 假設他們開始排序 -
它需要多少步我使用這種算法排序N多人嗎？
Ň的平方。 >>我聽到Ň的平方。為什麼Ň平方？
因為你仍然必須檢查每一個時間。 >>呀。
你有來交換他們。 ，>>即使我們人類是一種全知
在這個意義上，視覺上，我們就可以看到，這是排序的種，
一台計算機是沒有那麼聰明。
要看看這裡和這裡和這裡，
但如果它在尋找什麼是最小的元素，
你只知道你什麼時候發現的最小元素？一旦你在最後。
但在這一點上，你只找到了目前最小的元素。
你不一定知道別的世界的狀態。
所以，你必須去再，再而三。
>> 所以這一次我真的看起來愚蠢的，因為，好吧，我檢查2，你是最小的，
但我不知道，在總。
3，4，5，6，7，8。好，好。 2確實是最小的。
現在，讓我們找到下一個最小的。好吧。
3，你是目前國內最小的。讓我們來看看。 4，5，6，7，8。好了，很幸運的了。
3確實是在正確的地方。但我會繼續這樣做，再，再而三。
我們怎樣才能做到以往任何時候都稍微好一點的呢？
相反的人，泡了從最小到最大的兩兩
，而不是在列表中選擇了當時最小的人來來回回，
我們為什麼不，而不是將這些人進入一個新的列表步驟一步？
讓我們來試試這個。現在讓我叫這個東西插入排序。
所以，在這裡，我們都在這裡。號碼1。在此列表中的其他任何人，我不在乎。
現在我的目標是把1號的開頭的排序列表。
我要提出，因為我只有8個內存塊，
隨意現在的我，我的所謂的未排序的列表之間的牆，
和任何人誰是在我後面我稍後會要求進行排序。
所以現在我們有數字1。
我想，插入他到我的排序列表，所以在這裡，我只是將我的牆上，
現在我要求這個列表進行排序，這個列表是無序的 - 至少據我所知。
一次，我不能看到所有的數字。
>> 現在，我碰巧遇到2號。和他一起，我該怎麼辦？
我你現在插入排序的列表。但是請注意，這是多麼容易。
我只需要看看。 1號是存在的。哦，顯然2進入1號側。
現在我該怎麼做3？我你進入插入排序的列表。但是，這是超級容易。
這是超級容易，這是超級容易，這是超級簡單，超級簡單，超級方便。
進行排序，現在一切都在我的身後，並沒有多少步驟，採取？
[學生]。>>因此，它只有n。我們很幸運。
這是只有n個為什麼？ >> [學生]因為該列表進行排序。
已排序的列表。因此，我們很幸運。
但是，我們設計了一個算法就是這樣的運氣，利用這個時間，
，最好的情況下，不浪費不必要的時間。
所以，我們現在有什麼，我們會打電話給泡各種
人們泡了兩兩種。
我們現在有選擇排序，我們剜出最小的人，一次又一次的。
現在，我們有插入排序，排序的主動放人屬於他們的地方
在一個日益排序列表。
如果我們可以，這些傢伙在這裡的一片掌聲。 [掌聲]
讓我們以我們在這裡休息5分鐘。
當我們回來時，我們會吹出來的水的所有這些算法
更好的東西。好的。非常感謝。您可以保留這些作為紀念品。
好的。我們又回來了。
>> 重溫一下真正的快，我們有3種不同的方法來排序，
這是整點到這一點，如果有人像Alex
可以搜索列表中的數字更快，比別人像肖恩可能。
即使我們有這樣的簡單的例子，8號，
你可以推斷輕鬆地以8個網頁，8億個網頁，
還是800萬Facebook上的好友。
因此，這些算法當然可以擴展到那些種值，
和想法，最終都是一樣的。
因此，冒泡排序是第一次在這裡我們種冒泡最大的人
所有的權利人兩兩交換。
然後，我們有什麼，我們會打電話給選擇排序，我有點刻意地
一直在尋找在列表中，選擇最小的數字，一遍又一遍，並再次，
其中的邏輯結果是，最終的排序條件列表。
然後在第三個問題，我插入到適當的地方的人，
我們做了一個很做作的例子，在已排序的列表，
但發送消息，在插入排序的情況下，
你可以得到幸運。
如果已排序的數字，它只會帶你n個步驟盡可能多的確認，
而選擇排序中，你多一點的隧道視野
和你也沒有意識到已經排序的列表。
因此，讓我們看到冒泡排序在這裡的行動。
在下面的例子中，我們看到豎線
其高度的號碼，以便我們可以排序的可視化排序發生。
酒吧，較小的數字越小;酒吧越大，數字越大。
>> 我們將發揮它在此默認速度。
這將現在移動快了一點，但紅色是什麼2條
並排比較。
如果你仔細觀察，會發生什麼情況是，如果酒吧秩序，
中較小的一個被移動到左側，右側的大的一個，
然後你繼續前進。
因此，如果我們這樣做了一遍又一遍，注意到最小的酒吧
要保持緩慢的左
最大的酒吧，要保持緩慢方式的權利。
事實上，我們已經開始看到一個模式的右手邊一路
就像我們看到8和7最終冒泡到盡頭，我們的人的名單。
所以，這是怎麼回事能很快地得到一個有點乏味，所以讓我停止了一會兒。
讓我改變的速度要快得多。
我不會改變的算法，我只是讓，動畫得更快。
冒泡排序，相同的算法，
但現在你可以看到速度遠遠超過我們的口頭示範
最大的元素確實冒出來的頂部。
>> 順便說一句，這些小方塊在左下角和右下角
只是為你做多少次比較小提醒。
但就目前而言，我們可以將精力集中在金字塔的形狀，就這樣吧。
最小的元素是在左邊，在右邊的最大，並在兩者之間的一切。
現在讓我們來看看選擇排序，而不是採取。
我要繼續前進，點擊停止。我們將得到一個新的隨機的酒吧。
選擇排序，回想一下，在列表中再，再而三，
採摘最小的元素。因此，這裡的選擇排序。
它看起來像有較少的工作，現在發生的，因為我們還沒有比較成對
但我們只是櫻桃採摘最小的元素由右至左排序。
這花了很短的時間，因此已經有一個二分法。
僅僅因為一個算法取n的平方時間，如冒泡排序
如選擇排序，這些都是真正的最壞情況下的運行時間。
例如，在的情況下，讓我們說，選擇排序，
其實，我選擇最小的人，並把他或她在這裡，
然後我做了一遍，然後我做了一遍，
但有輕微的優化，我可以做的。
>> 當我在這種情況下，移動數字1 - 薩米 -
什麼，我需要做的，他此後嗎？ >> [學生]離開他。
離開他，對不對？什麼也沒有。
我並不需要再次薩米交談過，因為如果我選擇了最小的元素
在這裡，把他，為什麼要浪費時間去年底我的整個列表？
在接下來的迭代，讓我實際上只移動到2號，3號。
因此，在現實中，我沒有做N Things的n倍。
我是做N Things的，然後再有n - 1的東西，那麼n - 兩件事情，那麼n - 3樣東西，
那麼n - 4，點，點，點。
我們有一個幾何級數位，這意味著
你逐漸變小的數字相加。
不是N + N + N + N，但N + 7 + 6 + 5 + 4 + 3 + 2 + 1。
有什麼工作是 -
我要搞砸了我的板只是一個瞬間 -
的去上班了的東西，如N（N - 1）/ 2
如果我們只是看看後面的一本數學書，你把所有的作弊表，
的公式。
如果你只是增加一些N + N - 1 + N - 2，它的工作原理是這樣的。
如果我們只是種繁殖了這一點，該公司的N平方減去n / 2。
我一直說Ň平方，雖然，那是因為我是一種精神的快捷方式
因為在現實中，N的平方減去n除以2，的確是真正的步數
選擇排序算法，像如果我們真的計算
所有這些比較，所有的小繁忙的工作中，我們正在做。
但坦率地說，當n變得像一百萬或一個億，到底誰在乎
如果你正在做一個億平方減一億美元，除以2？
有十億平方是​​一個龐大的數字。
你可以把另一個十億它關閉 - N。這不是什麼大不了的。
因此，更大的數字，不太重要的低有序的條件。
誰在乎你，如果你在談論的十五次冪的步數除以2？
>> 因此，在一般情況下，計算機科學家傾向於扔掉一切，但最大的一屆，
我們只是種簡化了世界，並說該算法
花了大約ñ平方的步驟。這是一個算法的運行時間。
所以，我們會回來，這只是一瞬間的一些具體的例子，
但現在，這樣的直觀的動機只是簡化了我們的世界背後
和談論的最重要的條件，而不是進入所有這些花哨的公式。
因此，選擇排序，和我們有點幸運了。
讓我們來看看在插入排序。讓我繼續前進，開始這個。
現在的模式發生的事情是，有一點不同，
我們開始用隨機數，
但是如果我們實際上在最壞的情況下，向上計數的步數
如果該列表以正確的順序，全面啟動
我們將只需要n個步驟，盡可能多的實現。
>> 但是，如果該列表實際上是向後 - 例如，這裡在這種情況下 -
然後發現，其實我們要在這種情況下，做了很多的工作。
它應該那種感覺，你喜歡這個人是種更努力地工作
讓那些更小的元素的左側，這是因為我們有不吉利的。
意外的反向排序的列表。
與此相反，插入排序，如果我們模仿我們所做的與我們人類在這裡
開始大家一起排序，然後再啟動，這是一個相當不錯的算法，對不對？
，事實上，它已經排序。
因此，讓我們嘗試總結到底有多少時間，這些東西都是我們
通過引入只是有點術語或符號，這實際上是更簡單
比花哨的建議。
這件事在這裡，大O在屏幕上，是一個計算機科學家通常會使用
來描述的算法的最壞的情況下的運行時間。
>> 同樣，最壞的情況下，這是完全依賴於上下文的。
我們所說的最壞的情況完全變化的基礎上的，我們正在談論的問題。
但在排序的情況下，可能出現的最壞的情況嗎？
是倒退，因為它只是感覺一樣，這意味著大量的工作，為我們的一切。
我已經記下了幾個到目前為止，我們已經看到的算法：
線性搜索，二進制搜索，如電話簿或紙片，
然後像冒泡排序，選擇排序，插入排序，我們看到了我們人類，
，然後，最終將被稱為歸併排序。
因此，在最壞情況下的線性搜索，多少步它採取尋找數字7
如果有n門像肖恩面嗎？ >> [學生]。
N.所以我們要編寫大O的n。
我只是要填補一些空白。這僅僅是一格的空白。
但在最好的情況下，線性搜索，7可能會在一開始的列表，
和肖恩可能已經開始尋找在開始的列表。
所以，如果你正在使用的線性搜索和檢查左到右，或可能是從右到左 -
它們是等價的 - 在最好的情況下，多少步線性搜索，
像肖恩的算法？只有1步。
>> 所以我說這是歐米茄符號。
這是只是資本歐米茄。
歐米茄只是說最好的情況下運行時間的性感方式。
因此，在最好的情況下的運行時間是一個單一的步驟或步驟的恆定數目的 -
在這種情況下 - 但在最壞的情況下，大O，它實際上是n個步驟。
這一個在這裡，θ，我們其實並沒有去看看現在。
這個特殊的例子是不相關的。
但現在讓我們嘗試二進制搜索。
用二進制搜索在最壞的情況下，多少步要採取尋找數字7
或任何我們所想要的？ >> [學生]登錄N。
仍然要採取日誌n，因為就像亞歷克斯把倒霉的
當我們真正的工作有條不紊問題
和她沒有發現，直到最後的門，她看著7號，
儘管，在公平，她扔掉了一定的門前進的道路上，
在最壞情況下的二進制搜索日誌n的運行時間。
再次，這充分說明這個劃分和征服。
但是，在最好的情況下，又如何呢？
和亞歷克斯親身經歷，最好的情況下，當她來到了舞台上。
多少步驟，在二進制搜索？ >> [學生] 1。
1，只因為她是幸運的。
但是，這很好，因為歐米茄是最好的情況，
最好的情況下輸入，即使它只是隨機的好運氣。
>> 現在，我們也要去到只是休假空白的種，現在。
現在怎麼樣冒泡排序？
冒泡排序在最壞的情況下，每個人都在以相反的順序，
因此，我們做了很多的氣泡。
但究竟有多少步驟，要在最壞的情況嗎？ >> [學生] N的平方。
這是n個平方，因為如果你仔細想想，
如果該列表是完全向後 - 8是在這裡，就在這裡 -
事情開始泡沫，8號移動方式，這種方式，
這種方式，這種方式，但如果是7號，在最壞的情況嗎？
在這裡，她仍然在那裡。所以，我們做了一遍又一遍。
這就是我們得到n個步驟，然後再有n - 1步，然後再有n - 2個步驟。
如果你把我的話 - 如果你種繁殖出來，
它的大致Ň平方一些其他條款，我們將不理會現在的中端 -
然後在最壞的情況下，冒泡排序為n的平方，給予或採取。
但最好的情況下，冒泡排序呢？
最好的情況是什麼？所有的數字進行排序了。
是什麼啟發我所用，我用的伎倆，
意識到，我已沒有工作，因此提前停止嗎？
[學生]檢查一次。 >>檢查一次。但什麼是我做沿途嗎？
我跟踪我做了多少掉期。
我意識到，如果我沒有任何掉期計算我的手指，然後我做了沒有工作。
我當然不應該再嘗試做任何工作，這樣我就可以停止。
>> 因此，在最好的情況下，冒泡排序的列表時，已排序，
你會說什麼的歐米伽符號，最好的情況下運行時間？
這只是N。我們做了一些工作，但我們只需要做1漫步的價值，工作。
在這裡，我要離開這部分空白。
和現在選擇排序。
選擇排序我拔最小的人一遍又一遍。
的運行時間，這是我們說什麼？
這在最壞的情況下為n的平方。
不幸的是，在最好的情況下，它也是n平方
因為我不擁有那種無所不知的觀點對整個世界;
我只知道，我確實發現了一個完整的迭代最小的人。
因此，選擇排序種吸在這個意義上，
但好處是它的一種直觀。
這是很容易的代碼，因為所有你必須做的是寫一對夫婦的嵌套循環，
通常情況下，通過尋找最小的元素
然後把在列表末尾在它所屬的最小元素。
因此，這裡也有將是一個權衡。
它需要你去思考，去開發的東西，通過編寫代碼的時間量
很可能需要更多的時間，如果你想有一個更好的算法和更快的性能。
>> 但是，如果你真的只是種代碼的東西了快速和骯髒的
只是一種最愚蠢的想法，你能想到的，
可能你幾分鐘的代碼，但與大型數據集
你的算法可能需要幾個小時才能運行。
甚至我在讀研究生，有時會這些權衡。
這將是凌晨3點，我嘗試分析一些非常大的數據集
我是這樣做的安全性研究，這是不是花5分鐘
調整我的程序的數據進行分析，並去睡覺
或花8個小時，得到它恰到好處，所以它運行的瞬間，而不是去睡覺。
因此，也有它是一種有意識的決定。
開發時間少，更多的睡眠。
回想起來，我可能不應該鼓勵
當這裡的目標是優化的代碼質量，
但同樣在現實世界中是一個非常合理的折衷。
更少的時間，更少的性能，反之亦然。
所以，在這裡，我們終於有機會談論THETA。
θ符號是計算機科學家們可以在談話中帶來
大O和歐米茄發生是相同的。
你說THETA真正地發送消息，這是一種緊張的約束。
無論情況是好還是壞，它的N的平方。
因此，它是不相關的故事在這裡。
插入排序是最後一次，我們看到了，
我只是將每個人放到合適的地方。
在最好的情況是插入排序的運行時間，因為我們在這裡看到了嗎？
[學生]：最好的情況是什麼？ >>最好的情況。
>> N，因為在最好的情況下，每個人排序，
和薩米並沒有其他人真的有移動。
他們已經在他們的正確的地方。
所以插入排序在最好的情況是，在這種情況下，正。
但是，在最壞的情況下，它是一種n個平方。為什麼呢？
如果我名單上的人是相反的順序，
我第一次從8號開始，我將他或她進入正確的位置，這是在這裡。
我種移動到側邊。這些傢伙是無序的，他或她進行排序。
但現在，我偶然發現誰後呢？ >> [學生] 7。
7在最壞的情況下，因為它是在相反的順序。
>> 因此，這裡是7。 7屬於哪裡？肯定在我身後。
但現在7實際上不屬於我，但緊隨其後的8號後面，
所以我說，“對不起，8號，可以請你移動這樣
“7，以騰出空間嗎？”現在我遇到6。
“哦，對不起，8號和7號，你可以移動，以騰出空間為6？”
所以，換句話說，插入排序，即使我沒有做太多的運動，
我後面的人做更多的工作，而這得到了，以耗資有人時間。
它要花費計算機的時間。
因此，在插入排序的情況下，我們仍然深受其害。
如果你開始添加的總步數，我們最終打大致Ň平方
因為這些傢伙需要的人要插入到該列表中，以騰出空間。
因此，在這種情況下，Theta是不是適用於特別在手的故事。
這是所有好和好。我們有這3種不同的方式談論的運行時間。
但是，什麼這實際上意味著在實質，如果我們真正嘗試編寫一個算法？
>> 最後，我提議，有一個更好的算法有
本身具有一定的取捨。
我們把它稱為歸併排序，它是這片神奇的算法排序
工作快弄好了，它是如此容易表達，至少在偽代碼。
該算法的合併排序的實施將是如下。
當你給定的n個元素 - n個數，n個人，不管是誰 - 第一次有一個完整性檢查。
如果n小於2，歸併排序只是停止。它返回時，這麼說。
為什麼你會停止，如果n是小於2？ >> [聽不見的學生反應]
右。並再次，n不為在列表中的數目，n是列表的大小。
如果n小於2，這意味著你的名單是1，
你很明顯排序的，如果是1號，
或0，在這種情況下，沒有什麼排序，
因此，我們需要這種形式的基本情況。
如果該列表是如此之短，只是沒有做，確實沒有做任何事情。返回。
否則的左一半的元素進行排序，然後排序的右半​​部分的元素，
然後合併排序半。
>> 這種看起來像一個小騙子，我問你如何排序的元素
你告訴我“的左半部分進行排序，排序的右半​​邊。”
我想，“好吧，你怎麼排序的左半邊嗎？”
“排序的左一半的左半邊，排序的左半邊的右半部分，然後完成。”
你是週期性的定義是什麼意思排序，
但事實證明，在這種情況下，這實際上是輝煌的。
這不是真正的這種惡性循環永遠不會結束
因為它結束的時候嗎？ >> [學生]當你達到10件事。
當你達到10件事。
因此，即使你可能會開始有8人，和我說，這些人“之類的左半邊，
這4人，“然後我說，”怎麼你的左半邊排序嗎？“
“好了，在這裡的2人進行排序。”然後你會說，“好吧，好吧。”
“你是怎麼排序的左半邊這些人嗎？”
“只是有點這個人在這裡。”現在的輝煌啟示什麼？
我有，排序1人。完成。我沒有做任何工作。
但現在我要解決的這個人，但他們是一個人，沒有任何關係。
>> 因此，魔術顯然是在這第三步：合併排序的一半。
所以，歸併排序這輝煌的洞察力，如果你打破一個大問題分解
2個較小的，相同大小的問題
，然後就種膠更小的解決方案結合在一起結束時，
我建議，我們可以做的更好的[點擊音]
選擇排序或插入排序。
其實我已經忽略了半小時，但我真的不知道這是怎麼回事
今天外面。 [呼呼的聲音] [笑]
因此，讓我們看看我們可以看到這一點幫助我們的朋友羅布·鮑登。
歸併排序的過程中，有2個大的步驟。
首先，連續分裂列表杯分為兩半
直到我們有一堆名單，他們只用1杯。
不要擔心，如果列表中包含一個奇數
你不能讓他們之間的一個完全乾淨的切割。
只需隨便挑哪一個清單，包括額外的杯子中。
因此，讓我們這些列表拆分。
現在，我們有2個列表。
現在，我們有4個列表。
現在我們有8個列表，每個列表中的單杯。
所以這是它的第1步。
對於第2步，我們多次合併對使用合併算法，我們以前學過的列表。
合併108和15，我們結束了15日，108。
，合併50和4，我們最終有4個，50。
，合併8和42，我們有8個，42。
合併23和16，我們最終有16個，23。
現在我們的列表大小為2。
請注意，每個的4列出的是排序條件，
這樣，我們就可以開始再次對列表合併。
合併15和108以及4和50，我們先來的4個，然後15，
然後是50，那麼108。
合併8，42，16，23，我們先來8，那麼16，
然後是23次，然後在42。
所以現在我們有2列出了大小為4，每一個排序。
所以，現在我們合併這兩個列表。
首先，我們乘4，然後我們乘坐8，然後乘坐15
和16和23和42和50和108。
我們就大功告成了。我們現在有一個排序的列表。
>> 羅布樣的東西，我們尚未利用。
有人建議，但我們並沒有真正做到這一點。
他是做一些身體上的杯子，建議
他花了一些資源，除了時間。 >> [學生]空間。 >>空間。
事實上，他有這種雙向電平表空間，在那裡，他在這裡
和下行空間在這裡實際上是暗示，他用兩倍的空間
因此，我們的算法 - 插入排序，冒泡排序，選擇排序 -
但他卻利用這一額外的空間來搬東西來回種
而為了讓事情。
即使感覺就像我們到了一個排序的列表，感覺就像過了好一會兒。
在現實中，羅布做什麼的就是這樣一個算法。
他首先把大小為n的問題，把它分成的左半和右半。
這時候，他感動的杯子。然後，他重複了這一過程。
他在這裡和在這裡的2台2分4。
然後，他重複了這一過程，這些不同的杯子2套1分2。
而這正是輝煌的機會出現。
羅伯的故事在這一點上，有8個大小為1的列表，
所有這一切都已經進行排序。
>> 那麼，他怎麼繼續做？
成對他把這個排序的列表，這個排序的列表和它們合併。
然後，他把這個和合併他們，那麼這個人，合併他們，
那麼這個合併。
然後他做了什麼呢？
然後，他重新合併的大的列表，然後再重新合併的大列表。
如果你認為這只是直觀的，現在，什麼是他真正在做什麼？
他一半除以問題，在一半，在一半，在一半
為了得到這些超小的列表。
他是那種相結合的一倍，兩倍，一倍，兩倍。
所以，他在做什麼的兩倍多的工作，到目前為止，我們已經看到的
與任何涉及分而治之，但沒什麼大不了的。
雙倍的工作是沒有什麼大不了的。這只是一個常數因子。
就像我們算術表達式之前，我只是要過的常數因子
如2次。誰在乎呢？如果它是20億倍，這仍然有很多步驟。
所以此合併似乎是關鍵的洞察力。
讓我們通過這只是數字前 - 噢，那是不是要繼續還。
讓我們通過這個數字只是實際看到了。
這主要是一點點可憐的人的動畫。
我們的建議。
合併排序的運行時間 - 我們只需要在談論這個問題的一種方式。
這不是數學，這僅僅是一個簡潔的方式表達自己種。
因此，T代表時間，n代表什麼？ >> [學生]的大小 -
>> [馬蘭]的問題，大小的人數。
因此，我要求的運行時間排序n的人將是0的時間量
如果n小於2，因為如果你1杯或沒有杯子，你有什麼排序。
但更普遍的是，我要提出的運行時間進行排序n個元素
將是所花費的時間，以排序的左半加右半
加 - 這是什麼額外+ N？ >> [學生]歸併排序。
[馬蘭它實際上是合併，因為如果你有N / 2個元素
你這裡有n / 2個元素，多少時間需要將它們合併？
就像羅布，你必須在這裡採摘這一個，也許採摘在這裡，
在這裡採摘，採摘在這裡，在這裡採摘。
您擁有一次觸摸的杯子。
如果有4杯加4杯，8杯
或者，更普遍的是，8正杯。
因此，合併步驟中，我們可以表達為n，
並且，從字面上涉及的次數羅布物理觸摸
這些保麗龍杯。
現在讓我們做一個任意的例子。
如果有16杯，運行時間排序，Rob的算法，16杯嗎？
它的2倍量的所花費的時間排序8杯
因為在這裡，我們有8杯8杯。
我不知道需要多久，所以我們概括為T的時刻。
誰知道它是什麼呢？
但現在我可以按的遞歸或重複問同樣的問題。
需要多少時間排序8杯水嗎？
8杯，我說需要花費的時間進行排序4杯加4杯量，
然後把它們合併在一起。
精細。我們正在進入一個循環了。排序4杯多久？
所花費的時間進行排序4杯2杯加2杯排序，加上合併過程。
精細。排序2杯多久？
2杯的時間量，它需要進行排序1杯加分類，另一杯所花費的時間
加量合併所花費的時間，這僅僅是2。
>> 精細。最後一個問題。排序1杯多久？
這是我們預測的基本情況，我們會稍早觸及的。
事實上，它沒有任何排序的最小的問題
意味著，現在，類的小學風格，
我們可以去堵塞這些數字。互動式
現在，我們知道T的1是什麼，這樣我就可以插入T的1 0。
這將會給我的答案為T 2，然後我可以插在更高了。
這將讓我的T 4，我可以插在更高了。
這將讓我的T 8，我可以插在更高了。
如果我真的做出來的，這些問題的答案堵在數學上，
然後我得到的​​T 16是64。
64代表什麼？
如果T是16，是的，這16次4。
因此，我要求這件事情，現在的運行時間稱為歸併排序 -
這將是迄今為止，我們已經看到了奇 -
將被稱為n日誌n
因為可以搶多少次分裂一大堆杯的一半嗎？登錄N。
這是相同的電話簿的例子，這是自計數的例子一樣。
>> 多少次，你分了一半的東西嗎？
然而，有此合併的步驟。
您可能要分杯一而再，再而三成半，
但每次你要合併。
我們前面所說的，合併Ň杯需要n個步驟
因為你必須鼓起了一杯，剜出一個杯子，你必須觸摸每杯一次，
就像搶一樣。
因此，如果我們正在做的事情log N次，我們正在做的N Things的這些迭代，
這些halvings，我們有n次日誌n。
因此，如果我們插入在16在這個例子中，16次記錄16 -
不要擔心，這是為什麼現在的情況，因為我從來沒畫的基礎 -
但日誌16基座2是4，16倍，4是64。
但相反的，如果我們使用冒泡排序，選擇排序或插入排序16號，
什麼的運行時間，如果n為16？
這將是16平方，這是256，即使你還沒有完全遵循了所有的數學，
256是大於64。這真的是神奇的外賣。
並認識到，通過在較小的例子，你會工作的pset
使得一切更加直觀。
但是，什麼是真正的意思的感覺，這種算法是這樣的：
如果我們看一下這裡的歸併排序 - 讓我在此窗口中拉起來 -
這是一個略有不同的例子，我們有所有這些算法 -
泡沫，選擇和合併 - 只並排。
>> 他們都開始用隨機的酒吧，這是很好的。
沒有人有一個比其他的基本優點。
我要在瞬間點擊這些動畫 - 開始，開始，開始 -
這樣一來，我可以粗略地說，他們都在同一時間開始，
讓我們來看看，冒泡排序的最壞情況下的運行時間是什麼？ >> [學生] N的平方。
Ň的平方。選擇排序的最壞情況運行時間是什麼？ Ň的平方。
和合併排序是很明顯的 - 即使你不太明白，現在所有的數學，
它會隨著時間的推移變得更加直觀 - 是，我們主張，n次日誌n。
因為日誌，n是嚴格小於n一旦我們有很大的數字，
n倍日誌n是小於n次n或n的平方。
那麼，這是什麼感覺，實際上是一個更好的算法的運行時間，
n次日誌n，而不是為n的平方？在這裡，我們走了。單擊開始，單擊，單擊。
>> 這就是它使用類似歸併排序。
我們有一個時刻。讓我們來看看這裡發生了什麼。
[笑]冒泡排序是誰的錢？
而有時取決於輸入。
讓我們來看看。
來吧。我覺得他應該正在迎頭趕上。 >> [學生]，冒泡排序！
[學生口中念念有詞]
[馬蘭]是啊，是啊。
[學生口中念念有詞走，走，走！
[歡呼] [掌聲]
1日，最後的演示，所以現在如果它是一個小技巧來包裝你的頭腦圍繞數學
那裡的可視化排序，你實際上可以聽到的速度
不同的算法不同。
這是一個動畫的人，其實聽起來就
的交換的方法和對條形高度的。
正如我們將要看到這裡，有幾個排序算法，在那裡，人們想到。
這第一個將是插入排序，這將飛過
給你的感覺如何將這些不同的算法工作的聲音。
這裡是插入排序。
[電子蜂鳴聲]
[馬蘭]冒泡排序。
[更快的電子蜂鳴聲]
[馬蘭]選擇排序。
[更快的電子蜂鳴聲]
[馬蘭]歸併排序。
[電子蜂鳴聲]
[嗶嗶減慢] [笑]
[馬蘭]地精排序。
[電子蜂鳴聲]
>> 這是CS50。我們會下週見。 [掌聲和歡呼]
>> [CS50.TV]