>> [音樂播放]
>> DAVID J.馬蘭所有權利。
因此，歡迎回來。
這是CS50，和 本週三結束。
>> 所以，記得在過去的幾個星期中， 我們已經花了相當多的
C，對編程，語法的時間。
這是相當正常的，如果你還在 掙扎與習題集2，
撞你的頭靠在牆上。
這是神秘的前瞻性的錯誤消息 和錯誤，你
不太能追下去。
因為，放心好了，在短短 幾個星期的時間，你會回頭看
凱撒之類的東西，[？ V-genair？] 甚至裂紋，
實現你來多遠 在很短的一段時間。
因此，如果這是任何安慰， 現在掛在那裡。
>> 今天，雖然我們開始轉型 的東西更高的水平。
我們開始想當然 你們知道如何編程，或者
至少開始 ，舒適的水平。
我們將開始考慮我們如何能夠 設計方案更多
有效。
我們如何去優化 我們的算法的效率，並
一般解決更多 有趣的問題。
並開始想當然地認為， 如果我們想，我們可以編寫任何
我們心目中的例子。
因此，我們今天不要觸摸鍵盤 任何形式的代碼。
這將是更高的水平， 最終的問題解決。
>> 所以到這一點，讓我提出 ，下列7項
矩形代表七個門，後面 這是一個一大堆
號，其中數字50。
讓我在此項目 屏幕在這裡。
並提出，我們需要一個志願者 幫我找一個前面的數字
看到這裡的互聯網。
上來吧，在粉紅色的。
好的。
你叫什麼名字？
>> 詹妮弗：[聽不清]
>> 國寶，J. MALAN：對不起？
>> 詹妮弗：詹妮弗。
>> DAVID J.馬蘭：珍妮弗。
所有權利，珍妮弗。
認識你很高興。
上來吧。
因此，這些這裡有7個門，什麼 我希望你能在這裡為我們做的，
在所有的同學面前， 找到我們的號碼，50。
要找到一個號碼，你可以窺見背後 這些門通過簡單輕敲
一個門，它 將揭示其編號。
，讓我們看看你的速度有多快 可以找到我們的號碼，50。
>> 15。
16。
50。
幹得漂亮。
好的。
圓形，珍妮弗的掌聲。
>> [掌聲]
>> 好的。
那麼，什麼是你的策略 找到的數目，50？
>> 詹妮弗：嗯，我想，也許 -
[聽不清]
>> DAVID J.馬蘭：哦。
給它一秒鐘。
所以，你的戰略 找到的數目，50？
>> 珍妮花：所以我剛開始在 開始看到的第一個數字
，然後我想，也許，如果 他們排序，我就繼續
攻高了？
>> DAVID J.馬蘭：“確定”。
我們似乎已經找到 的情況下。
雖然，讓我們剝開層層 只是一點點，你想要去的
提前透露其他門 你也可以選擇嗎？
>> 詹妮弗：哦，親愛的。
>> DAVID J.馬蘭：啊。
>> 珍妮花：所以我只是很幸運。
>> DAVID J.馬蘭：所以你很幸運。
好的。
所以不壞。
但是，這是一個有趣 洞察力，對不對？
如果你認為，你沒有得到， 著實有點幸運有。
但是如果你假定數字 排序，你可以更精確
如何影響 你的行為？
>> 珍妮花：所以，如果他們進行排序，我 想，也許從最小到最大。
>> DAVID J.馬蘭：“確定”。
>> 詹妮弗：或者，如果這結束了 真大，然後從最大到最小。
>> DAVID J.馬蘭：“確定”。
所以從最大到最小，或者 從最小到最大。
但是，讓我提出，假設您有 倒霉了，以為他們
不，實際上，分類，有多少 這些門可能你有偷看
落後，最壞的情況下？
>> 珍妮花：他們所有。
>> DAVID J.馬蘭：他們所有。
因此，讓我們概括為n。
恰好是7，但是讓我們更 一般說有Ñ門
這裡的屏幕。
因此，在最壞的情況下，你將不得不 看7門，或n門背後。
所以這真的是，這是一個有點 今天的運氣，但它是一個真正的線性
各種各樣的算法，即使你 那種跳繩周圍。
這公平嗎？
>> 珍妮花：是啊。
>> DAVID J.馬蘭：嗯，讓我看看你的 策略的改變，如果我感動我們
這裡我們的第二個例子 7種不同的門。
相同的數字，但是這 時間進行排序。
什麼是你的戰略將是， 試圖把你的頭腦是什麼
其他的數字是 -
>> 詹妮弗：OK。
>> DAVID J.馬蘭： - ？
>> 珍妮花：讓我們開始 與第一個。
>> DAVID J.馬蘭所有權利。
開始的第一個。
4。
現在，在那裡你會去，為什麼呢？
>> 珍妮花：4是真的小。
所以，如果他們是那種也許最小 最大的，它應該
的兩倍，以及 - 。
>> DAVID J.馬蘭：“確定”。
讓我們來看看，你覺得呢？
>> 詹妮弗：最後一個嘗試。
尼斯。
>> DAVID J.馬蘭：非常好做。
好的。
>> [掌聲]
>> DAVID J.馬蘭：“確定”。
所以其實你這樣做 可怕的，因為你
這樣做很好。
使我們無法 使某些要點。
因此，讓我們在這裡嘗試回滾。
>> 詹妮弗：OK。
>> DAVID J.馬蘭：很好 做了，儘管如此。
所以，你開始之初， 你看到，這是4，那麼你
移到末尾。
但是，假設你沒有得到幸運 在那裡，假設50
別處。
你的第三步怎麼辦？
>> 詹妮弗：返回到開頭。
>> DAVID J.馬蘭：返回 到開頭。
好了，你會一直感動 這門，這是8。
好的。
所以，這不是50個。
你會在哪裡看過？
>> 詹妮弗：如果我沒有 知道他們排序。
>> DAVID J.馬蘭：正確。
好吧，如果你不知道 他們進行了排序 -
>> 詹妮弗：哦，知道，是啊。
>> DAVID J.馬蘭 - 但你沒有 知道其中50還在嗎？
>> 珍妮花：只要堅持下去。
>> DAVID J.馬蘭所有權利。
確定。
繼續下去。
OK，我可以工作。
>> 詹妮弗：OK。
>> DAVID J.馬蘭：現在，如果你只是 要繼續下去，你叫什麼
算法下放備份成。
>> JENNIFER：線性 - 。
>> DAVID J.馬蘭：這是一種線性的。
但是，讓我提議，讓我們 我把在現場。
讓我刷新頁面。
同樣的號碼，同樣的安排， 同門。
但回想起在第一天 上課的時候，我們撕了電話簿
一半，排序，是什麼 我們的策略嗎？
>> 詹妮弗：開始在中間。
>> DAVID J.馬蘭：“確定”。
因此，開始在中間。
所以，讓我們繼續前進，和模擬。
開始在中間 露出那扇門。
因此，數字16。
所以，你會強烈的傢伙都做了， 誰撕了一半，電話簿
去下一個猜測？
>> 詹妮弗：這半場。
>> DAVID J.馬蘭：為什麼了吧？
>> 詹妮弗：如果他們最小 到最大，然後50
為此。
>> DAVID J.馬蘭：好。
完全合理的。
所以像電話簿，你去 的權利，而不是左側，但在這裡
關鍵是外賣。
您現在可以扔掉，或撕下， 這個問題的一半，讓你不
7門，但實際上僅有3。
這是大約一半的 大小的問題。
好的。
所以，現在你將有什麼 完成後，你向右走？
>> 珍妮花：所以16還是蠻小的， 相對於50，也許我會嘗試，
像這一個。
>> DAVID J.馬蘭所有權利。
42。
所有的權利，所以現在你叫什麼 本能告訴你嗎？
>> 珍妮花：我可以扔掉 這一點，然後只是 -
>> DAVID J.馬蘭：“確定”。
好，你可以扔掉 的左半。
>> 詹妮弗： - ，拿起這一個。
>> DAVID J.馬蘭的權利。
>> 珍妮花：是啊。
>> DAVID J.馬蘭：所以，即使它很難 或許看到，當有只
7門，想想現在， 的一致性
你只是算法應用。
在以前的情況下，你做 得到幸運的，這是偉大的。
但你沒有使用啟發式， 我想說的。
您使用自己的直覺， 知道它的排序，如果它是相當
小的開始，很明顯，我們已經 去了更多的權利。
但是，從某種意義上說，你很幸運， 因為也許這是100號，
也許50是在中間。
也許50即使在這裡。
>> 但你做了什麼一點點不同 這個時候，你做同樣的事情
一遍又一遍。
我認為，你剛才 沒有，但通過手機影響
書中的例子，多是 算法，多
特別少套管。
更本能。
因此，在一天結束的時候，怎麼會 你描述的效率
第一種算法，你在哪裡 左到右，相對於
第二種算法在這裡？
>> 珍妮花：這個應該，喜歡，也許 時間減半，甚至更多，是的。
>> DAVID J.馬蘭：好吧，也許甚至更多。
讓我們一點點推更難。
真的，如果我們繼續 邏輯，我們肯定減半
本次算法的運行時間 扔掉一半的
數字，但沒有什麼我們做下 迭代，當詹妮弗透露
第二個數字？
>> 門再次減半。
然後我們做了什麼，如果 有更多的門一起玩嗎？
我們將減半，並再次， 一遍，又一遍。
這就像你們 站在上面的第一週
類，你坐下的一半，一半 你坐下，你的一半
坐了下來，直到一人獨行 站在靈魂。
我們說的運行時間 的是，它採取的步數
順序是怎樣的？
>> 揚聲器1：[聽不清]
>> DAVID J.馬蘭：所以底數2的n， 或只是更簡單，登錄的n。
因此，對數的東西。
和圖形是不在一條直線上 只是越來越糟，這是
沒有這個有趣的曲線 隨著時間的推移變得如此糟糕。
因此，讓我們保持這種想法。
讓我們感謝珍妮弗。
感謝這麼多的最多。
一秒鐘。
沒有檯燈，但我們 確實有CS50應力球。
>> 詹妮弗：耶。
>> DAVID J.馬蘭：好的，在這裡。
謝謝你承擔 應力在這裡。
好的。
所以，讓我們來看看，如果我們現在不能 正式這一點。
所以，再一次，我們剛剛做的是 基本上我們做同樣的事情
在第一個星期。
但而不是結束，只是一個線性 算法，這是我們描繪
以前這條直線， 據此，如果我們把一個門
屏幕上，然後珍妮弗會 不得不看，可能，
後面多了一個門。
如果我們把兩個門，她可能有 看看後面兩個門。
>> ，所以這種線性 的大小之間的關係
問題，比方說，在x軸，和 它需要的時間量
解決在y。
但畫面我被影射 早期是這樣的綠線。
綠色故意的，因為 它只是感覺好多了。
在理論上，算法，當我們做到了 電話簿，當我們做到了
你們計數對方， 在第二種情況下，當珍妮弗只是
做了它在這裡，它是 從根本上更好。
因為它不只是快兩倍。
它甚至不是快四倍。
這完全依賴於什麼 輸入的大小，到底有多少
最終步驟了。
>> 所以這個簡單的想法，我們都拿了 為電話簿授予，
可以類似地應用 這樣的東西。
這可能是更隨便 被稱為，因為您可能
可以想像，分而治之。
當然，沒有什麼不同，我們做了什麼， 電話簿。
>> 但偽代碼，召回，是這樣的。
因此，我們不會做這個了，但記得 第一個星期，我們都站了起來
然後你的一半坐了下來，一半 你坐下，你的一半坐了下來。
該算法在一個實施 有點作弊的方式，在那，
不只是我一個人計數， 從根本上說，更有效地。
在這種情況下，我被利用 二次資源。
排序的，多個CPU，多動腦筋， 多聰明的人
房間幫助我得到的東西 線性的東西
對數，從東西 紅色到綠色的東西。
>> 但是，在這種情況下，珍妮弗單靠 從根本上改善後
她的第一個算法的性能， 再次，只是想有點困難。
而現在，當談到時間來實現 這些東西，搞清楚
什麼行代碼，你能寫出這樣 ，你可以重複一遍，
一遍，又一遍，排序 在循環的方式。
因為你不會有 做的第一件奢侈品，像珍妮弗，
如果只是有一大堆，說 嗯，如果這第一個數字是4，
讓我跳方式結束。
哦，如果這個數字太大了， 讓我回到隨意移動
到第二元件。
你會發現，它將會是一個很大 難以形式化我們人類
想當然是非常合理的 啟發式方法，但只有一台計算機是
會做你告訴它做。
>> 現在，這具有非常有趣 的影響。
此圖意味著排序排序 壓倒視覺，但是請注意，在那裡
在該曲線圖中的直線是什麼？
哪裡是線性圖 我們稱之為ň？
嗯，這是那種朝下方 這幅畫，是吧？
因此，我們所做的是我們排序 地圖的x軸和
y軸設法得到一個什麼樣的感覺 其他類型的曲線的樣子。
>> 和具體的數學 今天的表達式將不那麼重要
不多，但發現有很多 算法遠不如
東西是線性的。
事實上，N立方看起來很糟糕。
2 n個看起來很糟糕。 Ñ​​平方看起來很糟糕。
，我們將看到一些人 可能會在今天的現實。
日誌N不那麼糟糕的感覺，但 比n底數2的n。
但你知道，它會更 更驚人的，如果詹妮弗，或者如果我們
第一個星期，想出了 東西是n的日誌記錄。
>> 因此，換句話說，這整個 可能的解決方案的範圍
問題，但即使在這裡，請注意 會發生什麼。
當我縮小，這些曲線 會被證明是絕對
現在屏幕上的最差？
因此n的立方小艾 糟糕的時刻。
但是，如果我們放大，看到更多的 x和y軸，誰去
最終主宰？
因此，它實際上原來，2 n，並且可以算出這個只是通過
堵在一些越來越大 數字，你會看到2到
N，事實上，獲取更大的快得多。
如果我們真的縮小，2 絕對吸Ń算法。
我的意思是要採取 相當多的時間
電腦上翻騰通過。
>> 但是，你會看到隨著時間的推移，特別是 甚至與未來問題集
最後的項目，為您的數據 集變大了，好嗎？
即使是在Facebook的第一個版本， 作為朋友，
註冊用戶的數量得到了大， 您可以排序的電話呢
執行線性搜索的東西， 還是一個很簡單的排序
算法，今天我們會看到。
你必須開始思考更難 這些問題更難。
和類型的問題的地方，如 Facebook和谷歌，微軟，
和其他工作，正是這些 大數據排序排序問題
這些天越來越多。
>> 好的。
，所以詹妮弗的成功，第二 算法，坦率地說，她的確令人驚訝
以及第一次，但我們 寫我的運氣，讓我們
可這一點。
在第二種情況下，她利用 算法，又重複了一遍，
再次，但她認為理所當然的一 我們允許若干假設
她，但她利用一些細節 第二，她沒有足夠的時間
第一次。
這是什麼？
>> 列表排序。
所以只要列表排序，我們 聲稱，珍妮弗是能夠做到的
從根本上更好。
7門，是的，是不是很有趣， 但假設我們700萬門。
n的日誌是一定要去 執行很多，很多
從長遠來看快。
但她必須有 她門的排序。
現在，我帶著這樣做的自由 事先在電腦屏幕上
在這裡，但假設珍妮弗 不得不做自己？
假設門問題 表示數據庫中的數據，或
為Facebook註冊的朋友，或 任何在互聯網上的網頁
可能需要不同的網站 索引或搜索過。
>> 假設你剛剛有了原始數據 設置和它留給你的，或
珍妮弗做排序？
，而是需要我們回答 的問題，好了，多少時間
珍妮弗，甚至我會採取 這些數字進行排序，提前讓
她能利用？
對嗎？
因為言下之意，當然是 如果它需要我相當長的一段時間排序
數字，到底誰在乎你 這麼快可以找到一個像50，
作為在詹妮弗的情況下，如果我們多 不堪重負的總時間量
了通過分揀事前事中？
>> 因此，讓我們來看看，如果我們不能 這裡繪製圖片。
我有一大堆的壓力 球，如果有幫助
打破這兒的冰。
如果你不介意，我們 需要七個志願者 -
，“確定”。
哇。
因此，我們不必花 檯燈，它似乎。
好的。
因此，如何對你們兩個在前面。
怎麼你們倆在後面。
所以這是四個。
你怎麼樣在前面 五，六，七。
就在那裡。
您的朋友的指點你， 所以你得到的獎品。
>> 好的。
上來吧。
為什麼不，我們有你 你們來就在這裡。
我去給你們每人一個。
繼續前進，安排自己 相同的是什麼
在屏幕上描繪。
>> [插入聲音]
>> DAVID J.馬蘭：OOP，對不起。
問題。
好的。
那麼，在這裡，我們去。
5號。
6號。
一，二，三，四， 五，六，七。
哦，這是很尷尬。
>> 揚聲器2：我剛剛得到一個 - 。
>> DAVID J.馬蘭：處理好。
好的。
謝謝您的參與。
>> [掌聲]
>> 確定。
好的。
因此，我們有四，二，六， 一，三，七，五。
完美的，所以我們有七個志願者 在這裡誰是寬度相等的
我們玩的數組 與早期的。
我選擇了七個原因 這將是剛
方便一點點。
我要首先提出， 我們梳理這七名志願者。
如果你想，首先， 打招呼，雖然。
由於這將是一個 尷尬幾分鐘。
介紹一下自己。
>> GRACE：嗨，我是格雷斯。
我是一個大二在利維瑞特大廈。
>> 布蘭森：你好。
我布蘭森。
我是一個大一的焊接。
>> GABE：你好。
我加布。
我是一個小輩在Cabot。
>> 尼爾：我是尼爾。
我一大一馬修斯。
>> 傑森：我是傑森。
我是一個大一格里諾。
>> MIKE：我是麥克。
我一大一灰色。
>> JESS：我是傑西。
我是一個大二萊弗里特。
>> DAVID J.馬蘭：優秀。
好的。
嗯，謝謝你給我們所有的 這裡的志願者迄今。
現在手頭的挑戰會 是這些傢伙排序，但隨後
我們要覺得有點 我們如何有效地實際上努力
排序。
所以，讓我們先試試這個。
你們可以看到對方的號碼 只是把周圍的角落。
來吧，採取了幾秒鐘， 從最小的排序自己
左到最大的在右邊。
去。
>> 確定。
好。
這真是混賬快。
現在有人在這裡，究竟是什麼算法 這些傢伙的應用呢？
>> 揚聲器1：最偉大的。
>> DAVID J.馬蘭：“確定”。
最小到最大還真有幾分 的目標，但我不知道這是
一個真正的算法。
最小到最大不告訴 我一步一步做什麼。
是嗎？
>> 揚聲器1：[聽不清]
>> DAVID J.馬蘭：“確定”。
所以，如果你看到一個人小於 你的電話號碼，然後移動到
他們的權利。
因此，現在越來越多的表現， 更像是一個算法，因為你
可以說，如果這樣，那麼這個。
因此，我們有某種 條件結構。
這些傢伙似乎做那幾個 次，因為一些你有點感動
的距離。
所以大概是有某種 循環在他們的頭腦中去。
>> 但是，讓我們盡量正規化，。
如果你們能重置回 這種佈置。
讓我們來看看如果我們不能正式確定這是一個 位，然後問這個問題，只是
效率如何？
當然，當我們這樣做時速度比較慢， 它會感覺一樣好
一種算法，但讓我們來看看，如果我們能 把我們的手指的精確步驟。
>> 所以，你們倆有四個和兩個。
或您正確或不正確的順序？
顯然不正確。
所以我們交換。
現在，我要移開 這裡說，四到六。
你是正確的或不正確的？
>> GABE：正確。
>> DAVID J.馬蘭：正確。
六一？
不。
交換。
所以這是兩個互換。
六，三個？
不。
交換。
六，七？
看起來不錯。
7個和5？
>> JESS：[聽不清]
>> DAVID J.馬蘭：OK，交換。
和排序。
好的。
所以，很顯然不是，對不對？
於是有更多的事情。
不過，說實在的是，這些傢伙，即使 只是本能。
不停地移動。
他們不只是停下來，他們一旦 糾正一個問題。
所以。
事實上，我將不得不 做同樣的事情。
我要倒帶回來排序 此問題的​​開始，
或此數組的開始 人，讓我們開始打電話給他們。
>> 現在應該做些什麼算法 在第二遍呢？
>> 揚聲器1：同樣的事情。
>> DAVID J.馬蘭：同樣的事情。
而這一點，我開始喜歡，對不對？
只要你可以找到自己做 同樣的事情一遍又一遍，這是
變得更像一個算法， 人類的本能。
>> 所以，現在，在這裡，我們又來了。
兩個和四個？
號
四之一？
嗯，確實有一些 工作尚待完成。
三？
好。
四和六？
六，五？
六，七？
OK，現在，完成。
OK，沒。
我必須回去。
>> 所以，現在，再次，我們正在做這 有點刻意。
而現在，只是一個大腦 執行該算法。
一個CPU，如果你願意。
坦率地說，這是唯一的資源 我們將有機會獲得。
一旦我們做回一個鍵盤 和我們有一些像C
處置中，我們只寫一個程序 可以做一件事的時間。
然而，這些傢伙剛才，我們 利用他們的集體腦力
像你這樣的傢伙做週零。
所以，讓我們繼續這樣做。
>> 兩個和一個。
二和三。
三和四。
四和五。
五和六。
六，七。
做了什麼？
所以我，但讓我打 魔鬼代言人。
我的電腦誰只是 發了一通通過這個數組
人，知道我做的嗎？
>> 揚聲器1號
>> DAVID J.馬蘭：那麼，為什麼呢？
我會怎麼做，以 果斷地結束，我做？
大概一個多通。
對嗎？
因為我知道從先前 通的是，我糾正了錯誤。
這意味著，也許有 另一個錯誤
我需要糾正。
所以我只能確定經複捲， 然後檢查，一到兩個，兩個
三，三，四，四，五， 五，六，六，七。
OK，我現在沒工作。
>> 我可以肯定記得，我沒 工作像變量一樣的東西，
我喜歡一個int。
叫它掉，如果掉的是有一次我0 在這裡，它從0開始，然後
我也只是愚蠢繼續下去 來回，再次檢查，
一遍，又一遍，對不對？
因為你在一些被卡住 一種無限循環。
所以，只要有0掉期， 我們可以聲稱這
算法確實是完整的。
>> 現在，讓我們把名稱。
我建議我們只是算法 實現東西叫做泡沫
形式的，在這個意義上，作為這種已知 是一種更大的數字
泡自己的方式到頂部，漲幅高達 到的數字數組的末尾。
但這種算法是如何高效？
多少步了我的身體有 例如，採取排序這些
七人？
>> 四，五？
OK，太多的是最終 要得到答案。
但即便如此，具體數量 是不是非常有趣。
設為n概括。
所以，如果我已經N多人在這裡，他們 ，排序，在隨機順序
開始的時候，在那個原來的順序。
嗯，我有多少步 第一遍？
這是一，二，三，四，五， 六，他們七人，所以
七，六 - ，所以這是Ñ 減去一個步驟的第一次。
>> 現在，我有多少步 我倒帶時要採取？
好吧，我們實際上可以增加一倍，如果 我們真的很想，但現在，我
只是會說，所有的權利， 另一個n減1。
那麼N減1是會得到 惱人跟踪，讓我們
只是小幅圍捕。
所以2n個。
因此，14個步驟，給予或採取。
>> 我多少次 一個步下一次？
嗯，這是3N。
真的。
現在，在最壞的情況下，為 例如，我有多少次
來回走了，反反复复， 執行該算法，交換
每個合格的人，大約有嗎？
它實際上是Ñ平方，對不對？
>> 因為在最壞的情況下，可以種 想想這個直觀的，
即使它可能需要一點 位時間的下沉。
在最壞的情況下，會是什麼 七人的模樣，在
協議條款 他們的人數？
完全倒退，對不對？
只是模擬， 你叫什麼名字呢？
>> MIKE：麥克。
>> DAVID J.馬蘭：邁克？
OK，邁克，你只是和我一起過 這裡只是一秒鐘？
事實上，沒有。
對不起邁克，讓我們倒帶。
你叫什麼名字呢？
>> 尼爾：尼爾。
>> DAVID J.馬蘭：尼爾。
OK，尼爾，你來 我，如果你不介意的。
所以我要提出的，只是 簡單起見，尼爾現在是在他
最壞情況下。
但記得我是如何實現 我的算法。
我比較，比較，比較， 比較，比較哦。
現在，這些傢伙都出來了 秩序，所以我修復。
所以你們交換。
但現在，考慮如何更遠 尼爾一定要去嗎？
它大致Ñ。
你知道，這實際上並不ñ。
這就像，N減1，但我得到 惱火跟踪的小
號，所以我們只叫了N。
>> 所以，如果尼爾移動一步最大限度每個 時間，移動尼爾一步，
我必須做出這個非常繁瑣的通 來回，這大概是
這樣，n個步驟，共n次， 因為它是要帶我
許多步驟尼爾所有 他所屬的地方。
更別說其他人，如果你們 都亂序。
>> 所以姑且稱之為的冒泡排序Ñ平方。
這個算法的運行時間， 該算法的性能，
該算法的效率， 我們只是描述
一般為n的平方。
這是很好的，因為我可以做 同樣的例子，八人，九
人，一萬人， 答案是不會改變的。
>> 所以，如果你們不介意，讓我們 重置你開始的地方。
讓我們嘗試其他兩種方法 如果我們不能從根本上做
比這更好的。
所以這個時候，我要建議 一種不同的算法。
這是非常聰明的，我們最後一次， 你們是正確的，有
權利只是一種本能 的交換兩兩。
但是，如果我真的就想辦法 簡單地說，我的目標是移動
這樣的小數字， 推動所有的大號碼
這樣，為什麼不我只是做，在 最天真的可能的方式，看看我
比什麼是可以做的更好 相當複雜的算法？
>> 所以，讓我們來看看。
四是一個非常小的數字，所以我 要離開你有片刻。
哦，2號，甚至更好。
所以，你可以只是一步 一會兒嗎？
這是我目前最小的編號 候選人，我會記住
與一樣，一個變量。
但我會繼續檢查。
是否有某人的 號碼是小？
六，沒有。
哦，還有尼爾再次。
>> 所以我打算推你回來 排序的概念。
尼爾將挺身而出。
而現在，變量，我使用 跟踪誰擁有最小
號碼被更新為包含 尼爾的位置。
好吧，讓我們來看看。
三，七，五。
好吧，我知道尼爾是最小的。
什麼是最簡單的事情 我現在要做的嗎？
只是，我不會浪費我的時間 冒泡尼爾一個點到左邊。
為什麼不讓我在那裡他將尼爾 屬於當然，這是在哪裡？
>> 所有的方式在開始時。
所以，尼爾，跟我來。
你叫什麼名字呢？
>> GRACE：格雷斯。
>> DAVID J.馬蘭：格雷斯。
確定。
所以，雍容，不幸的是，你 樣的方式。
那麼，我們如何解決這個問題？
對嗎？
如果這是一個數組，有 只有七個地點。
回想一下，與Rob，我們談到 聲明年齡，我們只有一個
有限數量的年齡？
同樣的想法在這裡。
我們只有有限數量的整數。
格雷斯是怎麼樣的，在我們的 這樣，那麼我們如何解決呢？
>> 最簡單的方法是什麼樣的， 格雷斯，對不起。
你要去走了過來 所以我們可以騰出空間。
現在，如果你想想，也許 我們只是使問題變得更糟。
也許我們這樣做，因為如果 格雷斯是在正確的地方？
但我們知道，她不是，因為 否則，她會一直
而不是站在 尼爾在這個時候，對不對？
我們已經檢查了她的電話號碼。
>> 好的。
所以，現在，尼爾在正確的地方， 我可以做一個輕微的優化。
在接下來的一分鐘，我要忽略 尼爾都在一起，所以不
浪費他的時間，或意外 他換到錯誤的地方。
所以，現在，我該如何尋找下一個 最小的元素嗎？
二。
這是一個不錯的數字，如果 你要挺身而出，
我會永遠記得你。
六，沒有好。
四，三，七，五，沒有好處。
因此，讓我打動你 你的正確的地方。
而我們只是很幸運這個時候。
>> 現在，我要忽視這些 兩個傢伙，現在更盡一
通過這一點。
六，是一個非常小的數目。
加油前進。
哦，對不起。
Grace的號碼比較好， 所以踩前進。
四。
對不起，格雷斯。
你回去吧。
三是更好的。
七。
五。
現在，你叫什麼名字呢？
>> 傑森：賈森。
>> DAVID J.馬蘭：賈森。
因此，Jason是現在最小的 我的元素。
他要去哪裡去了？
那麼，六是。
你的名字嗎？
>> GABE：加布。
>> DAVID J.馬蘭：加布。
加布的方式。
什麼是最簡單的事情嗎？
交換這兩個傢伙，然後繼續。
所以，現在讓我們來看看。
誰是最小的？
四。
讓我只是一種作弊。
五是將是最小的。
接下來，我覺得，如果你想一步 未來，我有什麼做
這些傢伙，加布？
再交換。
所以，現在，仍有小幅的順序。
我發現加布是最小的，所以 我彈出他，將你們。
並完成。
>> 因此，答案是一樣的。
最終的結果是一樣的。
這兩種算法哪 是更好嗎？
第二個，我聽說了。
為什麼呢？
>> 揚聲器3：n個步驟[聽不清]。
>> DAVID J.馬蘭：這是最多的n個步驟。
有趣。
那麼是什麼關係嗎？
那麼我怎麼找到 最小的元素？
我不得不採取了多少步 找到最小的元素？
我一看所有的方式 到底對不對？
由於在這最壞的情況下，什麼 如果尼爾在這裡？
因此，只要找到最小的元素 我需要n個步驟，或n減1。
但是，“確定”。
所以修復尼爾。
請記住，一分鐘左右前。
>> 但我怎麼找了下 最小的元素？
這是N減1，或n減去2真的， 從步驟的數量。
這樣就OK了。
所以，我沒有Ñ零下2。
好的。
所以，感覺更好一點。
好的。
下一次多少步 找到3號？
所以N減去4。
因此，它的下降，少一個 在每個迭代步驟。
因此，這並不感覺更好，對不對？
如果最後一次大約是N倍N 這個時候它的N減1，加N減
2，加N減去3，加上n 零下4，點，點，點。
但是，如果你還記得你高中 課本，一點作弊
表背面有公式，如果 你這一系列的數字加起來，
總步數是什麼 要我把這裡嗎？
>> 這是其中的一個，喜歡，正零下 1，次數n，再除以2。
因此，讓我看看，如果我可以拉 這件事只是一瞬間。
再次，我是那種四捨五入一些 編號只是為了讓我們的生活變得簡單，
但我記得，它的東西一樣，如果 我做N減去1件事情，那麼n減去
2，那麼n減去3，大致 超過2，這樣的事情，如果我
乘了這一點， 實際上n的方陣。
這不是感覺太美好了。 Ñ​​零下n次2。
>> 但這裡的東西。
在計算機科學中，出現問題的時候 開始變得有趣的是，當n
變得非常大。
當n變得非常大，這 這些價值觀是要主宰一切
其他人呢？
這是一種n個平方，對不對？
是的，除以2，是相當不錯的。
但是，如果你正在談論數十億 條數據，或萬億
條數據，OK，所以 你快兩倍。
但誰真正關心，如果大的數字， 如果這個因素是什麼得到
越做越大。
當然，它使更多的 差異比這個傢伙。
所以，即使你們是正確的， 第二種算法，我們叫它
選擇排序，是在現實世界中， 潛在快一點，因為我
採取越來越少 每一個步驟的時間。
>> 這不是真正的從根本更快。
因為如果我們真正發揮出 大的n值，結束時
一天，n足夠大，它仍然是 要感到相當緩慢。
好吧，讓我一個 在這最後一關。
這是我所說的 選擇排序。
你們可以自己復位 最後一次？
而在這最後的情況下，我要去 提出的東西
所謂插入排序。
插入排序，概念， 有點不同。
>> 而不是去來回 我選擇最小的元素，
只是去處理這些 傢伙，我遇到他們，並插入
他們到他們的正確的地方。
所以，我只是要開始與Grace， 我看到，她是第四個。
數四屬於哪裡？
我還沒有開始任何排序， 所以格雷斯獲得呆在那裡。
現在，我稍後會要求，如果你能 走一步到您的權利，這
我的排序名單，這是我的 未分類的剩餘列表。
所以，現在我要繼續下， 你叫什麼名字呢？
>> 布蘭森布蘭森：
>> DAVID J.馬蘭：布蘭森。
因此，布蘭森是2號。
所以，我要帶你 出了一會兒。
而現在，你屬於 在這個數組？
所以恩典的權利。
所以，我們又是一種使 格雷斯在這裡做了很多工作。
我們在哪裡把你嗎？
因此，我們要滑動你 離開了，有插入布蘭森。
但現在我要求 你們完成。
但是請注意，我沒有使用額外的空間。
它仍然是2個元素 在這裡，在這裡。
總數組的大小為7，因此我 不要欺騙你，沒事吧？
>> 所以現在我們有加布在這裡， 六，你屬於哪裡？
你很幸運了。
所以，你呆在那裡。
只取一小步的權利 只是為了讓你排序。
現在我們有尼爾再次，數字 1，你在哪裡去了？
現在是我們將開始看到 該算法中，雖然在第一
一目了然，感覺很聰明，看 什麼是即將發生。
如果你能挺身而出。
>> 在哪裡，我們希望把尼爾？
所以，很顯然在這裡，所以如何 我們得到尼爾？
讓我們做到這一步一步的。
加布，你需要去哪裡呢？
沒錯，所以採取一大步， 或兩個半步驟，以使
那邊的一個步驟。
格雷斯，你去哪裡？
好。
所以又邁進了一步。
最後，布蘭森？
另一個步驟。
現在我們可以把尼爾到位。
>> 所以，現在，繼續這樣的邏輯。
即使我們不轉移尼爾 過來，過來，過來，把他
他走到哪裡，在最壞的情況下， 下一個數字，我們可能會遇到能
的數量，例如，有一個數 零，那麼我們要全部轉移
這些傢伙。
假設有一個數字，負 一個，那麼我們必須轉移
所有的這些傢伙。
所以我們真的只是一種翻轉 周圍的問題，這樣，我們
從轉移的費用 選拔過程，所以插入
過程中，如你們剛剛 移動大致Ñ減去的東西
步數。
而且，步數只打算 增加，因為我選擇更多的數字，
如果我要繼續推搡你們 回來，回來，回來。
>> 所以現在傷心的事情是所有這些 算法是n的平方。
讓我們繼續前進，感謝這些 傢伙，這些位可視化
是不同的。
非常出色。
>> [掌聲]
>> 好的。
你去那裡。
感謝 -
>> 布蘭森：[聽不清]保持的數字。
>> DAVID J.馬蘭：沒有，你可能 保持數字。
好的。
幹得漂亮。
好的。
因此，讓我們來看看，如果我們現在不能總結 更為迅速，並且視覺上更
正是剛剛發生了什麼 在這裡，如下所示。
我要繼續前進 拉起Firefox瀏覽器。
我們會鏈接這個示範 本課程的網站。
Java是一個有點惱人獲得工作 在某些瀏覽器，這些天。
所以，如果你在家裡玩這個， 意識到你可能需要使用Firefox
得到它的工作。
什麼，我要做的事情與此 示範以下。
>> 在底部，我有一大堆 菜單選項，包括一個起點和一個
“停止”按鈕。
另外，順便說一句，似乎是一個 在這些程序中的錯誤，讓你
不能真正看到啟動或停止 按鈕，除非你按住Command或Alt
加和變焦，好奇 顯示更多的按鈕。
因此，只是供參考，如果你玩 這個在家。
現在，我要單擊“開始”，在短短 此刻，在指定的延遲後，
只是一樣，在這裡，200毫秒 所以我們可以看到發生了什麼。
>> 因此，我要求這是一個可視化 第一算法
這些傢伙確實，冒泡排序，即 我們交換成對的人。
此可視化的關鍵洞察力 是矩形條的高度
表示的數量的大小。
所以酒吧更高， 數字越大。
較短的酒吧，數字越小。
如果你注意到了，我們正在經歷 在此算法中，在第一次迭代
交換大和小的數字，所以 少數至上
大數量的權利。
>> 而只要我們得到數組的末尾 多數量比七，我們
要回去的開始。
和預測。
在最左邊，那個小傢伙是怎麼回事 交換到一邊，這
過程重複。
現在，這個可視化很快就會 無聊，所以讓我繼續前進，停止
它，改變延遲東西 只是為了得到更快現在，感覺
該算法。
>> 因此，即使我已經加快了，這是 就像我的處理器升級，買
一台新電腦。
我還沒有從根本上改變了我 算法，但你確實可以看到更多的
顯然比人類大 數字冒泡到頂部，
小的數字冒泡 下到谷底。
現在這個東西在這裡排序。
順便說一句，在廣場，有 只是有一些簿記
幫你算多少次比較， 或有多少掉期
實際上已經完成。
>> 好吧，讓我們嘗試之一 我們看到別人。
讓我點擊這裡冒泡排序， 讓我選擇，這整個網頁
是一點點馬車。
讓我們接受的風險 並再次運行它。
我們去那裡。
因此，讓我們做選擇排序。
我不知道為什麼菜單 出現在那裡。
讓我們放大到解決這個問題 錯誤，改到50。
啊，讓我們真正做到 是更快的。
5毫秒左右開始。
>> 因此，這是選擇排序。
如此反复，想想我們 與人類在這裡做了。
我們經歷的數組，並選擇 最小的元素，
一遍，又一遍。
現在，我要求還是蠻不錯的。
它仍然為n的平方，給予或採取， 但它是在現實世界中，位
更快，因為我​​確實服用 略少的每個步驟。
但我們只是在談論什麼？
可能40或酒吧在這裡？
我們不是在談論4000萬美元。
所以它不是完全清楚的，我認為 確實是一個顯著的收益。
>> 現在讓我回去，並改變我們的 第三個算法，它被選擇
插入排序。
而現在它是真的馬車，因為 菜單實在不應該是出現了下滑。
所以，現在，我們將在這裡滾動備份 並啟動此算法。
吶喊，啟動和停止。
所以這一種有一個漂亮的圖案 它，讓我們再次
插入人體，或在 這種情況下，酒吧
其適當的位置。
它之前已經完成 我轉頭。
但是這一個，並且，在理論上， 仍然為n的平方。
>> 因此，讓我們來看看，如果我們不能概括 這些如下。
我要繼續前進，只是為了給 我們一個共同的說話方式
這些事情，讓我介紹一下 這裡只是一個符號位。
你看到的東西叫大 O，因為它實際上就是一個大
O.這是一種方式，一台計算機 科學家或數學家甚至使用
描述的運行時間 的一些算法。
多少步驟，它實際上採取？
>> 現在，我要自己難堪 我的筆跡，在這裡只是一個瞬間。
但是，讓我繼續前進，說 這將是大O字在這裡。
讓我介紹另一個 符號，資本歐米茄。
歐米茄是相反的， 從本質上講，大澳鑑於大O
的手段，在最壞的情況下，多少時間 可能一些算法，
以n，ω是要 多少時間可能
在最好的情況下採取。
我們會看到我們所說的 最好的情況下，在短短的時刻。
>> 所以，讓我們先從簡單的東西。
讓我開始線性搜索。
所以，不排序。
我們稱這個線性搜索。
而現在，做一點 表了這一點。
而現在，線性搜索的情況下， 在最壞的情況下，多少步
它要帶我找到一個 任意選擇的數？
還有的N總門 或n總數。
最壞的情況。
我將不得不多少步 找到在一個數組中的數字50
n個門？
為什麼？
因為它可能是所有 一路過來到年底。
因此，就像珍妮弗遇到， 50號是一路過來，所以在
最壞的情況下的線性搜索 大O的n，我們會說。
>> 怎麼樣最好的情況下， 如果你很幸運嗎？
只是要一步一步， 或恆定的步數。
因此，我們將介紹為1。
因此，這是相當不錯的。
現在，如果我們做的東西 喜歡二進制搜索？
因此，二進制搜索，在最壞的 的情況下，花了多少時間？
>> [插入聲音]
>> DAVID J.馬蘭：其實我 聽到一對夫婦的地方。
因此，它實際上登錄N，給予或採取 因為我們把一半的列表中
一遍，一遍，又一遍，我們能夠 發現，最終，該值，
如果它的存在，但有一個catch。
什麼是假設，我們必須 想當然二進制搜索？
進行排序。
它不排序，可以分割的東西 半一遍又一遍，你
向左走，你可以去， 你可以去左右，但你
不會找到的元素，如果 列表中，因為沒有排序
你可能會錯過它。
因為你的啟發，去左 或向右將是有缺陷的，如果它是
確實沒有排序。
因此，有一個隱藏的成本有點 使用這樣的事情。
>> 現在，讓我們進入我們的排序 算法搜索 -
哦，居然讓我們去在這個空白。
在最好的情況下，二進制搜索？
這也是1，如果它恰好是 在中間的陣列，或
中間的電話簿。
現在，讓我們做冒泡排序。
如此反复，現在我們正在進入 排序，而不是搜索。
>> 在最壞的情況下，沒有多少步 理賠冒泡排序要採取？
擺正Ń。
所以我要畫，。
哦，我的筆跡看起來更糟 當它預計的那麼大。
好的。
所以這Ñ平方。
而冒泡排序在最好的情況下， 多少步，要採取？
1，我聽說了。
>> 揚聲器1：N。
>> DAVID J.馬蘭：N，我聽說了。
>> 揚聲器1：2。
>> DAVID J.馬蘭：2，我聽說了。
我聽到3？
好的。
所以我聽說過1，N 2，但讓我們挑 除了至少在最前面的那
建議，1。
這不是一個壞的本能，因為它 一種遵循一種模式。
但是，如果只需要1步，如何在 世界我聲稱，該清單
排序，因為如果我只允許 1步，多少個元素
其實，我可以檢查，以確保？
那麼，就1，這意味著有Ñ 減去1個元素，可能是滿分
秩序，我只是去後的信仰 看著1元
事情進行排序。
所以這裡不正確。
因此，微創，有多少 我要看看嗎？
>> [插入聲音]
>> DAVID J. MALAN：N減1，還是真的， N，因為我需要看每
元件，以確保 它不是秩序。
但是，我們將再次排序波我們 手較小的數字，
假設，當n變大時，他們 反正無趣。
因此，冒泡排序。
而現在，讓我們做這些最後兩個。
選擇排序，然後我們會 做插入排序。
然後，我們會打擊你的 頭腦的東西多
比所有這些。
好的。
>> 這是最壞的情況下運行 選擇時間排序？
>> 揚聲器4：N的平方。
>> DAVID J.馬蘭：n的方陣，我聽到。
但是，為什麼Ñ平方，直觀？
>> 揚聲器4：因為我們只是做了它。
>> DAVID J.馬蘭：因為我們只是做了它。
確定。
好答案。
但直覺上，這是為什麼選擇 排序Ñ平方？
我們有什麼做 一遍又一遍嗎？
我們必須保持通過掃描， 你最小，你是
最小的，你是最小的。
並授予，我們可以取n 步驟，則n減1，那麼n減去2。
但是，如果你有種把它們統統加起來， 或採取的信心，我已經加入
他們在前進，我們大致得到Ñ 平方減去一些小的數字。
所以，我現在就打電話給這n的平方。
但最好的選擇排序 的情況下，多少步
要帶我嗎？
>> 揚聲器5：[聽不清]
>> DAVID J.馬蘭：這是不幸的 仍然為n的平方，右？
因為如果我選擇最小 元素，我們在這裡有七人，
我只知道，一旦我得到非常 最後，我發現最小
數，無論他或 她可能已經。
但我怎麼找了下 最小的號碼是多少？
我必須做的另一張通行證。
因此，在最好的情況下，什麼是 輸入選擇排序？
這是一個已排序列表，頭號， 數二，數三，數四。
但我一台電腦。
我只能看一眼 在一個時間的事情。
我不能排序採取的一個步驟 像人類和說，
哦，這看起來是正確的。
>> 我只能判決正確性 選擇排序方式選擇
最小數。
但是，即使我發現的頭號第一， 如果我不知道別的約
其他號碼，我不，我 知道，我已經交給一個數組
或一組門後面是 數字，只有這樣，我知道，一個
是最小的嗎？
如果我得到的所有的方式在這裡實現， 該死的，一個是最小的。
>> 但我怎麼確定 二是下一個最小的？
通過做同樣的低效率 一遍又一遍。
最後，用插入排序， 如何，在最壞的情況下，
我們說，它執行？
它也為n的平方。
最好的情況下怎麼樣？
我們會離開，作為一個扣人心弦的。
我們要填補那個空白的下一次， 但首先，讓我建議，我們
從根本上做得比 所有這些，好嗎？
>> 因此，認為自己是什麼插入 排序將是。
嗯，這是不是很劇烈， 因為我是唯一一個
看到了變化。
哇。
確定。
所以，在這裡，我們有一個有點 不同的示範。
如果我在這裡放大，你會看到，在 左邊我們有冒泡排序，
中間我們有選擇排序， 最右邊，我們有些東西
還沒有看過 所謂合併排序。
但我們一直在考慮什麼 在這裡做今天迄今。
當珍妮弗第一次來到了舞台上， 我們經歷過的數字數組
一遍，又一遍，線性搜索， 我們得到了線性運行時間，大O
N，可以這麼說。
>> 當我們現在考慮的第一週 類，當我們分而治之，
我們電話簿撕裂， 和珍妮弗，我們集體
利用關鍵的洞察力，這是 重複自己一遍又一遍
莫名其妙地扔掉，扔掉， 扔掉，一半的問題，或
通常，分割一半中的一個問題， 然後把一塊較小
概念上等同的問題 另一方面，我們莫名其妙地做
從根本上更好。
但隨著冒泡排序，選擇 排序，插入排序，我們可能
詹妮弗沒有這樣的見解。
我們非常簡單，只是走回 提出了一大堆的時候，我們
調整了一點點東西，交換 在這個命令，也許
插入或選擇。
但是在一天結束的時候，我做了很多 尷尬的步行來回。
我們並沒有真正利用的東西 智能不喜歡像珍妮弗除以
和征服。
>> 因此，歸併排序，與此相反，我們 直到下週不會看到，它是怎麼回事
除以利用的關鍵概念 的輸入，然後減半，然後
減半，再減半。
和在該循環的每次迭代， 排序的左半邊和右
減半的話，左半邊的左半部分， 和右半邊的左方，再
的左半部的右半部分，並 的右半邊的右半部分。
並重複一遍又一遍。
>> 所以，你會看到在視覺上，但是這 是什麼在等待著我們下週。
而在一般情況下，當我們覺得一點點 任何這樣的問題上有點困難。
我們有N平方的左側，正 在中間，和n平方
n在登錄的權利。
因此，有你真正的懸​​念。
我們會看到你在星期一。
>> [掌聲]