[Powered by Google Translate] [第3條 - 更舒適]
[羅布·鮑登 - 哈佛大學]
>> [這是CS50。 - CS50.TV]
>> 所以第一個問題是奇怪的措辭。
GDB可以讓你“調試”程序，但是，更具體地說，是什麼讓你這樣做嗎？
我會回答這個問題，我不知道發生了什麼準確預計，
所以我猜它的東西，它的沿線，讓你一步一步
步行通過該計劃，與它進行交互，更改變量，做所有這些事情 -
基本上完全控制程序的執行
並檢查執行的程序的一部分。
因此，這些功能可以讓你調試的東西。
好吧。
為什麼二進制搜索需要一個數組進行排序？
誰願意回答這個問題嗎？
[學生]：因為這是行不通的，如果它不排序。 >>呀。 [笑聲]
如果沒有排序，那是不可能的分裂它的一半
知道這一切的左側是少的一切權利
大於中間值。
因此，它需要進行排序。
好吧。
為什麼是冒泡排序在O n的平方嗎？
有誰首先要給予什麼冒泡排序是一個非常快的高層次的概述？
[學生]：基本上，您的每一個元素，你去檢查的前幾個元素。
吧，如果的你交換他們的地方，然後你查了下幾個元素等。
當你到達終點，那麼你知道，最大的元素放在最後，
所以你忽視這一點的話，你繼續經歷，
每一次，你必須檢查少了一個元素，直到你不改變。 >>呀。
這就是所謂的冒泡排序，因為如果你在其一側翻轉數組，所以它的向上和向下，垂直，
那麼大的值會沉底，小的值將泡沫到頂部。
這就是它得到了它的名字。
是啊，你只是去。
你繼續通過陣列，交換中的較大值
得到最大的值的底部。
>> 為什麼是IT O n的平方呢？
首先，沒有人說為什麼它是Øn的平方？
[學生]由於每次運行時，它會n次。
您只能確保你已經採取了最大的元素一路下跌，
那麼，你必須重複一樣多的元素。 >>呀。
所以記住什麼大的“O”表示什麼大的歐米茄手段。
大O是一樣的上限如何慢，其實是可以運行的。
所以說的O n的平方，它是不是O的n否則將無法運行
線性時間，但它是O n的立方
因為它的邊界是由O n個立方。
如果它一定的O n的平方，那麼它的界也由N的立方。
因此，它是n的平方，絕對是最糟糕的情況下，不能做的更好比n的平方，
這就是為什麼它是O n個平方。
它是如何為n的平方，所以看到輕微的數學，
如果我們有五件事情在我們的名單中，第一次能有多少掉期我們可能需要進行
為了得到它？讓我們實際上只是 -
多少掉期，我們要通過數組必須在第一次運行的冒泡排序？
[學生]：N - 1。 >>呀。
>> 如果有5個元素，我們需要做N - 1。
然後在第二個我們要多少掉期使嗎？
[學生]：N - 2。 >>呀。
第三個是為n - 3，然後為方便起見，我會寫的最後兩
然後我們需要做2掉期和1交換。
我想最後一個可能會或可能不會實際需要的情況發生。
它是一個交換嗎？我不知道。
因此，這些掉期交易的總金額，或者至少比較，你必須做出。
即使你不交換，你仍然需要的值進行比較。
因此，有n - 1個比較，在第一次運行時通過數組。
如果你重新安排這些事情，讓我們實際上使六樣東西，這樣的事情疊加起來很好，
然後我會做3，2，1。
因此，只要重新排列這些錢，我們希望看到我們做多少次比較
在整個算法。
因此，如果我們把這些傢伙在這裡，
然後我們還只是總結然而有許多比較。
但是，如果我們總結，我們總結，我們總結這些，
它仍然是同樣的問題。我們只是總結了這些特殊群體。
>> 所以，現在我們正在總結3 N。這不只是3 n的。
它總是要N / 2 n的。
所以，我們在這裡發生的有6個。
如果我們有10件事情，那麼我們可以做到這一點分組為5個不同的東西對
和N + N + N + N + N。
所以，你總是會得到N / 2 n的，所以這一點，我們就會把它記為n的平方/ 2。
因此，即使它的一半，捎來的因素
由於這一事實，通過在陣列的每個迭代中，我們比較少1
所以這就是我們得到了超過2，但它仍然為n的平方。
我們不關心的常數因子的一半。
所以這樣一個大O的東西很多依賴於只是做這類數學，
做算術金額的幾何級數的東西，
但他們大多在此過程是非常簡單的。
好吧。
為什麼是插入排序在歐米茄的n？歐米茄是什麼意思？
兩名學生在一次發言 - 不知所云] >>呀。
歐米茄你能想到的下限。
>> 因此，無論您的插入排序算法的效率有多高，
無論通過在列表中的，它總​​是有比較至少有n個東西
或重複過N。
這是為什麼？
[學生]因為如果列表已經排序，然後通過一次迭代
你的第一個元素是最少的，只能保證
和第二次迭​​代中，您只能保證前兩個是
因為你不知道，其餘的列表進行排序。 >>呀。
如果你傳遞一個完全排序的列表，最起碼你得去所有的元素
看，沒有什麼需要左右移動。
因此，通過列表，並說哦，這已經排序，
這是不可能的，你知道它的排序，直到你檢查每個元素
看，他們是在排序順序。
所以插入排序的下限是歐米茄的n。
什麼是最壞的情況下，歸併排序的運行時間，
最壞的情況是大O嗎？
因此，在最壞的情況下，如何合併排序運行？
[學生] n日誌n。 >>呀。
一般最快的排序算法是n日誌n。你不能做的更好。
>> 有特殊情況下，如果我們今天有時間 - 但我們可能won't -
我們可以看到，它比n日誌n。
但在一般情況下，你不能做的更好比n日誌n。
合併排序恰好是一個你應該知道這門課程是n日誌n。
因此，我們實際上將實施的今天。
最後，在不超過三句話，選擇排序是如何工作的？
是否有人要回答的問題，我會計算你的句子
因為如果你在3 -
有誰還記得選擇排序？
選擇排序通常是很容易記住的名稱。
您遍歷該數組，無論值最大或最小 -
任何順序排序
因此，讓我們說，我們正在從最小到最大的排序。
您遍歷數組，尋找任何的最小元素，
選擇它，然後就交換，無論是擺在首位。
然後在數組中的第二次，再次尋找最小的元素，
選擇它，然後交換在第二的位置。
因此，我們只是挑選和選擇的最低值
將它們插入到陣列的前面，直到它被排序。
該問題嗎？
>> 這些不可避免地出現在你的表格必須填寫，當你提交的pset。
這些基本上都是那些的答案。
好了，現在編碼的問題。
我已經發送過電子郵件 - 沒有人不明白的電子郵件嗎？好吧。
我已經發送過電子郵件，我們將要使用的空間，
如果你點擊我的名字 - 所以我想我會在底部
由於向後ŕ - 但如果你點擊我的名字，你會看到兩個版本。
第1次修訂將要被我已經複製並粘貼代碼到空間
搜索的事情，你將不得不實行。
第二次修訂將排序的事情，我們實施之後。
因此，您可以點擊我的第1次修訂，並從那裡工作。
現在我們要實現二進制搜索。
>> 有沒有人想只給一個偽高層次的解釋
我們有做搜索？是啊。
[學生]你只取中間的數組，如果你正在尋找
小於或大於。
如果是少了，你去的那一半少，
，如果它更重要的是，你去了一半，更重要的是，你重複，直到你剛剛得到的一件事。
鮑登]是啊。
請注意，我們的數字數組已經排序，
因此，這意味著，我們可以利用這一點，我們可以先檢查，
好了，我在尋找數50。
所以，我可以進入中間。
中間是很難界定的東西，它是一個偶數時，
但我們只能說我們會永遠的中間截斷。
所以在這裡我們8件事，所以中間是16。
我在尋找50，所以50大於16。
所以，現在我基本上可以把我的數組，因為這些元素。
我可以扔掉一切從16倍。
現在我的數組是這4個元素，讓我再說一遍。
於是我想再次找到中間，這將是42。
42小於50，這樣我就可以扔掉這兩種元素。
這是我剩下的陣列。
我要再次找到中間。
我想50是一個壞榜樣，因為我總是扔掉的左的東西，
但相同的措施，如果我在尋找的東西
，它是小於的元素，我目前正在研究，
然後，我要扔掉的一切權利。
所以，現在我們需要實現這一點。
請注意，我們需要傳遞的大小。
我們也可以不需要進行硬編碼的大小。
因此，如果我們擺脫這種定義 -
好吧。
我怎樣才能很好地計算出目前的數字數組的大小是什麼？
>> 數字數組有多少個元素？
[學生]數字，括號，長度？
[鮑登]不存在C中
需要的長度。
陣列所不具有的特性，所以數組有沒有length屬性
這只會給你然而，它正好是。
[學生]它有多大的內存和除以多少 - “”是啊。
所以我們可以看到它有多大的內存？ >> [學生] SIZEOF。 “是啊，大小。
sizeof是操作員要返回的數字數組的大小。
這是怎麼回事，然而，許多整數有一個整數的大小
因為這是多大的內存，它實際上是佔用了。
所以，如果我想在陣列中的一些事情，
然後，我會想除以整數的大小。
好吧。所以，讓我在這裡傳遞的大小。
為什麼我需要傳遞的大小嗎？
為什麼我不能只是做了詮釋大小=大小（幹草堆）/ sizeof（int）的的嗎？
為什麼不工作？
[學生]：這是不是一個全局變量。
鮑登草堆存在，我們通過在數字草垛，
這是一種什麼樣的來了伏筆。是啊。
[學生]草堆只是對它的引用，所以它會返回引用是多大。
是啊。
我懷疑你在課堂上看到了堆棧真的，對嗎？
我們剛剛談到它。
所以堆棧是其中所有變量都以被存儲。
>> 在堆棧中為局部變量的分配的任何內存是怎麼回事，
每一個函數都有自己的堆棧空間，它自己的堆棧幀是它叫什麼。
因此，主要有它的棧幀，然後在它裡面會存在這方面的數字陣列，
它的尺寸大小（數字）。
這將有大小除以元素大小的數字，
但主要的堆棧幀中所有的生命。
當我們調用搜索，搜索得到它自己的堆棧幀，
自己的空間來存儲所有的局部變量。
但這些參數 - 草垛是不是這整個數組的副本。
我們不會將整個陣列作為複製到搜索。
它只是傳遞一個引用到該數組。
因此，搜索就可以訪問這些數字，通過這個引用。
它仍然訪問主要的堆棧幀裡面的東西，生活，
但基本上，當我們得到的指針，這應該是很快，
這是指針是什麼。
只是指針引用的東西，你可以使用指針來訪問的東西
在其他的事情'堆棧幀。
因此，儘管數字是當地主，我們仍然可以訪問它，通過這個指針。
但是，因為它只是一個指針，它只是一個參考，
大小（幹草堆）返回引用本身的大小。
它不會返回它指向的東西的大小。
它不返回數字的實際大小。
所以這是去上班，因為我們希望它。
>> 該問題嗎？
指針將進入顯著血淋淋的細節在數週的到來。
這就是為什麼有很多的東西，你看，大多數搜索的東西或排序的東西，
他們幾乎所有的事情，需要採取實際數組的大小，
因為在C中，我們不知道數組的大小。
您需要手動將它傳遞進來。
你也可以手動通過整個陣列，因為你只是路過的參考
它不能得到從基準的大小。
好吧。
所以，現在我們要實現什麼解釋過。
你可以在一分鐘，
你不必擔心讓一切完美的100％。
只寫了一半的偽代碼，你是怎麼想它應該工作。
好吧。
沒有必要完全做到這一點。
但是，沒有人感到舒適與他們有什麼到目前為止，
喜歡的東西，我們可以一起嗎？
有沒有人想自願嗎？或者我會隨機挑選。
它不具有任何措施，而是東西，我們可以通過修改進入了工作狀態是正確的。
[學生]：當然可以。 “好了。
所以，你可以保存修改，點擊保存圖標上的小。
你專區Ramya，對不對？ >> [學生]是啊。 >> [鮑登]好吧。
所以，現在我可以看到你的修訂，每個人都可以拉起來的修訂。
在這裡，我們有 - 好。
於是專區Ramya的遞歸解決方案，這無疑是一個有效的解決方案。
有兩種方法可以做到這一點問題。
你可以做到這一點迭代或遞歸。
大多數遇到的問題，可以做遞歸也可以通過反复。
所以，在這裡，我們已經做了遞歸。
>> 是否有人想函數的遞歸定義是什麼意思？
[學生]當你有一個函數調用自身
然後調用，直到它與真正的和真實的。 >>呀。
遞歸函數僅僅是一個函數調用自己的。
有三個大的事情，必須有一個遞歸函數。
第一種是很明顯，它調用自身。
第二個是基本情況。
因此，在某些時候，需要停止調用本身，
而這正是的基本情況。
所以，在這裡，我們知道，我們應該停止，我們應該放棄在我們的搜索
當開始等於結束 - 我們就去了，這意味著什麼。
不過，最後的最後一件事是重要的遞歸函數：
函數必須以某種方式接近的基本情況。
喜歡，如果你不更新任何東西時，你的第二次遞歸調用，
如果你真的只是調用該函數使用相同的參數
沒有全局變量發生了變化或任何東西，
你將永遠不會達到的基本情況，在這種情況下，這是很糟糕。
這將是一個無限遞歸和棧溢出。
但在這裡我們可以看到，在更新發生，因為我們正在更新啟動+ / 2年底，
我們正在更新結束參數在這裡，我們在這裡更新start參數。
因此，在所有的遞歸調用，我們要更新的東西。好吧。
你想，走我們通過您的解決方案？ “當然可以。
我使用搜索幫助，這樣每次我有這樣的函數調用
我有我在尋找數組中的開始和結束
在哪裡，我要找的數組。
>> 在每一個步驟，它說這是中間的元素，這是啟動+ / 2年底，
等於我們正在尋找什麼？
如果是這樣，那麼我們發現它，我想會向上傳遞層次的遞歸。
如果這是不正確的，那麼我們是否該中間值的數組過大，
在這種情況下，我們看陣列的左半邊，從開始到中間索引。
否則，我們做半場結束。
鮑登]好吧。
聽起來很好。
好了，這樣一對夫婦的事情，而實際上，這是一個非常高層次的東西
你永遠不會知道這門課程，但它是真實的。
遞歸函數，你總是聽到的是一個糟糕的協議
因為如果你遞歸地調用自己太多的時間，你會得到堆棧溢出
因為，正如我之前說的，每一個函數都有自己的堆棧幀。
因此，每次調用遞歸函數都有自己的堆棧幀。
所以，如果你1000遞歸調用，你會得到1000個堆棧幀，
快，你有太多的棧幀，和剛剛突破。
所以這就是為什麼遞歸函數一般都是壞的。
但有一個不錯的遞歸函數的子集稱為尾遞歸函數，
發生這種情況是一個例子，其中，如果編譯器注意到這個
它應該，我認為 - 鐺，如果你傳遞給它的O2標誌
然後，它會發現這是尾遞歸的東西好。
>> 一遍又一遍，每一次遞歸調用，它會重複使用相同的堆棧幀。
因此，由於您使用的是相同的堆棧幀，你不不必擔心
曾經堆棧溢出，並在同一時間，像你說的，
一旦你返回true，那麼它返回所有這些堆棧幀的
和第10個調用搜索幫助返回的第9位，具有返回到8號。
因此，不需要時發生的功能是尾遞歸。
是什麼讓這個功能尾遞歸的通知，對於任何給定調用搜索幫助
的遞歸調用它的是它的返回。
因此，在第一次調用搜索幫助，我們將立即返回false，
立即返回true，否則我們做一個遞歸調用搜索幫助
我們回到調用返回。
而且我們不能這樣做，如果我們做的東西，如int x =搜索幫助，返回X * 2，
只是一些隨機的變化。
>> 所以，現在這個遞歸調用，此int x =搜索幫助遞歸調用，
不再是尾遞歸，因為它實際上不返回
返回到前一個堆棧幀，這樣，以前的呼叫的功能
然後做一些事情的返回值。
因此，這是不是尾遞歸，但我們以前是很好的尾遞歸。是啊。
[學生]不應該的第二基本情況，首先檢查
因為有可能的情況就是當你傳遞給它的參數
你已經開始=結束，但他們是針價值。
問題是不能運行的情況下到針到底是值
或開始=結束，適當的，開始結束
，你有沒有檢查那個特定的值，
然後開始+ / 2年底將是相同的值。
但我們已經返回false，我們從來沒有真正得到的價值。
所以，最起碼，在第一次調用，如果大小是0，那麼，我們要返回false。
但是，如果大小為1，然後開始不等於結束，
我們將至少檢查一個元素。
但我認為你是正確的，我們就可以結束的情況下，啟動+ / 2年底，
開始結束了一樣啟動+ / 2年底，
但我們從來沒有真正檢查該元素。
>> 因此，如果我們首先檢查的是中間的元素，我們正在尋找的價值，
那麼我們就可以立即返回true。
否則，如果他們是平等的，那麼有沒有點繼續
因為我們只是要更新的情況下，我們是一個單元素數組。
如果，不是一個單一的元素是我們正在尋找的，
然後一切是錯誤的。是啊。
[學生]的事情是，由於大小實際上是大於在數組中的元素數
已經有一個偏移 - “等的大小 -
[學生]說，如果數組的大小為0，然後搜索幫助將實際檢查草垛0
在第一次調用。
數組的大小為0，所以0是 - “”是啊。
還有另外一件事， - 這可能是很好的。讓我們來想想。
所以，如果數組有10個元素，我們要檢查的是中間的一個指數5，
所以我們正在檢查，讓我們說，該值小於。
因此，我們把一切都帶走5起。
因此，+ / 2年底將是我們新的終端，
所以是的，它總是要留結束之後的數組。
如果它是一個情況下，如果是奇數或偶數，然後我們會檢查，說，4，
但我們仍然丟掉 -
所以，是的，最終總是要超出了實際的數組。
所以我們的重點元素，最終總是要一前一後的。
所以，如果開始做以往任何時候都等於結束，我們是在一個數組的大小為0。
>> 其他的事情，我的想法是，我們正在更新開始啟動+ / 2年底，
所以這種情況下，我有麻煩，在那裡開始+端/ 2
是的，我們正在檢查的元素。
比方說，我們這10個元素的數組。不管。
因此，+ / 2年底將是像這樣的東西，
如果這不是價值，說，我們要更新。
該值越大，所以，我們想看看在這半年的數組。
因此，我們如何更新開始，我們要更新開始到現在是這樣的元素。
但是，這可能仍然工作，或最起碼，你可以開始+結束/ 2 + 1。
[學生]您不需要開始+結束[聽不清] >>呀。
我們已經檢查了這個元素，而且知道這是不是我們正在尋找一個。
因此，我們並不需要更新的開始是這樣的元素。
我們可以跳過它，並更新開始是這樣的元素。
而且是有過的情況下，讓我們說，這是結束，
因此，然後開始應該是這樣的，開始+結束/ 2應該是這樣的，
開始+結束 - 是的，我認為它可以在無限遞歸。
比方說，它只是一個大小為2的數組或數組的大小為1。我認為這會工作。
目前，開始元素和結束是超越它。
因此，我們要檢查的元素是這一個，
，然後我們在更新開始時，我們要更新開始為0 + 1/2，
這是要結束我們開始這個元素。
>> 所以，我們檢查了一遍又一遍相同的元素。
因此，這是每一個遞歸調用的情況下，必須更新的東西。
因此，我們需要做的啟動+端/ 2 + 1，否則有一個
在這裡我們實際上沒有更新的開始。
每個人都看到了嗎？
好吧。
有沒有人有問題，該解決方案或任何更多的評論？
好吧。沒有任何人有一個迭代的解決方案，我們都可以看嗎？
我們都這樣做遞歸？
我也想，如果你打開了她，那麼你可能會覆蓋你的前一個。
它會自動保存嗎？我還不能肯定。
沒有任何人有反复？
我們可以一起穿過它，如果沒有。
這個想法是將是相同的。
迭代的解決方案。
我們會想，基本上做的是同樣的想法
在這裡我們要跟踪的數組的數組新的結束和新的開始
做一遍又一遍。
並且如果我們跟踪作為開始標記和結束計劃相交，
當時我們沒有找到它，我們可以返回false。
那麼，如何才能做到這一點？任何人有任何建議或代碼為我拉起來嗎？
[學生]做一個while循環。 >>呀。
你會希望做一個循環。
>> 你的代碼，我可以拉，你要什麼建議嗎？
[學生]我是這麼認為的。 >>所有權利。這使事情變得更容易。你叫什麼名字？
[學生]盧卡斯。
第1次修訂。好吧。
低就是我們俗稱的開始之前。
是不完全是我們稱為前結束。
其實，到底是現在在陣列內。這是我們應該考慮的元素。
如此之低是0，是陣列的大小， - 1，
，現在我們正在循環，我們正在檢查 -
我想你可以穿過它。
什麼是你的想法通過呢？走我們通過您的代碼。
[學生]：當然可以。在草垛的中間值，並把它比作針。
所以，如果要大於你的針，然後你想 - 哦，其實，應該是向後。
你會想扔掉的右半邊，所以是的，這應該是方法。
[鮑登]因此，這應該是少了呢？這就是你說的嗎？ >> [學生]是啊。
鮑登]好吧。更少一些。
所以，如果我們要找的是比我們想要的東西，
是啊，我們要扔掉的左半邊，
這意味著我們正在更新我們的一切考慮
移動低的數組的權利。
這看起來不錯。
我認為它有同樣的問題，我們說，前一個，
其中，如果低為0和為1，則低+上/ 2的成立是同樣的事情再次。
>> 甚至如果不是這樣的情況下，它仍然是更有效地在至少
扔掉的元素，我們只是看著我們知道這是錯誤的。
如此之低+ / 2 + 1 - [學生]這應該是其他方式。
鮑登或者這應該是 - 1，另一個應該是+ 1。
[學生]：應該有一個雙等號。 >> [鮑登]是啊。
[學生]是啊。
好吧。
最後，現在，我們有這樣的+ 1 - 1的事情，
是它 - 它可能不是 - 是為低，結束了更大的值比起來，有沒有可能？
我認為唯一的方法可能發生的 - 它是可能的嗎？ >> [學生]：我不知道。
但是，如果它被截斷，然後得到減去1，然後 - “”是啊。
[學生]，可能會出現混亂。
我認為這應該是不錯的，只是因為
結束下，他們必須是平等的，我想。
但如果他們是平等的，那麼我們就不會做了while循環開始
我們只是將返回的值。因此，我認為，我們現在是很好的。
請注意，儘管這個問題已不再是遞歸的，
同一種想法適用於我們可以看到這本身很容易
一個遞歸的解決方案的事實，我們只是更新的指數，一遍又一遍，
我們正在做的小問題，我們關注的一個子集的數組。
[學生]如果低為0和1，它們都為0 + 1/2，這將去0，
，然後將+ 1， - 1。
[學生]：我們在哪裡檢查的平等？
就像如果中間實際上是針？
目前我們還沒有這樣做呢？哦！
如果it's -
是。我們不能只是做了測試，在這裡，因為咱們說的第一個中間 -
[學生]：它實際上是想扔掉的結合。
所以，如果你扔掉綁定的，你必須先檢查或任何。
啊。是啊。 >> [學生]是啊。
所以，現在我們丟掉了一個我們目前看，
這意味著我們現在還需要有
（幹草堆（低+）/ 2] ==針），然後我們就可以返回true。
是否其他人或只是如果，我把它的字面意思是同樣的事情
因為這會返回true。
所以我會把其他的話，但不要緊。
>> 因此，如果這一點，否則這一點，這是常見的事，我做
即使它的情況下，一切都很好，在這裡，
如低永遠不能大於了起來，這是不值得的推理​​是否是真實的。
所以，你可以說，而低是小於或等於
或在低是小於
這樣，如果他們永遠等於或低恰巧經過，
然後我們就可以打破這個循環。
問題，問題，意見嗎？
好吧。這看起來不錯。
現在，我們想要做的那種。
如果我們去我的第二次​​修訂，我們看到這些相同的數字，
但現在他們不再有序。
我們要實現使用任何算法在O n日誌n。
所以，你認為哪種算法，我們應該在這裡實現嗎？ >> [學生]歸併排序。
鮑登]是啊。合併排序是O（n日誌n），所以這就是我們要做的。
的問題將是非常相似的，
它輕易借錢給別人，自己一個遞歸的解決方案。
我們也可以拿出一個迭代的解決方案，如果我們想，
但遞歸會更容易在這裡，我們應該做的遞歸。
我想我們將通過合併排序第一，
雖然已經有一個可愛的視頻歸併排序。 [笑聲]
因此，合併排序有 - 我浪費這麼多的本文。
哦，只有一個左。
所以合併。
哦，1，3，5。
好吧。
合併需要兩個單獨的陣列。
單獨這兩個數組進行排序。
因此，這個數組，1，3，5，排序。此陣列中，0，2，4，排序。
現在合併你應該做的是將它們組合成一個單一的陣列本身就是排序。
因此，我們希望，都將有它裡面的這些元素的數組的大小為6
在排序順序。
>> 因此，我們可以利用一個事實，即這兩個數組進行排序
做到這一點的線性時間，
線性時間的意義，如果這個數組的大小為x，這是大小y，
那麼總的算法應該是O（X + Y）。好吧。
因此，建議。
[學生]我們從左邊開始？
所以，你把0下來，然後1，然後你在這裡的2。
因此，它是一種像你有一個標籤，向右移動。 >> [鮑登]是啊。
對於這些數組，如果我們只專注於最左邊的元素。
因為這兩個數組進行排序，我們知道，這2個元素
是任一陣列中的最小元素。
因此，這意味著這2個要素：1，必須是我們的合併數組中最小的元素。
碰巧的是，最小的是一個正確的時間。
因此，我們採取0，將其插入在左邊，因為0小於1，
所以取0，將其插入到我們的第一個位置，然後更新
到現在為止的第一個元素。
現在，我們重複。
所以，現在我們比較2和1。 1較小，因此，我們將插入1。
我們更新該指針指向這個傢伙。
現在，我們再次做到這一點，所以2。這將更新，比較這2個，3個。
此更新，然後4和5。
所以這是合併。
>> 這應該是很明顯的，它是線性的時間，因為我們只是一次過的每個元素。
這是實施合併排序是這樣做的最大的一步。
它並不難。
有兩件事情要擔心的是，比方說，我們合併1，2，3，4，5，6。
在這種情況下，我們最終場景中的這個人會是較小的，
然後我們更新this指針，這將是更小，更新，
這其中的體積更小，現在你不得不承認
當你運行的元素比較。
因為我們已經使用了這整個陣列，
此數組中的一切現在只是插入到這裡。
所以，如果我們運行其中之一，我們的陣列已經完全融合進點，
然後我們就採取的其他陣列中的所有元素，並將其插入到數組末尾的。
因此，我們就可以插入4，5，6。好吧。
這是一件事要注意的。
實現這應該是第1步。
合併排序，然後此基礎上，它的2個步驟，2個愚蠢的步驟。
讓我們把這個數組中。
所以，歸併排序，第1步是，遞歸打破數組轉換成半。
所以這個數組分割成兩半。
我們現在有4，15，16，50和8，23，42，108。
現在，我們做了一遍，我們分裂成兩半。
我會做的這一邊。
因此，4，15和16，50。
在這裡，我們會做同樣的事情。
現在，我們把它分解成半。
我們有4個，15，16，50。
所以這是我們的基本情況。
一旦數組的大小為1，那麼我們就停止分裂成兩半。
>> 現在我們該怎麼做這個嗎？
我們結束了，這也將分解成8，23，42，和108。
所以，現在，我們在這一點上，現在歸併排序的步驟2的合併對的列表。
因此，我們要合併這些。我們只是調用合併。
我們知道合併將返回這些排序。
4，15。
現在，我們要合併這些，這將返回一個列表的排序順序，
16，50。
我們合併者 - 我不能寫 - 8，23，42，108。
因此，我們必須對一次合併。
現在，我們只需再合併。
請注意，每個列表進行排序本身，
然後我們就可以合併這些列表進行排序的列表大小為4
合併這兩個列表進行排序的列表大小為4。
最後，我們可以合併這兩個列表大小為4，得到一個列表進行排序大小為8。
因此，看，這是整體的n日誌n，我們已經看到的，合併是線性的，
所以，當我們在處理這些的合併，等等之類的整體成本合併
這兩個名單只是因為 -
好，這是O n個，但N在這裡僅僅是這2個元素，所以它的2。
而這些2將2​​和2將是2和2將是2，
在所有的合併，我們需要做的，我們做Ň。
像2 + 2 + 2 + 2是8，它是N，
所以在這個集合的合併成本是n。
然後是同樣的東西在這裡。
我們將合併這兩個，那麼這些2，本次合併及個別將採取四項業務，
本次合併將採取四則運算，但再一次，在所有這些，
我們最終合併N總的事情，所以這一步需要Ň。
因此，每個級別需要n個元素被合併。
>> 有多少級？
在每個級別上，我們的陣列生長的大小。
在這裡我們的數組的大小為1，在這裡，他們是大小為2，在這裡，他們是大小為4，
最後，它們的大小為8。
所以，因為它增加了一倍，有將是一個總的日誌n這些水平。
所以取n日誌n個層次，每個人的水平總運營，
我們得到了一個n日誌n算法。
有問題嗎？
人已經取得了進展如何實現這一點呢？
有人已經在一個國家，在那裡我可以拉起自己的代碼嗎？
我可以給一分鐘。
此人將變得更長。
我強烈建議復發 -
你不必做遞歸合併
遞歸合併，因為這樣做，你將不得不通過不同大小的一堆。
可以，但是這很煩人。
但是，遞歸進行排序本身是很容易的。
你只從字面上調用sort左半邊，右半邊的排序上。好吧。
任何人有什麼我可以拉起來嗎？
不然我會給一分鐘。
好吧。
任何人有什麼我們可以使用嗎？
否則，我們就與這，​​然後從那裡展開。
>> 任何人有以上這一點，我可以拉起來嗎？
[學生]是啊。你可以把我的。 >>所有權利。
是的！
[學生]有很多的條件。哦，拍攝。你能 -
[學生]我一定要救它。 >>呀。
所以，我們做單獨的合併。
哦，但它不是那麼糟糕。
好吧。
因此，排序本身就是只是打電話mergeSortHelp。
我們解釋，什麼mergeSortHelp。
[學生] MergeSortHelp幾乎沒有兩個主要步驟，
這是分類，每個陣列的一半，然後合併他們兩個。
[鮑登]好吧，所以給了我第二次​​。
我認為這 - >> [學生]我需要 -
是啊。我失去了一些東西。
在合併，我意識到，我需要創建一個新的數組
因為我不能這樣做的地方。 “是的。你不能。正確的。
[學生]：因此，我創建了一個新的陣列。
我忘了在年底合併，重新更改。
好吧。我們需要一個新的陣列。
在合併排序，這是幾乎總是正確的。
一個更好的算法，時間上的成本部分
幾乎總是需要使用更多的內存。
所以在這裡，無論你怎麼做歸併排序，
你將不可避免地需要使用一些額外的內存。
他或她創造了一個新的陣列。
然後你說結束時，我們只需要到新的數組複製到原來的數組。
[學生]我是這麼認為的，是的。
我不知道如果這樣的作品在計數的參考或任何方面 -
是的，它會奏效。 >> [學生]好吧。
你有沒有嘗試運行此？ >> [學生]不，還沒有。 “好了。
嘗試運行它，然後我就說說它的第二個。
[學生]我需要把所有的函數原型和一切，但是，對不對？
函數原型。哦，你說的一樣 - 是的。
排序打電話mergeSortHelp。
>> 所以為了進行排序打電話mergeSortHelp，mergeSortHelp必須已定義
排序或之前，我們需要的只是原型。只需複製並粘貼。
同樣，mergeSortHelp被調用合併，
但合併還沒有被定義，所以我們可以讓mergeSortHelp知道
的合併將是什麼樣子，就是這樣。
所以mergeSortHelp。
我們在這裡有一個問題，我們有沒有基礎的情況下。
MergeSortHelp是遞歸的，所以任何遞歸函數
將需要某種形式的基本情況，知道什麼時候才能停止遞歸調用本身。
什麼是我們的基本情況，要在這裡嗎？是啊。
[學生]如果大小為1？ >> [鮑登]是的。
所以，像我們看到，我們停止分裂陣列
一旦我們得到數組的大小為1，這不可避免地排序。
因此，如果大小等於1，我們知道已經排序的數組，
這樣，我們就可以返回。
>> 請注意，這是無效的，所以我們不返回任何特別的，我們只是返回。
好吧。所以這是我們的基本情況。
我想我們的基本情況也可能是，如果我們碰巧被合併數組的大小為0，
我們可能要停止在某些時候，
所以我們只能說大小小於2或小於或等於1
因此，這將工作的任何陣列。
好吧。
所以這是我們的基本情況。
現在你要帶我們通過合併嗎？
所有這些情況意味著什麼呢？
在這裡，我們只是在做同樣的想法， -
[學生]我需要通過大小，所有的mergeSortHelp調用。
我一個額外的主增加的大小和它的不存在，如大小/ 2。
[鮑登]哦，尺寸/ 2，尺寸/ 2。 >> [學生]是啊，在上面的函數，以及。
鮑登]在這裡？ >> [學生]只要大小。 >> [鮑登哦。大小，尺寸是多少？ >> [學生]是啊。
鮑登]好吧。
讓我想到的第二個。
我們遇到的問題嗎？
我們一直在治療左為0。 >> [學生]第
這是不對的。抱歉。它應該是開始。是啊。
鮑登]好吧。我想效果更好。
和結束。好吧。
所以，現在你要帶領我們通過合併嗎？ >> [學生]好吧。
我只是走過，我創建了這個新陣列。
它的大小是陣列的部分的大小，我們要進行排序
，並試圖找到的元素，我應該把在新的陣列步驟。
因此，要做到這一點，首先我檢查的數組，如果左邊的一半繼續有任何更多的元素，
如果沒有的話，那麼你去，其他情況下，只是說
好了，它必須是在右邊的數組，我們將提出，在目前的指數newArray。
>> 然後否則，我檢查，如果陣列的右側也完成，
在這種情況下，我只是把在左邊。
這實際上可能不會是必要的。我不太肯定。
但無論如何，其他兩個檢查其中的兩個較小的左側或右側。
此外，在每一種情況下，我在遞增佔位符，我增加。
鮑登]好吧。
看起來不錯。
沒有任何人有任何意見或疑慮或問題嗎？
所以的情況下，我們到的是，要帶的東西 - 它看起來像5 -
但我們要考慮的事情，我們需要合併左數組是否已用完，
右邊的數組是否已用完的事情，我們需要合併 -
我指著不惜一切代價。
所以，左數組是否已用完的東西或已用完的東西，右邊的數組。
這兩種情況。
我們還需要瑣碎的情況下，是否在左邊的是不到正確的事情。
然後我們要選擇左側的事情。
這些都是案件。
因此，這是正確的，所以就是這樣。
陣列離開了。它是1，2，3。好吧。所以，是的，這些都是我們可能想要做的四件事。
我們不會在一個迭代的解決方案。
我不會建議 -
合併排序是一個函數，是不是尾遞歸的例子，
這是不容易的是尾遞歸，
而且它不是很容易，使迭代。
這是很容易的。
此實現歸併排序，
合併，不管你做什麼，你要建立合併。
>> 因此，遞歸排序建立在合併的合併僅僅是這三條線。
迭代，它是更煩人，更難以思考。
但是請注意，這不是尾遞歸，因為mergeSortHelp - 當它自稱 -
這個遞歸調用返回後，需要做的事情。
所以這個棧幀必須繼續存在，甚至在調用此函數。
然後當你調用這個堆棧幀必須繼續存在
因為即使在這一號召，我們仍然需要進行合併。
它是平凡的，使該尾遞歸。
有問題嗎？
好的。
所以回到排序 - 哦，有兩件事我想告訴。好吧。
進行排序，我們將盡快這樣做。
或搜索。排序？排序。是啊。
讓我們回到了開始的排序。
我們要創建的數組進行排序的算法，該算法使用任何算法
在O的n。
所以，這怎麼可能呢？有沒有人有任何形式的 -
我之前在暗示 -
如果我們要提高n日誌n的n為O，
我們已經改進我們的算法時間上，
這意味著什麼，我們需要做彌補？
[學生]空間。 >>呀。我們將使用更多的空間。
，甚至沒有更多的空間，這是成倍更多的空間。
因此，我認為這種類型的算法是偽的東西，偽多項式 -
偽 - 我不記得了。假的東西。
但是，這是因為我們需要用這麼大的空間
這是可以實現的，但並不現實。
>> 以及我們如何做到這一點？
我們可以做到這一點，如果我們保證，任何特定的數組中的元素
低於一定的大小。
因此，讓我們說，大小為200，
任何數組中的元素是尺寸200以下。
其實這是很不現實的。
你可以很容易有一個數組，你知道它的一切
是小於一些數字。
就像如果你有一些絕對龐大的向量或東西
但你知道一切都將是0和5之間，
那麼它會更快地做到這一點。
，被綁定的任何元件上是5星，
所以這個界，這是你要多少內存使用。
因此，綁定的是200元。
從理論上講，永遠是綁定的，因為一個整數只能為達至4億美元，
但是這是不切實際的，因為那麼我們就可以使用的空間
4億美元的訂單。所以這是不現實的。
但在這裡我們會說，我們的結合是200元。
在O n個這樣做的竅門是我們另一個數組計數的大小約束。
因此，實際上，這是一條捷徑 - 其實我不知道如果鐺做這個。
但在GCC至少是 - 我是假設鐺它太 -
這將初始化整個數組是0。
所以，如果我不想這樣做，那麼我可以分別做為（int i = 0;
我的束縛，我+ +）和計數[I] = 0;
所以，現在一切都被初始化為0。
我重申了我的陣列，
我在做什麼是我清點人數的每一個 - 讓我們去這裡。
我們有4，15，16，50，8，23，42，108。
我的計數是在每個這些元素的出現數目。
讓我們添加一對夫婦在這裡有一些重複。
因此，我們的價值的價值，在這裡，將是陣列[i]。
因此，值可能是4或8或什麼的。
而現在，我計算該值多少我已經看到了，
所以計數[值] + +;
做到這一點後，計數看起來像0001。
讓我們做計數[值] - 約束+ 1。
>> 現在，這只是考慮到這一事實，我們從0開始。
所以，如果200將是我們的最大數量，
0到200是201的東西。
所以，計數，它會看起來像00001，因為我們有一個4。
然後，我們將有0001，我們將有一個在8計數指數。
我們將有一個23指數數2。
我們將有一個42指數數2。
因此，我們可以使用計數。
所以num_of_item =計數[I]。
所以，如果num_of_item為2，這意味著我們要插入2號我
到我們的排序的數組。
因此，我們需要跟踪到數組有多遠，我們是。
所以，索引= 0。
陣列 - 我剛寫出來。
計數 -
數組[索引+ +] =我;
這是我想要的嗎？我想這就是我想要的。
是的，這看起來不錯。好吧。
因此，每個人都明白我的計數數組的目的是什麼？
每個這些數字的出現的數目進行計數。
然後我遍歷，計數數組，
和第i個位置的計數數組中
我是應該出現在我的排序的數組是多少。
這就是為什麼，4的計數將是1
和8的計數將是1，23的計數為2。
因此，這是多少人，我想我排序的數組插入。
然後，我就這樣做。
我插入num_of_item的，我到我的排序的數組。
>> 有問題嗎？
如此反复，這是線性時間，因為我們都只是這一次迭代，
但它也是在這個數字恰好是線性，
，所以它在很大程度上取決於你所綁定的是什麼。
200綁定，這是沒有那麼糟糕。
如果您的綁定將是10,000，那麼這是有點差，
但如果你所綁定的4億美元，這是完全不現實的
這個數組的大小為4億美元，這是不現實的。
所以，就是這樣。有問題嗎？
[聽不見的學生回應] >>好。
我實現了一個其他的事情時，我們會通過。
我認為這個問題是在盧卡斯和可能，我們已經看到的每一個。
我完全忘了。
我唯一​​想評論的是，當你正在處理的事情，比如指數，
你從來沒有真正看到當你寫一個for循環，
但在技術上，只要你處理這些指數，
你幾乎總是要處理無符號整數。
這樣做的原因是，當你正在處理的有符號整數，
所以，如果你有2個有符號整數和你加在一起
他們最終太大，那麼你最終會用負數。
所以，什麼是整數溢出。
>> 如果我增加2億美元和1億美元，我結束了負1億。
這是整數，如何在電腦上工作。
因此，問題與使用 -
這是罰款，除非低恰好為2億美元，高達恰好為1億美元，
那麼這將是負1億美元，然後我們要分2
並最終為負500萬元。
因此，這是一個問題，如果你恰巧是通過一個數組
數十億美元的東西。
但是，如果低+上發生溢出，那麼這是一個問題。
只要我們讓他們無符號，然後是2億加1億美元為3億美元。
3億美元，除以2，為1.5億美元。
因此，只要他們是無符號的，一切都是完美的。
因此，這也是一個問題，當你寫你的for循環，
而實際上，它很可能它會自動。
它實際上只是會罵你的。
因此，如果這個數字是太大而僅僅是一個整數，但它適合在一個無符號整數，
它會罵你的，所以這就是為什麼你從來沒有真正遇到的問題。
你可以看到索引是永遠不會是負的，
因此，如果你要遍歷一個數組，
你幾乎總是可以說無符號整型我，但你真的不有。
事情是去上班幾乎一樣好。
好吧。 [竊竊私語]是什麼時候？
最後一件事，我想向大家展示 - 我就這樣做真快。
你知道我們是如何定義，所以我們可以定義MAX 5或東西嗎？
讓我們不要做最大。的綁定為200。這是我們以前所做的。
定義一個常量，它只是要進行複製和粘貼
發生的地方，我們寫的約束。
>> 所以，我們其實可以做更多的＃define。
＃我們可以定義函數。
他們並不是真正的功能，但我們會打電話給他們的功能。
一個例子是類似的東西MAX（X，Y）被定義為（X <Y Y：X）。好吧。
所以，你應該習慣了三元運算符的語法，
但小於y是x？返回y，否則返回x。
所以你可以看到，你可以使之成為一個獨立的功能，
的功能也能像布爾MAX需要兩個參數，返回。
這是一種最常見的喔做這樣的。我們稱他們為宏。
這是一個宏。
這僅僅是它的語法。
做任何你想要的，你可以寫一個宏。
你經常看到的宏用於調試的printfs之類的東西。
因此，一個類型的輸出，有特殊的類似C中的常​​量強調LINE強調，
2強調LINE強調，
還有還有，我認為強調FUNC。這可能是它。類似的東西。
這些東西將被替換的函數名
或你的行的數目。
通常情況下，你下來，然後我可以在這裡只是寫寫調試的printfs，
調試，它會打印的行數和功能，我恰巧在
它遇到，DEBUG聲明。
您還可以打印其他的事情。
這麼一件事，你應該注意的是，如果我發生的DOUBLE_MAX
像2 * y和2 * X。
因此，無論出於何種原因，你碰巧做了很多。
因此，使它的宏。
這實際上是壞了。
我想請通過做一些像DOUBLE_MAX（3，6）。
那麼應該怎麼回來了？
[學生] 12。
是的，12應該返回，返回12。
3被替換為x，6被替換為y，我們返回2 * 6，這是12。
現在看這個怎麼樣？我們應該回來了嗎？
[學生] 14。 >>理想的情況下，14。
問題是，如何哈希定義的工作，請記住這是一個文字的複製和粘貼
幾乎一切，還等什麼，這是要被理解為
少為3比1加6次，2次加6，2倍，3。
>> 因此，對於這個原因，你幾乎總是包裹在括號中的一切。
你幾乎總是包裹在括號中的任何變量。
在有些情況下，你沒有，就像我不知道我需要做的是在這裡
因為小於的是幾乎總是去上班，
雖然這可能也不是真實的。
如果有什麼可笑的如DOUBLE_MAX（1 == 2），
那麼這將被替換為3小於1等於等於2，
，這樣的話它要小於1，這等於2，
這不是我們想要的。
因此，為了防止任何運算符優先級的問題，
始終包裹在括號中。
好吧。就是這樣，下午5:30。
如果您有任何問題，在pset，讓我們知道。
這應該是有趣的，和黑客版也更為現實
比去年的黑客版，所以我們希望你嘗試了很多。
去年的非常熱烈。
>> [CS50.TV]