[音樂播放] 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在登錄的權利。因此，有你真正的懸念。我們會看到你在星期一。 [掌聲]