演講嘉賓：好的，這是CS50。 這是3週結束時，如果 你有沒有冤大頭不已， 知道，會有午餐 這個星期五​​和往常一樣，在那裡 您可以享受良好的交談 食品在火與冰 一些CS50年代 工作人員和同學。 前往這個網址在這裡。 現在，你可能還記得，或者你 可能很快被認識， 這些東西在這裡，這 在最後給出了 的學期很多類。 所謂考試藍色書籍，其中 你寫你的答案考試。 現在我已經在這裡等26 藍色的書，對他們每個人 通過Z.寫著的名字，a和 不愧是名是簡單，一 到Z和一 手頭今天的目標 將是繼續什麼 我們開始在星期一，這是不 這麼多看代碼，但真正 尋找思路和解決問題的能力。 其中一個目標， 本課程的承諾 是教你去思考更多 細心，更有條理， 並且更有效地解決問題。 事實上，我們能做到這一點真的 甚至沒有觸及一行代碼。 所以，我有一對夫婦的大象 在這裡今天，橙，藍， 如果我們能找到一名志願者， 也許從更遠的背面比平常。 怎麼樣在那裡，下來吧。 它的目的將是對 幫助再加上這裡管理這門考試。 你叫什麼名字？ 聽眾：瑪麗·貝絲。 演講嘉賓：瑪麗·貝絲，上來吧。 讓我的麥克風為您服務。 很高興認識你。 聽眾：很高興見到你。 演講嘉賓：好，讓我有 這裡藍皮書A到Z， 我要去假裝 我有一個學生， 而他們來的有點隨意 在三個小時的考試塊的末尾， 所以他們結束了在某些 半隨機的順序是這樣的。 現在，在短短的一瞬間你的工作是怎麼回事 以be--這其實是他們如何獲得 在結束時打開在 類，最有可能的。 你現在的工作將是，相當 簡單地說，這些藍色的書為我們梳理 從A到Z 聽眾：哦，這是 要帶下去。 演講嘉賓：我們會看 當你做到這一點，沒有壓力。 聽眾：沒有，沒有壓力或任何東西。 演講嘉賓：而且為了好玩， 我們提出了一個定時器。 聽眾：太好玩了，太好玩了。 演講嘉賓：我可以抱麥克風為您服務。 好吧，我們剛剛增加了一倍我們的速度。 所以在此期間，讓我帶來什麼 要成為瑪麗貝絲問題 是什麼，是她做的，怎麼會是 她打算著手解決呢？ 而事實上，你可能沒有 沒有想過的東西 如此簡單，當你挑選的 高達26本書就是這樣， 它確實有一個自然的 訂購他們。 過程是怎樣的 你實際上使用？ 它是相當隨機的只是 挑選你看到的第一個 並把它在它的地方？ 你首先將雙手左右 尋找，然後找乙？ 你看看在 他們兩人並排 而只是說，等一下，這 是不對的，然後交換順序？ 我們已經看到在週一 這有許多方法 在其中我們可以做到這一點， 的確，我們附近結束了， 我會留意可能 什麼瑪麗·貝絲在做什麼。 我們有幾堆，似乎一個 更大的一個，三個小的。 聽眾：我命令他們 當我找到兩封信 我知道是一起在一個序列中， 我把它們放在一起，讓我不 不用擔心保存 軌道書一整排的。 這只是，呵呵，首先， 我這裡有這個堆棧。 演講嘉賓：所以，幾乎像 拼圖的碎片 有合適的形狀，以 相互匹配。 聽眾：好看多了，是啊。 演講嘉賓：好的，優秀的。 現在每個這些 樁的大概排序？ 聽眾：是的。 演講嘉賓：好的，從A到Z的所有 沒錯，恭喜你，你做到了。 你有你的選擇。 藍？ 好吧，謝謝你了。 因此，瑪麗·都建議 什麼她的做法是， 但什麼是另一種方法，你如何 可能去整理這些東西？ 你會怎麼做？ 擊敗的紀錄會一直 一分鐘，50秒左右， 再加上那些我忘了算。 你會怎麼做？ 是嗎？ 聽眾：以堆棧。 從起始處開始。 請檢查您的論文。 如果最上面的一個是高 不是，也許，他們是， 底部的一個是 高，然後切換他們。 演講嘉賓：好，那麼開始 在頂部和底部， 然後你的工作方式 向內那樣，交換呢？ 好了，有點類似 在精神冒泡排序， 但選擇極端 不相鄰的對。 但是它的短是，有 當然了一堆不同的方式 我們可以做到這一點， 坦率地說，我覺得你真好 通過幾個途徑，對不對？ 你做那種四堆排序，並 然後有效地融合在一起。 那就是，敢說，另一 技術完全。 你沒有把它當作一個大的一堆， 你劃分的問題分為四個四邊形， 如果你願意，然後以某種方式 合併它們的末端。 因此，讓我們考慮，最終， 怎麼回事我們可以做到這一點。 我們形式化的概念 的冒泡排序最後一次， 和冒泡排序召回是一個 算法，我們可視化 八你的同學在這裡， 起初看似隨機排列。 然後我們決定成對的，如果 兩個元素是無序， 簡單地交換他們。 於是四加二 顯然失靈， 所以這兩個同班同學 交換位置。 然後，我們重複了四和六， 然後6和8，在每次迭代中， 移動到右側。 所以，給八人，有多少配對 比較我做了，而走路 左到右在一個這樣的迭代？ 有多少的比較？ 七，對不對？ 因為如果有8 人，但你有一雙 他們和你繼續前進 1跳的權利， 你不會有八 比較，因為你不能比較 對本身的元素，否則會 僅僅是毫無意義的，讓你有七。 或者更一般地，如果 我們有N多人，我們 做了N減1的比較 用冒泡排序。 所以，現在讓我們考慮如何好或 壞的泡沫實際上是排序，並嘗試 給自己用的詞彙 這在像這樣的批判算法， 很快我們自己。 所以，通過第一通 冒泡排序，在第一時間 我是從左邊走到對面的權利 現階段，我花了Ñ減1的比較。 而這將是我的 計量單位的，對不對？ 我是那種說話，散步， 有些快，有些慢， 所以我計算的秒數 沒有特別明顯的， 但計數的數目 我確實在週一的操作， 比較兩個人，那種感覺 就像衡量一個不錯的單位。 因此n減1的步驟是第一次， 但之後發生了什麼？ 什麼是一傳一上攻 通過其他未分類列表？ 你能告訴我該元素 誰是一路過來嗎？ 是嗎？ 這是最大的因素，對不對？ 第八，即使她 從這裡開始，我每次 對她比較 一個鄰居，她不停地 冒泡向右 列表中的右手側。 事實上，這正是 該算法得名。 現在，通過這一邏輯，有多少的比較 需要我做的第二次 我作出這樣的傳球從左至右？ Ñ​​減2，對吧？ 這純粹是在浪費我的時間，如果我 保持比較8人反對某人 別的，因為我們已經知道 她是在正確的地方。 所以這是一個比特的 優化，所以下通 將是加N減去兩個步驟 其中n是人的數目。 現在你可以種推斷，即使 如果你不是一名計算機科學家， 如何結束。 在此算法結束時，據推測 你有只是一個比較離去。 你有一種固定的 在案例二開始列表 一都失靈 並應一和二， 所以這個谷底的 加1最後的比較。 現在，點，點，點樣波是 手在一些多汁詳情 但我們只是繼續和簡化。 如果您還記得高 學校，坦率地說，很多你 有數學書的有 有點小抄 前蓋或 後蓋表明您 什麼系列求和樣 這最終加起來。 在一般情況下，如果你有一個 變量如N，而事實上這其中， 如果你看著你 老同學的數學書， 你會看到，這實際上 加起來這筆款項在這裡， n次Ñ減1都除以2。 所以現在我只想規定 這是真的，那麼對信仰的飛躍， 這就是這個總結 最多，我們可以 證明，在更一般的情況。 但現在讓我們展開了這一點。 因此，讓我們乘了這一點，所以這是 Ñ​​平方，減去N，所有除以2。 這真的Ñ平方， 除以2，再減去Ñ超過2， 所以這是所有漂亮和有趣。 但是，如果我們發生 現在Plug-in的價值呢？ 假設我沒有8 人，但說一百萬。 和一百萬只是因為 這是一個非常大的數字， 讓我們插上，在看看會發生什麼。 所以，如果我插上一百萬到該公式 我要拿到一百萬平方， 除以2，減去 萬元，除以2。 現在，那是要一樣的嗎？ 所以500十億，減去50萬元。 如果我實際上做 在數學，這表示 該排序一百萬 人與冒泡排序 可能要花費499999500000 在結束步驟或比較， 我們只是推斷。 這感覺很慢，但坦率地說 測量一個特定的輸入 像這樣，是不是所有的說服力。 但事實上，這確實表明，當n 變大，該算法 那種感覺差， 更糟的是，不然你真的 開始感受到了疼痛 冪，使得n的平方， 這些加起來非常快。 而這個細節不 失去了對的人，其實 幾年前，某參議員誰是 競選活動，坐下來接受採訪 與谷歌的埃里克 施密特，當時的CEO， 並與一個問題的挑戰 就像我們今天探討。 讓我們一起來看看。 [視頻回放] -Senator，你在這裡 在谷歌，我喜歡 認為總統的 作為一個工作面試。 現在，它是很難得到 一份工作，擔任總裁， 你正在經歷的嚴酷了。 這也很難找到一份工作，在谷歌。 我們有問題，我們 要求我們的考生的問題， 而這一次是從拉里·施維默。 What--你們覺得我 開玩笑，這是在這裡。 什麼是最有效的方式來 排序一百萬的32位整數？ -Well-- -I'm對不起，maybe-- 不，不，不。 我認為，冒泡排序 將錯誤的路要走。 -COMe上，誰告訴他的？ 我沒有看到電腦 科學的背景。 -We've了在那裡我們的間諜。 - 確定，讓我們問一個不同的 面試問題。 [完視頻回放] 演講嘉賓：所以說起 具體的數字，雖然， 不會是那麼有用。 這不是一個生活的一課泡沫 排序，給定一個億的投入， 可能需要多達500十億步驟。 你真的不能一概而論 從太有效 做出好的設計決定 編寫程序時。 因此，讓我們雖然把重點放在如何 我們可以簡化這個結果。 所以，我在這裡黃色高亮 n的結果的平方除以2， 所以一百萬平方 除以2，然後 我已經強調了什麼 最終的答案是 一旦我們減去關閉N除以2。 並聲稱我會做，現在是， 誰的心裡很不舒服，如果你減去了關心 一老一少Ñ超過2時，第一 這個公式的一部分，是這麼多的大嗎？ 它支配著其他 長期，N的平方除以2 如此多的大，顯然，作為 n變大像一百萬， 這是真的，在一個很大的區別 一天500十億之間到底 和499999500000？ 並不是的。 還等什麼，我們要 做計算機科學家是 忽略這些低階條款及 採取這樣的事情，真的 只需將它簡化為 術語，是怎麼回事無所謂。 在我們的大數據集得到的，更大的 我們的數據庫中得到的，就越網頁 我們必須搜索，越 朋友你在Facebook。 當n變大，我們真的 要關心大 長期在任何此類分析 我們的算法性能。 而我要說，你知道嗎， 冒泡排序是大O的順序， n的順序上的平方。 這不恰好n 方如我們所看到的， 但誰真正關心 那些小的方面， 坦率地說，誰真正 關心，如果我們除以2？ 這只是一個常數因子。 並為500十億與250 十億真有那麼大的一筆交易？ 我可以等一年， 讓我的筆記本電腦逐字 得到兩倍於硬件的速度， 等諸如此類的差異 剛剛消失，自然隨著時間的推移。 我們關心的是什麼 的表達，該部 那將改變表達的 作為我們的輸入變得越來越大。 事實上，在現實世界中， 這就是正在發生的事情越來越多 是投入到我們的問題， 算法越來越大。 因此，大O將是符號， 漸近符號，我們只 利用計算機科學家描述 的性能，或在運行時間， 的算法。 這樣我們就可以比較算法 寫上不同的計算機 由不同的人，通過使用 一些基本相似度量 喜歡比較的次數你 製作，或者互換的數量 你正在做的。 我們不是要 計數的時間量 傳遞上的時鐘 牆壁上的典型。 我們不是要擔心 大約是多少內存 您使用的是今天 至少，儘管這 另一種資源，我們可以衡量的。 我們要盡量立足分析 上只是基本操作，那些， 坦率地說，你可以看到最直觀。 因此，與類似的n大O 平方，我要求是n的平方Ò 是一個上限，所謂 運行冒泡排序的時間。 換句話說，如果 希望聲稱有 上多少這個上限 幾步之遙的算法可能需要， 這將是n的大O 平方在這種情況下，一個上限。 如果我不是改變 故事是不是冒泡排序， 但這個上限。 你能想到的算法 我們已經看過了已經 其上限，最大 測量的時間或操作 將所述有界 用n，一個線性函數， 沒有二次一個是彎曲？ 什麼是算法 始終把沒有更多的 不是像n步，或 2n個步驟，或3N步驟？ 是嗎？ 聽眾：尋找 列表中的最大號碼是多少？ 音箱：完美，找到 在列表中的最大數。 如果我給出的名單 人，例如， 各是誰在持有一個號碼， 什麼是最大數 步驟應該帶我， 一個相當聰明的人， 找到最大的人在該列表中？ N，對不對？ 由於在最壞的情況下，當 也許最大的價值是什麼？ 右，一路在末端。 所以在最壞的情況下 上界，我可能 要一路走下去 在這裡是這樣， 哦，這裡的數字8， 或任何該值。 現在，這純粹是愚蠢的 如果我堅持下來了，對不對？ 尋找更多的元素 如果最後他們是在那裡？ 因此可以肯定，n是一個上限。 我不需要拿 比更多的步驟。 那麼，如果不是我提出的 還有在這個世界上的算法， 有一個運行時間的 通過日誌的n大O範圍內，日誌N？ 那裡有我們以前見過嗎？ 是嗎？ 聽眾：在電話簿的問題？ 演講嘉賓：像電話簿的問題。 什麼是如何的量度 太多的時間和多少眼淚吧 帶我找到喜歡的人 邁克·史密斯在電話簿？ 我們要求它是數n和 即使不熟悉，或者是 一點點朦朧什麼 對數或指數為， 只記得為log N 一般是指在過程中 在這種情況下，分割 東西兩半又一次，又一次， 又一次，又一次，使得其 變的越來越小，你這樣做。 因此，日誌正指，當然， 到電話簿例如 在理論的二進制搜索，當我們 有虛擬門電路板上， 或者當肖恩 尋找的東西。 如果他用二進制搜索，日誌N 將上限多少 時間花費。 但是，那些跑在算法 日誌N承擔哪些關鍵的細節？ 該列表進行排序，對不對？ 你的算法是錯誤的，如果 您輸入不排序， 可是你用 像二進制搜索 因為你可能會跳 右以上的元素 沒有意識到這是真的在那裡。 現在什麼可能意味著一，大O？ 這並不意味著你的算法 採用一個和唯一的一個步驟， 它只是意味著它需要一個 步驟恆定數目。 也許是1，也許是 10，也許是1,000 但它是獨立的 問題的大小。 無論多麼大的n是， 一個常數時間算法 始終以相同的步驟號碼。 那麼，什麼可能是一個算法 我們已經討論過，或只是 直觀地說來你 總是在所謂的恆定時間運行？ 是嗎？ 聽眾：兩個數相加。 音箱：兩個數相加， 2加2等於4，完成。 因此，可能的工作，還有什麼？ 如何更真實的世界，是嗎？ 聽眾：尋找 列表中的第一件事情。 演講嘉賓：尋找第一 元素在列表中，確保萬無一失。 實際上我們一直在談論 關於數組已經， 你怎麼在得到 在數組的第一元素， 無論多久 數組是C代碼？ 您只需要使用像支架 零符號，咣當，你在那裡。 事實上陣列，順便說一句， 支持的東西一般稱為 隨機存取，隨機存取 記憶，因為你可以從字面上 跳轉到任何一個地方。 我們可以做到這一點，甚至更簡單 我們可以倒回至零一周 當我們做劃傷。 它沒有多少時間了 要說塊划痕執行？ 就在固定的時間，對不對？ 說些什麼，說 東西，也沒關係 大划痕世界是怎樣的，它總是 要採取相同的時間量 簡單地說一下。 所以這是一定的時間， 但什麼是另一面？ 如果這是上 界，如果我們想要什麼 描述下界 我們的算法的運行時間？ 幾乎是最好的情況 潛在的，如果你願意， 儘管這些條款可以適用於最 的情況下，最壞的情況下，一般情況下，更多的 一般，但我們只關注 上下限比較一般。 什麼是算法，具有 下界n個步驟， 或2N步驟，或3N步驟？ n個步驟的一些因素， 這就是它的下限。 是嗎？ 聽眾：冒泡排序？ 演講嘉賓：冒泡排序需要 你最低限度n步，為什麼呢？ 這是為什麼？ 為什麼會這樣開始來找你 直觀地說，即使它不只是 沒有？ 是嗎？ 聽眾：[聽不清]。 演講嘉賓：沒錯。 在可能的最佳方案 冒泡排序，和大量的算法， 如果我交給你八人 誰是已經排序， 那將是愚蠢的 你的算法， 去來回 不止一次，對不對？ 因為只要你 通過列表步行一次， 你應該明白，哦，我什麼也沒有 掉期，這個列表進行排序，退出。 但是，要定你n步。 反之，什麼又 考慮這個問題的方法是什麼？ 冒泡排序是歐米茄， 這麼說的n，， 因為如果你看一下 少於n個元素，是什麼 是根本問題嗎？ 你不知道，如果它的排序，正確的。 我們人類的威力一目了然八 人是這樣，哦，它的排序， 未帶我n步，但它沒有。 你的眼睛，即使你有種 有願景的一大領域， 你看八素， 你看著八人， 這八個步驟有效。 而只有當我在整個行走 名單我知道，是的，排序。 如果我中途停止思考，所有的 沒錯，這是相當排序到目前為止， 什麼是它沒有排序的機率有多大？ 該機制的算法不會是正確的。 可能會更快，但不正確的。 所以，現在我們有辦法 描述一個下界， 和什麼有關固定時間？ 什麼是算法，該算法具有較低的 綁定在它的一個運行時間？ 1步，2步，10步，但 恆定的，獨立的n， 輸入的大小？ 是的，在後面。 聽眾：printf的？ 演講嘉賓：那是什麼？ 聽眾：printf的？ 演講嘉賓：printf的。 好了，肯定的。 所以它需要一個固定的步數。 我現在應該是now-- 我們正在談論的C代碼 不撓，事 如說，與printf的， 我們應該開始變得謹慎。 因為printf的確實需要 輸入時，它是一個字符串， 和字符串做技術上有長度。 因此，如果我們現在要挑 對你，如果你不介意的話， 在技​​術上，我們可以認為，printf的 確實需要一個可變長度的輸入， 並肯定它可能需要更多的 這漫長的時間來打印字符串， 比這個長。 因此，如果我們考慮一下剛才的 排序和搜索的例子嗎？ 怎麼樣邁克·史密斯在手機 書，或二進制搜索更普遍？ 在最好的情況下，可能會發生什麼？ 我打開電話本和，BAM， 還有麥克·史密斯的電話號碼。 我可以打電話給他的時候了。 進了一步，也許兩個步驟， 但是步驟的恆定數 如果我很幸運。 坦率地說，我們看到了 週一你的同學 在連續得到相當幸運的兩倍。 而這的確是恆 時間在下限 在算法中的問題查找 數50落後結束 門。 現在，順便說一句，如果你發現 這兩個大澳，上界， 和ω，下界， 是在同一個，即 是在相同的配方 括號中，你也可以 說，只是華麗， 這東西是時間值損耗 n或西塔的其他價值。 這只是意味著大當 O和ω-是相同的。 現在怎麼樣選擇排序？ 讓我們用這個新的詞彙。 在選擇排序，什麼是我們 老毛病又犯，又一次，又一次？ 我來回通過 在列表中，尋找誰呢？ 最小數量。 所以，要走多少步，如何 很多比較沒有我 必須作出，以找出誰 在列表中的最小元素是？ Ñ​​減1，對不對？ 因為如果我剛入手一個我 鑑於我開始比較他或她， 那麼他或她，他 還是她，他或她，我 只能對元素 一起Ñ減去1次。 所以，選擇排序同樣需要 Ñ​​減1步的第一次。 多少步它帶我去 找到第二個最小的元素？ Ñ​​減2，因為我是啞巴 如果我一直在看同一人 再次，如果我已經選中了他 或者她，把他們在他們的地方。 和第三步驟中，正 減去3，則n減去4。 我們已經看到這種模式 之前，確實 選擇排序相似 有一個上限 n個平方，如果我們這樣做了的總和。 什麼是它的下限，選擇排序？ 最低限度，有多少時間必須選擇 排序需要，因為我們將它定義在星期一？ 提出了兩個選項。 也許這是N，和以前一樣。 也許這是Ñ平方，因為它 現在作為上限。 聽眾：N的平方。 揚聲器：N的平方。 為什麼呢？ 聽眾：因為你 定義[聽不清]。 演講嘉賓：沒錯。 至少我定義選擇排序 這是非常幼稚的，堅持下去， 找到的最小元素。 又來了，找到的最小元素。 又來了，找到的最小元素。 有沒有排序 在那裡，最優化 也許讓我以後放棄 只是n或使步驟。 所以，事實上，選擇 排序，正歐米茄平方。 那麼插入排序，在這裡我把 我給誰，然後我一屁股坐在了他 或她在正確的地方？ 我接著給第二個人， 一屁股坐在他或她在正確的地方。 然後旁邊的人，屁股 在正確的地方他或她。 注意，這是非常 線性的，可以這麼說。 我是一條直線，我 不會來回， 我從來沒有回頭真的，但 發生了什麼，當我插入了他 或她進入初 因為我們沒有在週一的名單？ 發生了什麼？ 是嗎？ 聽眾：[聽不清]。 演講嘉賓：是的，這 被抓了吧？ 你可能還記得， 你的同學，如果他們 正在作出任何動作 他們的腳，這是一個操作。 所以，如果有三個人在這裡和 新人所屬的方式在​​那邊， 在很長的階段，像這樣的，肯定的是，他 或者她只是去到了最後。 但是，如果我們思考一個 計算機和存儲器陣列， 這些人會 有洗牌了 讓路給那個人。 所以是n減1 shufflings， Ñ​​減2 shufflings，正 零下3 shufflings是正中下懷 發生在我後面，而不是在我面前 像以前一樣，在某種意義上。 現在，作為一個一旁，並作為 你可能已經看到了網上 如果你開始關注著有關 各種各樣的，有這麼多不同的人 在那裡，他們中的一些 比別人做得更好。 事實上，bogosort是 這是一種樂趣來查找。 Bogosort採用一組 數字或說一副撲克牌， 隨機打亂他們， 檢查，如果他們來分類的。 如果不是，它再次。 如果不是，它再次。 如果不是，它再次。 令人難以置信的愚蠢。 事實上，如果你讀 像維基百科的文章， 它的綽號是愚蠢的排序。 它最終會工作， 希望，給予足夠的時間， 但該時間量 可能需要相當長的一段時間。 所以，如果我可以，讓我們速度的東西 從早期的瑪麗·貝絲的例子， 通過具有幾個元素， 但有兩個以上處理器。 兩個人，如果你 不介意加入我。 怎麼樣1在這裡，和 讓我們go--沒有人在那裡？ 沒有人在那裡？ 行。 您與黑 襯衫，是的，下來吧。 好吧，你叫什麼名字？ 聽眾：彼得。 演講嘉賓：那是什麼？ 聽眾：彼得。 演講者：Peter，大衛，很高興認識你。 好吧，我們有彼得在這裡，如果你 想來在桌上在這裡。 而你叫什麼名字？ 聽眾：艾琳娜。 演講嘉賓：艾琳娜。 好了，很高興見到你。 埃琳娜滿足彼得。 彼得，埃琳娜。 而我們需要安德魯 在這裡為好，請。 和你的挑戰是怎麼回事 要以一副撲克牌排序。 如果不熟悉，甲板 卡最終應 排序有點像 這其中，我們會做的俱樂部，然後 黑桃，則心和 鑽石，從王牌為一體， 一路到王。 該卡我打算給你 將要在數量52。 我們將同樣 一次，在短短的一瞬間。 我們要扔掉安德魯 在屏幕上的位置， 這樣看，你這樣做。 和使所有的這 是更明顯的， 這些都是我上亞馬遜的卡。 因此，他們已經隨機 排序，我們要一次。 而我們要 保持它真正的這個時候， 所以我們要盡量壓你 否則這將讓乏味的 快。 如果你能進入52排序 通過一些手段在一起的元素，現在。 再次，當我們觀看這些 你們做什麼，到底 會產生一個明顯的 結果，想想真 他們是如何各盡其， 您可能如何描述它。 因為再次，這些都是 所有過程，算法 我們想當然地作為一個人。 但是，你可能早就有了 直覺，很久以前，你甚至 想過走 計算機科學類，你 可能曾與直覺 要解決這樣的問題。 但是，一旦你認識到 模式，並開始 形式化與步驟 您正在解決這些問題， 你會發現，你能解決多少 更有趣和更複雜 問題很快。 因此，有人從觀眾，什麼是 該算法中的至少一種元素 他們使用的是在這裡嗎？ 聽眾：[聽不清] 演講嘉賓：那是什麼？ 聽眾：通過訴訟。 演講嘉賓：通過訴訟。 因此，首先他們是聚類 所有的鑽石一起 看來，所有的 心在一起看來， 等等，不尊重 對於卡上的號碼。 現在，他們的出現，例如， 通過數量來對它們進行排序。 挺好。 好吧，那麼什麼會 是最後一步，然後在這裡？ 一旦我們有四個排序的西服，有什麼 做我們需要做的四樁 為了實現一 整理平台，很簡單？ 因此，我們需要再次合併。 所以這是一個有趣的想法， 再次，敢說，是非常直觀的，甚至 如果你可能從來沒有掌摑 那樣就可以了標籤。 除以這個根本概念 問題不是在一半此時， 但至少到四件。 解決相當多 從根本上相同的問題 在彼此隔離， 然後合併的結果。 而且，優，做。 好了，又大又圓 掌聲中，如果我們能。 [掌聲] 演講嘉賓：我不知道你會 做到這些，但在這裡你去。 太謝謝你了。 因此，讓我們來看看兩分鐘 八秒， 如果你想挑戰你的朋友。 什麼然後將要 從這樣的帶走 我們可以利用更普遍？ 好了，回想起 這個數字陣列， 現在回想起一些 偽代碼，我們已經寫在過去， 這是偽代碼 解決電話簿問題。 由此偽í 列舉一個更有條理的方式 描述我是如何做到一個非常直觀的 將所述電話的人的算法 本書的一半，重複，重複，重複， 直到我發現有人像邁克·史密斯， 如果他確實是在電話簿。 但是我種用什麼，我會打電話 很迭代的方法在這裡， 特別通告第8行和第11行。 這些都是一個迭代的證據 方法，一個循環的方法， 因為這正是 在他們的行為引起。 這些線路都表示去 三線，你可以種 想在你的 心靈之眼作為一個循環。 它告訴你去備份步驟 3，重複，一遍，又一遍， 又一遍。 但是，如果我們利用的一個關鍵思想 在這裡，我們沒有最後一次， 並簡化線路8 第11行和他們的鄰居 像剛才這樣，為黃色。 它不能從根本上縮短 偽代碼非常多， 但它從根本上改變 我的算法的性質。 就是我現在說 在步驟7中，在步驟10中， 是尋找邁克 以完全相同的方式， 但只在左 一半或右半部。 因此，換句話說，如果 我是從第一步開始， 拿起電話本，開到中間 電話本，看名字， 如果史密斯是其中 名字的，叫邁克，否則 如果史密斯早在本書中，第七步 在本書的左半尋找邁克。 但是那種感覺像 它讓我掛了吧？ 在黃色的，是一種 指令，但我怎麼 搜索麥克左 一半的電話簿嗎？ 哪裡有 算法與我 可以搜索一個像邁克·史密斯？ 那麼，它的盯著我們的臉。 我可以從字面上使用完全相同的 計劃有效地往上走頂端 一而再，再運行 同一行的代碼。 因此，即使本應該感到 像一個有點週期性的定義 在那裡你回答別人的 僅通過排序問問題 再次同樣的問題， 就像為什麼，為什麼，為什麼？ 現實的情況是，因為我們已經硬編碼 一組特殊的線，第4步， 其是，如果和步驟12，該 實際上是另外​​一個分支， 因為我們有這些治標不治本， 該算法將終止，如果我們 找到邁克，或者如果我們不這樣做。 但現在STEP 7和10，我們有 我們就這麼叫遞歸算法。 和遞歸確實是一個強大的理念 這是一個有點頭腦的第一個彎， 我們現在可以應用如下。 歸併排序將是最後的那種 我們看一下，至少在形式上類。 而且它是完全不同的 從這些過去三年，肯定 過去四年，如果我們有bogosort。 下面是偽代碼合併排序。 當n個元素的輸入，因此給予 大小為n的陣列中，如果n小於2， 返回。 那麼，為什麼我有 理智首先檢查？ 有什麼含義，如果我交給你 一個數組，其長度n小於2？ 它已經排序，很明顯，對吧？ 因為列表中任一具有 一種元素，它是平凡 排序的，因為它是 唯一存在。 或者說，它的大小為零，這意味著中 有天生什麼來排序，所以 它的排序。 只是有沒有什麼不對勁的地方。 這就是我們所謂的基本情況。 這是精神相似 以我們與麥克一樣。 如果小李的電話本，打電話給他。 如果他不在那裡，就放棄。 這是一個所謂的基本情況，以確保 這個算法在一天結束時 將停止在某些情況下。 但這裡的信仰的飛躍，現在，否則， 排序的元素的左半邊， 然後進行排序的權利 一半的元素， 然後合併排序的一半。 而這裡也正是感覺 像我們科平了。 我問你排序 n個元素，而我 他說，好了，不要它通過排序 左和排序的權利。 但我嘴上說 其他的東西，這 是看來關鍵主題 在直覺到目前為止， 有合併的這個第三步驟。 其中，即使它 似乎在精神上如此愚蠢， 就像剛合併的東西 在一起，似乎 為朝著一個關鍵步驟 兩個問題，即重組 一半最終被劃分。 所以，歸併排序，讓我們做到這一點，如果你願意 幽默的我，多了一個示範， 只是讓我們有一些 數字與合作。 我可以換8壓力 球八個人？ 好吧，你怎麼樣3，你們四個 在本節中，五，六，讓我們 做7，8，上來吧。 好吧，是的確定。 減去8，我們走了，再加上1。 優秀的。 沒事上來吧，讓我們 趕緊給你的數字。 排名第二，第三位，排名第四， 第五，六，七，八名。 我沒有做過8這個時候。 好了，如果你可以去進取， 讓我們梳理了原來的順序 我們昨天看了這 這樣，如果你​​不介意的話。 讓我們做吧的桌子前。 好吧，那麼歸併排序。 這是到哪裡去 獲得有趣的一種， 因為我似乎給自己 這麼多的信息較少今天。 所以歸併排序首先 對n個元素的輸入， 這顯然不是少了兩個比，它的 8，讓我有更多的工作要做。 所以，現在我們精神上的類 現在在else分支， 這意味著三個步驟。 首先，我要排序 元件的左半部。 那麼，如何去這樣做？ 好吧，我要種 精神上將列表在這裡， 您不必 身體動了，我 打算只把重點放在 這裡的元素的左半邊。 那麼，如何去整理 現在大小4名單？ 什麼是我的算法？ 首先我檢查為n比少了兩個，不， 所以我繼續在else塊了。 排序左前衛的元素。 所以，現在再次，精神， 而這正是 你必須累積了大量的 精神的歷史，如果你願意。 現在我左邊的分類 一半的左半部。 好了，所以現在我把我相同的合併 排序算法，是n小於2？ 不，它是兩個，所以我要排序 左半邊和右一半。 所以在這裡，我們走了，排序的左半部。 為什麼不乾脆 走了一步。 你叫什麼名字？ 聽眾：達倫。 音箱：丹。 丹上前。 聽眾：達倫。 演講嘉賓：達倫，完成。 你說達倫還是丹？ 聽眾：達倫。 演講嘉賓：達倫。 好吧，達倫已加強 向前和他現在排序。 這幾乎是一個 空洞的說法，對嗎？ 我豈不真的似乎要實現 任何事情，但是讓我們繼續。 現在讓我排序的權利 一半的元素。 你叫什麼名字？ 聽眾：盧克。 演講嘉賓：盧克。 來吧，向前一步。 完成後，我已經整理盧克。 左半現在排序和 右半現在排序， 但同樣的，這裡有一個關鍵的步驟。 什麼才是我旁邊需要做什麼？ 合併排序的一半。 現在我們只是有 大家來回這種方式， 因為那種我需要的 一些暫存空間。 這幾乎就像這些 傢伙都在桌子上， 我需要一些空間 移動至周圍。 所以，我要合併 你們看 在左半側和右半側。 又是誰顯然是第一位的， 左半或右半？ 所以，正確的上半年，讓我們在移動路 這裡達倫的原始位置。 現在合併他們的左半部分， 達倫是怎麼回事向右移動那裡。 所以感覺差不多 冒泡排序的效果， 但我的基本算法， 非常不同，這一次。 但現在也正是事情變得 有點討厭，因為你 要倒帶精神 在哪裡我離開了。 我剛剛合併排序的一半， 這意味著我在我的算法是在哪裡呢？ 我的右半邊進行排序，對不對？ 如果你後退，從字面上 在視頻中，您將 看到我們到了這 點盧克和達倫的 由左排序 一半的左半部。 然後，我們的合併 排序一半，這 裝置的下一步驟是分類的 左半部右半部。 好吧，讓我們 更迅速地做到這一點。 好吧，六，我會要求 現在你的排序，加油前進。 你叫什麼名字？ 聽眾：阿德里亞諾。 演講嘉賓：阿德里亞諾。 阿德里亞諾現在排序。 而你叫什麼名字？ 聽眾：亞歷克斯。 演講嘉賓：亞歷克斯現在排序。 左前衛，右前衛， 什麼是最後一步？ 合併。 很瑣碎，所以我 要在六個月合併， 退一步， 8，退一步。 現在發現這是 一個有用的外賣，有什麼 現在真正對的左半 列表中，不管我們怎麼開始的？ 它的排序。 現在，它不是在整理 物聯網的大計劃， 但它是獨立地排序 的另一半。 現在哪一步我是在如果我堅持 複捲怎麼回事開始？ 現在我要右半排序。 所以，現在我們回來的路上，在 故事的開始， 並讓我們這樣做更為迅速。 所以，我要排序 整個列表的右半邊。 什麼是下一步？ 排序的右半​​邊的左一半。 排序的左半 右半部分的左半部。 而你叫什麼名字？ 聽眾：奧馬爾。 演講嘉賓：奧馬爾，向前一步，完成。 左半部分是排序。 而你叫什麼名字？ 聽眾：克里斯。 演講嘉賓：克里斯，退一步 未來，你現在來分類的。 什麼是現在的關鍵一步？ 合併。 所以，一個人要融入地方 在這裡，如果你能退後一步， 三是要 退一步，合併。 這樣的左半 右半部，現已排序。 坦率地說，這個算法感覺就像我們 這是在浪費這樣的時間比以前， 但如果我們在實時這樣做，我們將 看到外賣成為怎樣的人。 現在我在這裡，對不對 一半的右邊一半的， 讓我繼續前進，排序的左半部。 向前邁出一步，你叫什麼名字？ 聽眾：拉姆齊。 演講嘉賓：拉姆齊現在排序。 你叫什麼名字？ 聽眾：碼頭。 演講嘉賓：濱海現在排序， 好吧，如果你走了一步。 這裡關鍵的一步，現在被合併，我 打算從我的兩個列表採摘， 左，右。 五是要放在第一位， 七是要到明年。 再次，這是故意的。 他們正在做的事實 步驟前進和後退 是代表我們不能 這樣做算法的地方，很容易 如冒泡排序和選擇排序， 和插入排序，我們只是 不停交換的人。 我真的需要一個排序 草稿紙在其中 把這些人 而我的融合， 然後我可以把它們放回原處。 這就是關鍵，因為我使用的是 新的資源，空間，而不僅僅是時間。 OK，這是驚人的。 左半部分是排序，右半部分是 排序的，現在的關鍵合成步驟。 我怎麼合併呢？ 所以，如果你按照我 左手和右手 我要指出我的左手 在左前衛，我的右手 在右前衛的，現在我要 決定一步步誰在合併。 誰顯然是第一位的？ 第一。 所以來這邊， 這裡是我們的便箋。 所以，現在排名第一，並通知 我會盡我的右手， 我打算將我的右手1 跳過來點排名第三， 現在我要 同樣的決定。 而實際上站在正確的 盧克在這裡，如果你能面前， 因為這是我們的便箋。 那麼，誰隨之而來的？ 我們有盧克與排名第二 或者克里斯與排名第三。 顯然盧克，數 2，讓你來這裡。 但是，我的左手現在是要 遞增為指向達倫， 而這裡的關鍵拿走了 合併，我將繼續這樣做， 很明顯，如果你有種 遵循的邏輯。 但我的手都從未 要往回走， 這意味著我永遠只能移動到 左邊有我的合併過程， 那將是關鍵 我們的分析在短短的一瞬間。 所以，現在讓我們迅速完成這件事。 所以三隨之而來的， 然後4隨之而來的， 現在5隨之而來的，則6， 七，最後8。 感覺就像是最慢的算法 然而，但如果我們真的 在相同的排序運行 時鐘速度的，所以要 說，具有相同的 滴答作響的時鐘和以前一樣。 為什麼呢？ 好吧，讓我們來 看的最終結果。 讓我們回到了這裡，讓我 拉了一個直觀演示 什麼，我們只是做了。 放大在這裡，在這個 在此頁面，告訴火狐 我們要排隊 在此框，讓我們 說冒泡排序，與 我們現在非常熟悉， 選擇排序，這是另一種 相當簡單的， 現在今天的歸併排序，其中 將是我們的高潮結局。 花了這麼多時間越長的原因 這裡有人類和我口頭上的， 很明顯，我解釋每一步。 但如果你只需要執行這一點，很多 像我們做冒泡排序和選擇 排序不僅在視覺上，觀看 到底有多少更有效 這個槓桿化 分裂和征服 可以在應用到數據集的 即使沒有大小八，但即使多了， 要大得多。 我給你通過歸併排序，方 方用這些算法。 這是會得到痛苦 很快，並且結束 沒有特別的高潮， 他們剛剛結束了排序。 但關鍵帶走的是 看快多少排序合併 是的，除非你覺得我 只是那種玩弄你。 如果我們這樣做了，最後一次， 讓我們重新加載此，讓我們回去 選擇冒泡排序， 而只是踢， 讓我們來選擇插入 排序，只是為了好措施。 而這一次又一次，讓我們 選擇合併排序，讓我們 實際上並排運行這些側。 它不是，其實是僥倖。 我已經做了有效的是我 分我輸入了一半，同樣， 又一次，又一次。 而且也只有這麼多的時候，你可以 將您的輸入成兩半，左 右。 那是什麼，我們總是看到公式 描述該師在半 一次，又一次，又一次，又一次？ 聽眾：日誌N。 演講嘉賓：日誌N。 但還有另一個關鍵的一步， 這種算法是不記錄n步。 如果它僅記錄n步， 我們將在同樣的問題 如之前在這裡我們不能 確保一切的排序。 你必須微創看看n個元素 可以肯定的n個元素進行排序， 否則就是信仰的飛躍。 所以它的最低限度日誌n步，但 那麼這個合併的關鍵一步 在這裡我合併了我的左半邊，右 半走過的階段？ 多少個步驟是合併？ 這是N，但我不只是 合併的最後時間。 在每個這些嵌套調用，每個 這些嵌套的合併，我還是整理。 我將這這兩個傢伙，那麼這兩個 男人，那麼這兩個傢伙，等等。 所以，我沒有再合併，再。 多少次？ 所以每次我分了 列表中的一半，我做了合併。 將列表中的一半，做了合併。 因此，如果分割清單 可以做日誌的n倍， 和合併，最終佔據N 步驟，可能是什麼，現在的上 結合在跑步 我們的算法的時間呢？ Ñ​​日誌N。 事實上，這就是 我們在這裡實現。 所以，你看到的時候視覺上的感覺 這三樣東西並行走線 為n的平方與n的 平方與n的日誌ñ。 這從根本上，我們會看到， 不僅是現在，而且在將來， 是非常非常快。 掌聲鼓勵了這些傢伙， 我會獎勵他們壓力球。 讓我們今天在這裡宣布休會，並 我們會看到你在星期一。