[音樂播放] ANDI鵬：歡迎來到第3個星期 謝謝你們，所有的未來 到今天這個較早的開始時間。 我們已經有了一個很好的，小 今天的親密組。 所以希望我們會得到 說完，或許，早， 一點點今天一早。 那麼快，只是一些 今天議程公告。 在我們開始之前，我們 要只走了過來 一些簡單的後勤問題，PSET 題，匯報，這樣的事情。 然後，我們將深入權利英寸 我們將使用一個名為GDB來調試程序 啟動揭穿我們的代碼，大衛 有一天在課堂解釋。 我們就去了四種類型的排序。 我們會去超過他們很快 因為他們非常密集。 但是要知道，所有的幻燈片和 源代碼是永遠在線。 所以感到自由，在你細讀，以 回去看看那個。 我們將通過 漸近符號，這 僅僅是一個奇特的方式 說“運行時間” 在這裡，我們有大O，從而 大衛在演講解釋。 而且我們也有歐米茄，這 是下界運行時。 我們將討論多一點 深入的關於如何將這些工作。 最後，我們就去了二進制搜索， 因為很多你誰已經 看了一眼你的pset便知 這是一個問題，在你的pset中。 所以，你都會很高興 我們管這個今天。 最後，根據您的 部分反饋意見，其實我 在離開約15分鐘 年底剛剛走了過來 pset3物流，如有問題， 也許有點指導，如果你願意， 我們開始編程了。 因此，讓我們試著打通 該材料很快。 然後我們就可以花一些時間 同時為處理器集更多的問題。 確定。 很快，所以只是少數 我們之前宣布從今天開始。 首先，歡迎來製作 它通過兩個你的pset中。 我看了看your--是啊，讓我們 獲得掌聲的那一個。 其實，我是真的， 真的很感動。 我分級的第一個PSET為你們 上週，你們做了令人難以置信的。 風格是在點 除了一些意見。 請確保你總是 註釋你的代碼。 但是，你的pset中都點上。 並保持了起來。 而且它的良好的平地機到 看到你們是把 在你的風格盡可能多的努力 和你在你的代碼設計 我們想給你看。 所以我路過沿著我的謝意 為助教的其餘部分。 然而，有一個 一些匯報的問題 我只是想說明一下 可使兩個我的生活 和許多其它的 助教的生活更容易一點。 首先，我注意到這個 過去week--你們有多少人 已經運行check50 在你的代碼提交？ 確定。 所以每個人都應該做的check50， 因為 - 一個secret--我們實際上 運行check50作為我們的正確性的一部分 腳本測試代碼。 所以，如果你的代碼是失敗的 check50，在所有的可能性， 它可能會 失敗我們檢查為好。 有時候你們 有正確的答案。 像，在貪婪的，一些 你有正確的號碼， 你只需打印出一些額外的東西。 而這額外的東西 實際上未通過檢查， 因為電腦不 真的知道它在尋找。 因此，這將只運行通過， 看到你的輸出不 符合我們所期待的答​​案 要，並註明這是錯誤的。 我知道，發生在 你的一些情況下，這個星期。 所以，我回去和手動 regraded每個人的代碼。 在未來雖然， 請，請確保 你正在運行 在你的代碼檢查50。 因為它是一種為TA疼痛 不得不回去手動再分類 每一個每一個PSET 單，很少錯過實例。 所以，我沒有脫任何積分。 我想，我脫下也許 的一個或兩個用於設計。 在未來雖然，如果 你失敗check50， 點將會採取 關閉正確性。 此外，pset中是 由於週五中午。 我覺得有一個7分鐘 我們給你遲到寬限期。 每哈佛的時候，他們獲准 為7分鐘遲到的一切。 因此，這裡在耶魯，我們將 堅持這一點。 但相當多，在12:07， 如果你的PSET不在， 這將是為後期標記。 因此，雖然它被標記為 為末，TA--我 還是會被分級您的pset。 所以，你仍然會看到一個檔次的出現。 但是，要知道，在 學期結束時， 所有後期的pset將只是 由計算機自動歸零。 我們這樣做有兩個原因。 其中，有時我們得到 原諒，就像院長的藉口， 後來，我不知道呢。 因此，我們希望確保我們分級 一切都為了以防萬一，比如，我 缺少院長的藉口。 其次，要 心中，你仍然可以 摔個PSET的 有完整的範圍點。 因此，我們要分級 所有的pset只是 以確保您的範圍的 那裡，你想他們。 因此，即使是晚了，你還是會 獲得信貸的範圍點，我想。 因此，道德的故事，使 確保你的pset是導通時間。 並且如果它們不是在導通時間， 知道這是不是很大。 是啊，在我繼續前進，沒有任何人有 有關PSET反饋有任何疑問？ 是啊。 聽眾：你是說，我們 可以去掉的pset之一？ ANDI彭：是的。 因此，有九pset中整體 在這學期的課程。 如果你有範圍 points--因此範圍是正義的， 相當多，你嘗試了 問題是，你投入的時間， 你表明你已經 表明您已經閱讀了規範。 這是相當多的範圍。 如果你正在履行 範圍點，我們 可以降最低 一出的全部範圍。 所以這是你的優勢， 完成並想盡一切PSET。 即使upload--如果沒有 他們的工作，快點上傳所有。 然後我們就希望能夠 給你一些這些點回來。 酷。 其他問題嗎？ 太好了。 其次，辦公hours--數 有關辦公時間快速筆記。 因此，首先，走在了本週初。 沒有人是曾經在 辦公時間週一休息。 Christabel來到 昨晚辦公時間。 是啊，Christabel。 和我們有在辦公室什麼 小時昨晚，Christabel？ 聽眾：我們有冰淇淋。 ANDI彭：所以這是正確的，我們有 冰淇淋辦公時間昨晚。 雖然我不能答應你， 我們將有冰淇淋辦公時間 每個星期，我可以向你保證 的是，將有顯著 更好的學生到TA的比例。 像合法的，就好像是三比一。 然而，對比，與 週四你有大約150 真正強調的孩子和沒有冰淇淋。 而且它只是沒有生產任何人。 所以這個故事的寓意是，來得早 在辦公時間，辦好事 會發生。 此外，有備而來提問。 你知道嗎？ 不管什麼助教，我 想，一直在說， 我們已經獲得一對學生情侶 誰在週四進來的一樣，10:50 不看了規範 是一樣幫助我，幫助我。 不幸的是，在這一點上，還有 沒有多少，我們可以做些什麼來幫助你。 所以，請進來本週初。 來得早在辦公時間。 有備而來的提問。 請確保您作為 一個學生，都在那裡 你必須使得 助教可以引導你前進， 這正是辦公時間 應分配的。 其次，所以我知道教授 喜歡我們測試的驚喜。 我有一個教授的 像喲，順便說一下， 請記住，中期 你下週一。 是啊，我不知道是中期。 所以我將是那個TA 提醒大家，測驗 0--因為，你知道，我們是CS。 現在，我們已經做了數組，你會得到 為什麼它的測驗0，沒有測驗1，是嗎？ 確定。 呵呵，我得到了一個有些笑。 確定。 因此，測驗0將是10月14日，如果 你在週一至週三節 而10月15日，如果你在 週二至週四部分。 這不適用於 那些你在哈佛 who--我想你會都是 以14號的測驗。 所以呀，在下週，如果 大衛在演講中，雲， 是啊，所以有關 競猜下週，大家 將不會因為震驚 您來第 你知道你的 測驗0是在兩個星期。 而且我們必須檢討 會議和一切。 所以不愁 被嚇到了點。 如有任何疑問before--任何疑問 在所有有關的後勤問題， 分級，辦公時間，部分？ 是啊。 聽眾：所以小測驗 將要演講期間？ ANDI彭：是的。 所以測驗，我想，是60 分配在時隙分鐘 你會只拿 在報告廳。 所以，你不必進來 上一樣，隨機下午7:00。 這一切都很好。 是啊。 酷。 好的。 所以，我們要 介紹一個概念，你 本週大衛早已種 這個過去一周觸及的講座。 這就是所謂的GDB。 你們有多少人而且，當 寫你的pset的過程中， 已經注意到一個很大的按鈕，上面寫著 在您的IDE頂部的“調試”？ 確定。 所以，現在，我們將真正得到挖掘 其實什麼按鈕的奧秘 確實。 我向你保證，這是一個 美麗的，美麗的東西。 所以到現在為止，我覺得 還有的是兩件事情 學生已通常 調試的pset在做。 一，他們要么加入 printf（）的 - 所以每幾行字， 他們加入一個printf（） - 哦，這是什麼變量？ 哦，這是什麼變量now-- 樣的，你會看到進展 你的代碼，因為它運行。 或者第二種方法孩子們做的是 他們只寫了整個事情 然後轉到這樣在末端。 希望它的工作原理。 我向你保證，GDB更好 比兩者的那些方法。 是啊。 因此，這將是你最好的朋友。 因為它是一個美麗的東西 在視覺上同時顯示 你的代碼做 在特定點 以及所有的你的 變量都在進行， 喜歡什麼他們的價值觀， 在該特定的點。 而這樣一來，你才能真正 設置在代碼中的斷點。 您可以通過一行一行地運行。 和GDB只會有 您，向您顯示， 什麼你所有的變量 是，他們在做什麼， 這是怎麼回事代碼。 並且在這樣的方式，它的 所以更容易看到 發生了什麼的printf的-ING代替 或寫下你的陳述。 所以我們會做後面的一個例子。 因此，這似乎有點抽象。 不用擔心，我們會做的例子。 所以本質上，三個最大的， 最常用的功能，你需要在GDB 是接下來，步過， 而步入按鈕。 我將頭以上 在那裡，其實，就是現在。 所以你們可以都看到， 或者我應該放大一點？ 在後面，你能看到嗎？ 我應該放大？ 只是一點點？ OK，涼。 在那裡，我們走了。 確定。 所以我在這裡，我 實現貪婪。 雖然很多你們的寫 貪婪form--，雖然環 是一種完全可以接受的方式做 它 - 另一種方式來做到這一點是根本 在分模。 因為那樣的話，你可以有你 值，然後讓你的其餘部分。 然後你可以只 加上它一起。 請問對我在做什麼邏輯 這裡是有意義的每一個人， 之前我們開始？ 樣的？ 酷。 太好了。 這是一個非常性感的一塊 的代碼，我會說。 就像我說的，大衛，在 講課，過了一段時間， 你們都開始看到的代碼 作為東西是美麗的。 有時，當你看到漂亮 代碼，它是這樣一個美妙的感覺。 因此然而，儘管這個代碼是非常 美麗的，它不能正常工作。 因此，讓我們在這個運行check50。 檢查50 20--空中接力。 2？ 那是pset2？ 是啊。 哦，PSET1。 確定。 所以我們運行check50。 正如你們所看到的， 它的失敗一對夫婦的案件。 而對於一些你，在 做你的問題集的過程中， 你喜歡啊，為什麼不工作。 為什麼工作一段 值，而不是為別人？ 那麼，GDB是要幫助你的身影 為什麼這些投入並沒有工作。 確定。 所以，讓我們來看看，之一 檢查我是失敗的check50 為0.41的輸入值。 所以正確答案 你應該得到一個4。 而是我所打印出 是3-n中，這是不正確。 因此，讓我們只是手動運行它，只是 確保check50正常工作。 讓我們做./greedy。 哎呀，我一定要貪婪。 在那裡，我們走了。 現在./greedy。 多少錢是欠？ 讓我們做0.41。 而且是的，我們在這裡看到 ，它的輸出3 當正確的答案， 事實上，應為4。 因此，讓我們進入GDB，看看我們如何 可以去解決這個問題。 因此在第一步驟中 一直調試代碼 是設置一個斷點， 或在這一點，你 希望計算機或 調試器開始尋找。 所以，如果你真的不 知道你的問題是什麼， 通常情況下，一般的事情，我們要 做的是設置了斷點為主。 所以，如果你們可以看到這 紅色按鈕就在那裡， 是的，這是我的設置 斷點的主要功能。 我點擊了。 然後我就可以去了我的Debug按鈕。 我打那個按鈕。 讓我放大了，如果我能。 在那裡，我們走了。 因此，我們有，在這裡，在面板上的權利。 我很抱歉，伙計們在後面，你 實在看不出真的很好。 但本質上，所有的 該右側面板做 被跟踪的兩個突出 線，這是代碼行 計算機正在運行， 以及所有的變量 到這裡。 所以，你有美分，硬幣，N， 所有申報不同的東西 在這一點上。 不用擔心，因為我們沒有真正 它們初始化的變量呢。 因此，在你的電腦，你 電腦只是看到， 哦，32767是最後使用的功能 在我的電腦的內存空間。 所以這就是美分是目前。 但是，沒有，一旦運行該代碼， 它應該成為初始化。 因此，讓我們通過，一行 行，這是怎麼回事的。 確定。 所以，在這裡是三個 按鈕，我剛才解釋。 你有玩，或者運行功能， 按鈕，你有步驟結束按鈕， 你也有步驟為按鈕。 並且基本上，所有三個 他們只是通過你的代碼 而做不同的事情。 所以通常情況下，當你正在調試， 我們不希望只是打遊戲， 因為比賽將只運行 你的代碼，它的結束。 然後，你不會真的 知道你的問題 除非你設置多個斷點。 如果設置了多個斷點， 它只是自動 從一個斷點運行， 到下一個，到下一個。 但是，在這種情況下，我們已經 只是那一個，因為我們 希望我們的工作方式 從頂部向下至底部。 所以，我們要忽略按鈕 現在為了這個計劃。 因此，在步函數只是 在每一行的步驟 並告訴您 計算機在做什麼。 該步驟為函數去 到實際的功能 這是對你的代碼行。 因此，例如，如printf（）， 這是一個函數，對不對？ 如果我想在物理上一步 到printf（）函數， 我真的進入片 其中，printf（）的寫，看看代碼 這是怎麼回事那裡。 但通常，我們假設 我們為您提供的代碼工作。 我們假設printf（）的正常工作。 我們假設調用getInt（）的工作。 因此，有沒有必要 走進這些功能。 但是，如果有功能 你寫你自己 要檢查 發生了什麼事情， 你會想一步 入該功能。 所以現在我們只是 跨過這段代碼。 所以，讓我們來看看。 哦，打印，“哦，海，怎麼樣 多大的改變是欠？“ 我們不關心。 我們知道的工作， 所以我們跳過它。 因此n，這是我們的浮動是 我們已經initialized--或declared-- 在頂部，我們現在是 等於說，以GetFloat（）。 因此，讓我們跨過這道。 而我們在看 底部這裡，程序 這促使我輸入一個值。 因此，讓我們輸入我們想要的值 在這裡測試，這是0.41。 太好了。 所以，現在N--做你們看 這裡，在bottom--它的 stored--因為我們 還沒有四捨五入的是，它 存儲在這個像巨大 浮動是0.4099999996， 這是足夠接近我們的 目的，現在，到0.41。 然後，我們將在後​​面看到，因為我們 繼續加強在該程序， 後這裡，正變得 圓潤和分成為41。 太好了。 因此，我們知道，我們的舍入的工作。 我們知道，我們有 正確的數量美分， 所以我們知道，這是 沒有真正的問題。 因此，我們將繼續加強 在此計劃。 我們去這裡。 而這行代碼之後的話，我們 要知道我們有多少個季度有。 我們跳過。 而且你看我們做什麼，其實，有一個 季度，因為我們已經減去25 從41我們的初始值。 我們有16個左右為我們美分。 大家是否明白如何 該程序是通過步進 為什麼美分現已成為16 為什麼，現在，硬幣已經成為1？ 是每個人以下的邏輯是什麼？ 酷。 因此，作為這一點的，在 計劃的工作，對不對？ 我們知道這是做完全 我們希望它。 而我們實際上並沒有 要打印出來，哦， 是仙在這一點上， 什麼是硬幣在此點。 我們將繼續經歷的程序。 步過。 酷。 我們去了助攻。 太好了。 我們看到，它採取 關閉$ 0.10一角錢。 而現在我們有兩個硬幣。 這是正確的。 我們去了幾個便士而我們看到的 我們已經得到了遺留美分。 嗯，這很奇怪。 在這裡，在該程序中，我應該 已減去我便士。 也許我只是沒有 這樣做行權。 唉，你可以看到 在這裡，因為我們知道 我們正在加緊 通過線32和33， 這就是我們的計劃 不當有變量運行。 因此，我們可以看看，看看，哦， 我在這裡減去美分， 但我沒有實際 添加到我的幣值。 我加入到美分。 我不希望添加到 分錢，我要添加到硬幣。 因此，如果我們改變，要硬幣， 我們已經有了一個工作程序。 我可以運行check50。 你可以只退出的GDB右出 這裡，然後再次運行check50。 我可以做到這一點。 我一定要貪婪。 0.41。 而在這裡，它的印刷 出正確的答案。 所以當你們可以看到，GDB 是一個非常強大的工具 當我們有這麼多的代碼 怎麼回事，這麼多的變數 它很難對我們來說，作為 一個人，來跟踪。 計算機，在GDB 調試器，有能力 多事的。 我知道，在VISIONAIRE，你們可能 可能擊中了一些段故障 因為你正在運行 從你的陣列的界限。 在凱撒的例子，這是 正是我在這裡實現。 所以，我忘了檢查 如果會發生什麼，我 沒有兩個命令行參數。 我只是沒有擺在那檢查。 所以，如果我跑Debug--我設置 我的斷點就在這裡。 我運行調試。 確定。 是啊。 所以實際上，GDB應該 已經告訴我， 是分割故障出現。 我不知道發生了什麼事情 在那裡，但是當我運行它， 這是工作。 當您運行通過行代碼 GDB可能只是突然退出你， 上去看看紅色的錯誤是什麼。 它會告訴你的，嘿嘿，你 有段錯誤， 這意味著您嘗試訪問 以陣列的空間不存在的。 是啊。 因此，在接下來的問題 本週集，你們 可能有很多 變量左右浮動。 你不會是知道 它們都是指在某一點。 因此，廣發行將真正幫助你在盤算 它們是什麼都等於 並能夠看到直觀。 有沒有人困惑於如何 任何被工作？ 酷。 好的。 所以在這之後，我們 去潛水權 成四種不同的 排序類型本週。 你們有多少人，第一次 所有的人，在我們開始之前， 讀完整個規範的pset3？ 確定。 我是你們的驕傲。 這就像半個班，這 是顯著超過上一次。 所以，這是偉大的，因為當 我們談論的內容 在lecture--還是遺憾， 在section--我喜歡 以涉及了很多的 回PSET是什麼 你想如何 實現在你的pset中。 所以，如果你來有 讀取規格，它會 是一個更容易讓你明白 我說的是，當我說， 嘿，這可能是一個真正的 實現這種好地方。 所以，你們誰讀了 SPEC知道，作為你的PSET的一部分， 你將不得不 寫一個排序的類型。 所以，這可能是非常有幫助 今天很多你。 因此，我們將剛開始時， 本質上，最簡單類型 排序，選擇排序。 典型的算法 我們怎麼會去這 is--大衛通過這些全都走了進去 講座，所以我會很快待著 這裡 - 本質上，你 有值的數組。 然後你找到 最小的未分類的價值 和你交換與價值 第一個未排序的值。 然後你只是不斷重複 以列表的其餘部分。 而且這裡有一個直觀的解釋 如何將工作。 因此，例如，如果我們開始 與五個元件的陣列，索引 0至4，用3,5，2,6，和4個值 所以，現在擺在array--， 我們只是假設 他們都是未分類 因為我們還沒有測試過，否則。 因此，如何選擇排序會 工作是，那就先 通過整體運行 未排序的數組。 這將挑選出的最小值。 在這種情況下，如圖3所示，右 現在，是最小的。 它得到5。 不，5不大於than-- 或不好意思，不低於than-- 3。 所以最小值仍然3。 然後你到2。 電腦看，哦，2小於3。 2現在必須的最小值。 所以2掉期與第一個值。 因此，人們通過後，我們確實看到 該2和3被交換。 而我們只是要繼續做 這再次與陣列的其餘部分。 因此，我們將只運行通過 最後四個指標的數組。 我們會看到，3 下一最小值。 所以，我們要交換與4。 然後，我們只是要繼續 貫​​穿直到最後，你 得到一個排序的數組中 2，3，4，5，和6被所有排序。 大家是否明白邏輯 如何選擇排序工作？ 你只要有某種 的最小值。 你跟踪的那是什麼。 每當你找到它，你將其交換 與在array--第一值 或者，不是第一value-- 陣列中的下一個值。 酷。 所以當你們那種 從短暫的一瞥看到， 我們要偽代碼這一點。 所以，如果你們在後面要 組成一個小組，每個人都在一張桌子 可以形成一個小夥伴，我要去 給你們喜歡3分鐘 剛才講通過 邏輯，英語， 對我們如何能夠實現 偽代碼寫一個選擇排序。 還有的糖果。 請上來，並得到糖果。 如果你在後面，你想 糖果，我會向你扔糖果。 其實，做你 - 爽。 哦，對不起。 確定。 所以，如果我們想，作為 一類，寫偽代碼 如何人們可能接近 這個問題，只是覺得自由。 我就到處去和， 為了，問群體 對於下一行 我們應該做的。 所以，如果你們想開始 關，什麼是第一件事情 當你試圖做 實現的方式來解決這個方案 有選擇地排序列表？ 讓我們只是假設我們 有一個數組，沒事吧？ 聽眾：你想創造一些 排序[聽不清]你是 通過你的整個陣列的運行。 ANDI彭：對。 所以，你會想迭代 通過每一個空間，對不對？ 所以，偉大的。 如果你們想給我 接下來line--是啊，在後面。 聽眾：檢查他們 全部為最小。 ANDI彭：我們去那裡。 因此，我們希望通過和檢查 看到最小值是什麼，對不對？ 我要縮寫，為“最小”。 你們有什麼想後做 你已經找到了最小值？ 聽眾：[聽不清] ANDI彭：所以你會想 與第一個數組中打開它， 對不對？ 這是開始的時候，我會說。 好的。 所以，現在你已經換第一 一，什麼你想以後做什麼？ 所以，現在我們知道，這一個在這裡 必須是最小的值，對不對？ 然後，你有一個額外的休息 該陣列是無序的。 所以，你想在這裡做的，如果你有什麼 人想給我的下一行？ 聽眾：那麼接下來你要遍歷 通過該陣列的剩餘部分。 ANDI彭：是的。 還等什麼，通過它遍歷 那種暗示我們可能會需要什麼？ 什麼類型的of-- 聽眾：哦，一個額外的變量？ ANDI彭：可能 另一個循環，對不對？ 因此，我們可能會想 迭代through--很大。 然後，你要回去 可能再次檢查最低， 對不對？ 而你要不斷重複 這一點，因為環正要 繼續運行，對吧？ 所以當你們可以看到，我們 只是有一個大致的偽代碼 我們如何希望這個節目的樣子。 這裡這個迭代，我們怎麼 通常需要在我們的代碼編寫 如果我們要遍歷一個 陣列，什麼類型的結構？ 我想Christabel 之前已經說過這​​一點。 聽眾：for循環。 ANDI彭：一種循環？ 沒錯。 因此，這可能是 將是一個for循環。 什麼是這裡的檢查會意味著什麼呢？ 通常情況下，如果你想查詢 如果有什麼東西else-- 聽眾：如果。 ANDI彭：如果一個，對不對？ 然後在這裡交換，我們將 去了以後，因為大衛· 通過講座去為好。 然後第二個迭代implies-- 聽眾：另一個循環。 ANDI彭：--another for循環，沒錯。 因此，如果我們正在尋找 在這個正確的，我們 可以看到，我們可能 將需要一個嵌套的循環 在有一個條件語句 然後代碼的一個實際的一塊是 要交換值。 所以，我只是一般寫 這裡一個偽代碼。 然後，我們實際上會 到身體上，作為一類， 試試這個今天實現。 讓我們回到這個IDE。 嗯，哦。 這是為什麼不是 - 它就在那裡。 確定。 對不起，讓我盡量放大一點。 在那裡，我們走了。 我做的是在這裡我創建 一個名為“選擇/ sort.c。” 我創建了九個數組 值，4，8 2，1，6,9，7,5，3。 目前，你可以 看，他們是無序的。 n為將成為數 告訴你值量 你在你的陣列。 在這種情況下，我們有九個值。 我剛剛得到了一個for循環在這裡 打印出的排序的數組。 而在最後，我也得到了一個為 循環，只是打印出來了。 因此從理論上說，如果此程序 工作正常，到了最後， 你應該看到一個打印的循環 其中，1，2，3，4，5，6，7，8， 9都是正確的順序。 所以，我們在這裡得到了我們的偽代碼。 有誰想用於：我只是 要去問volunteers-- 確切地告訴我，如果什麼類型 我們希望，第一，只是想迭代 通過這個數組的開始？ 什麼是代碼行我 可能要在這裡需要什麼？ 聽眾：[聽不清] ANDI彭：是啊，感覺 免費用於：對不起，你 不必忍受up--手感 自由地提高你的聲音有點。 顧客：INT I等於0-- ANDI彭：是的，不錯。 觀眾：我是小於數組的長度。 ANDI彭：因此，保持在 介意在這裡，因為我們 不具有功能 告訴我們的陣列的長度， 我們已經有一個 值，其存儲。 對嗎？ 另一件讓 在mind--以陣列 九價值觀，有什麼指標？ 遠的不說這個數組是0至3。 你看，最後 指數實際上是3。 這不是4，即使有 陣列中的四個值。 所以在這裡，我們必須非常小心， 什麼我們條件的長度 將是。 聽眾：那豈不是為n減去1？ ANDI彭：這是怎麼回事 Ñ​​減去1，正好。 這是否有意義，為什麼 它n值減1，每個人？ 這是因為數組是零索引。 他們從0開始並運行最多n個減1。 是的，這是一個有點棘手。 確定。 而then-- 聽眾：Isnt'1那 已經採取的雖然照顧， 通過剛才不是說“小於或 等於“，只是說：”不到？“ ANDI彭：這是一個 非常好的問題。 所以，是的。 而且，我們的方式是說 實施檢查權， 你需要比較兩個值。 所以，你真的想 離開“到”空。 因為如果你比較 這一次，你不會 有後什麼 要比較的，對不對？ 是啊。 所以我++。 讓我們添加括號研究。 哎呦。 太好了。 因此，我們有初 我們的外環。 所以，現在我們可能要 建立保持一個變量 軌道的最小值，對不對？ 沒有人想給我 行代碼，將做到這一點？ 我們需要什麼，如果我們打算 想儲存什麼？ 右。 對於也許一個更好的名字 將be--“臨時”完全works-- 也許更恰當地命名會是這樣， 如果我們希望最小value-- 聽眾：最小。 ANDI彭：分鐘，我們走吧。 分將是一件好事。 所以在這裡，我們怎麼 要初始化為？ 這是一個有點棘手。 因為現在在 開始本陣， 你有沒有看什麼，對不對？ 還等什麼，自動，如果 我們只是i等於0， 我們怎麼想初始化 我們的第一個最小值？ 觀眾：我。 ANDI彭：我，沒錯。 Christabel，那我們為什麼還要 它初始化到我？ 聽眾：因為， 我們從0開始。 所以，因為我們沒有什麼可比較 它，最小最終會被0。 ANDI鵬：沒錯。 所以她完全正確。 因為我們還沒有真正 看著任何東西， 我們不知道我們的最低值。 我們希望只是將其初始化為 我，這，目前，就在這裡。 而且，我們將繼續 向下移動，這陣， 我們將看到，每個 額外的傳球，我遞增。 因此，在這一點上， 我很可能會 想為最小， 因為這將是什麼 是未排序數組的開始。 酷。 所以，現在我們要添加 一個for循環，這裡的 要遍歷 未分類，或該陣列的其餘部分。 沒有人想給我一個 行代碼，將做到這一點？ Hint--我們需要什麼到這裡？ 這是怎麼回事往這個循環？ 是啊。 聽眾：所以我們會想 有一個不同的整數， 因為我們通過休息運行 數組，而不是我，所以也許對 學家 ANDI彭：是啊，J聽起來不錯。 等於？ 聽眾：那將是我加1，因為 你開始的下一個值。 然後到end--如此反复，j為 小於n減去1，然後J ++以下。 ANDI彭：太好了。 然後在這裡，我們將要 檢查，看看是否符合我們的條件， 對不對？ 因為你想 改變的最小值 如果它實際上是小於什麼 你對比的話，對不對？ 那麼，我們將要在這裡？ 請檢查。 聲明什麼類型 我們有可能將 TI想，如果用我們 要檢查些什麼呢？ 聽眾：if語句。 ANDI彭：if語句。 所以if--，什麼將是 我們希望裡面的狀況 我們的if語句？ 聽眾：如果j值 小於I--值 ANDI鵬：沒錯。 所以if--所以這個數組被稱為“數組”。 太好了。 因此，如果array--那是什麼？ 再說了。 聽眾：如果array-j是小於 數組我的話，就要改變最小。 所以分鐘就學家 ANDI彭：這是否有意義嗎？ 確定。 而現在到這裡，我們其實 要實現交換，對不對？ 所以記得，在演講中，大衛，當 他是想換the--是什麼 它 - 橙汁和milk-- 聽眾：這是毛。 ANDI彭：是啊，這是種毛。 但它是一個相當不錯的 概念展示時間。 因此，認為你的價值在這裡。 你有一個數組 的分，i的陣列， 或不管我們想在這裡交換。 而且你可能無法將其倒入 對方在同一時間，對吧？ 那麼究竟是為了什麼 需要創建在這裡 為了正確交換價值？ 聽眾：一個臨時變量。 ANDI彭：一個臨時變量。 因此，讓我們做INT溫度。 你看，這將是一個更好的 時間用於：哇，那是什麼？ 確定。 因此，這將是一個更好的 時間命名變量“溫度”。 因此，讓我們做INT溫度。 什麼是我們要 SET TEMP等於在這裡？ 聽眾：最小？ ANDI彭：這是一個有點棘手。 它實際上無所謂到底。 它什麼都無所謂 為了您選擇交換 只要你確保你 跟踪你交換什麼。 聽眾：這可能是數組我。 ANDI彭：是的，讓我們做陣列我。 然後什麼是下一行 的代碼，我們要在這裡？ 聽眾：陣列-i等於陣列-J。 ANDI彭：最後一點？ 聽眾：陣列-J等於陣列我。 聽眾：或數組，j為 陣列temp--或溫度。 ANDI彭：OK。 因此，讓我們運行這個，看看 如果它去上班。 哪裡是怎麼回事？ 哦，這是一個問題。 見，第40行，我們 嘗試使用數組-J？ 但是，在沒有Ĵ只存在嗎？ 聽眾：在for循環。 ANDI彭：對。 那麼，我們將需要做什麼？ 聽眾：外the--將其定義 聽眾：是的，我想你 if語句，使用權的另一個？ 所以像，如果minimum-- 好吧，讓我想想。 ANDI彭：伙計們，試試 看看咱們的 看看，什麼的東西，我們可以在這裡做什麼？ 聽眾：OK。 因此，如果最低不等於 j--所以如果最小仍然I-- 那麼我們就不會掉。 ANDI彭：這是否等於我？ 你怎麼在這裡想說的？ 聽眾：或者是啊，如果 最低不等於我，是的。 ANDI彭：OK。 好了，解決了，那種，我們的問題。 但是，這仍然沒有解決 如果j--發生，因為Ĵ哪些問題 外面它不存在，什麼 你，我們想用它做？ 外部聲明呢？ 讓我們嘗試運行此。 嗯，哦。 我們的排序不工作。 正如你所看到的，我們最初的 數組有這些值。 事後它應該有 一直在1，2，3，4，5，6，7，8，9。 它不工作。 啊。 我們該怎麼辦？ 聽眾：調試。 ANDI鵬：好的，我們可以試試。 我們可以調試。 縮小了一點。 讓我們設置的斷點。 讓我們去like--確定。 所以，因為我們已經知道， 這些線路，15至22， 在working--因為我做的是 通過與printing--只是迭代 我可以繼續跳過。 讓我們從第25行。 空中接力，讓我擺脫這一點。 聽眾：所以斷點的 其中，調試開始？ ANDI彭：或停止。 聽眾：或停止。 ANDI彭：是的。 您可以設置多個斷點和 它可以只從一個到另一個跳。 但是，在這種情況下，我們不知道 那裡的錯誤發生。 所以，我們只是想 從上向下展開。 是的。 確定。 因此，這條線在這裡，我們可以介入。 你可以看到這兒， 我們已經有了一個數組。 這些都是價值 是陣列中。 你看到了，怎麼指數為0， 對應於value--哦， 我要去嘗試進行放大。 對不起，這真的很難 以see--數組索引0， 我們有4的值， 然後依此類推等等。 我們有自己的局部變量。 現在我等於 0，這是我們希望它是。 因此，讓我們繼續單步調​​試。 我們的最低等於0， 我們也希望它是。 然後，我們進入我們的第二個用於 環，如果陣列-j是小於陣列-i的， 它不是。 所以，你怎麼看 即跳過了嗎？ 聽眾：所以要把如果 最低，所有that--不應該的 在裡面的第一個for循環？ ANDI彭：沒有，因為 你還是想測試。 你想要做一個比較每 時間，即使你通過它運行。 你不只是想這樣做 在第一通過。 你想做到這一點的 再每增加一個通行證。 所以，你要檢查 你的病情裡面。 所以，我們只是要 讓經過這裡運行。 我給你們一個提示。 它必須做的事實是，當 你檢查你的條件， 你不檢查 正確的索引。 所以現在你檢查 殲數組索引小於陣列 我索引。 但是，你在做什麼了，在 for循環的開始？ 難道你不設置Ĵ等於我？ 是啊，所以我們實際上可以 退出調試器在這裡。 因此，讓我們來看看我們的偽代碼。 For--我們要 開始我等於0。 我們要上浮到n減去1。 讓我們來看看，沒我們有這個權利？ 是的，這是正確的。 因此，然後在裡面在這裡，我們 要創建一個最小值 並設置等於i。 難道我們這樣做嗎？ 是的，這樣做。 現在，在我們內心的for循環中，我們 要做到j為我到n減去1。 難道我們這樣做嗎？ 事實上，我們做到了。 所以，不管，什麼是我們比較嗎？ 聽眾：J-加1。 ANDI鵬：沒錯。 然後你會想設置 您的最低等於到j加1為好。 所以，我通過真的很快去了。 難道你們明白 為什麼它的殲加1？ 確定。 因此，在你的陣列，在 你的第一個闖關， 你的for循環，對於int i等於0，我們只 假設這並沒有改變呢。 我們的陣列，完全， 短短四年未排序的元素，對不對？ 因此，我們要初始化i等於0。 而我是要只 通過這個循環運行。 因此在第一輪，我們要 初始化一個名為“分”變 這也等於我，因為 我們沒有一個最小值。 所以這是當前等於0為好。 然後，我們將經歷。 我們想再次重複。 現在我們已經找到了我們的最低 是，我們要遍歷 再看看它的比較，對不對？ 所以Ĵ，在這裡，是怎麼回事 等於I，這是0。 然後，如果陣列Ĵ再加上我，這 就是一個​​是下完了，一樣都不能少 比你目前的最低 值，要交換。 所以，讓我們只說我們已經 有，像，2，5，1，8。 現在，我等於 0和j是等於0。 這就是我們的最低值。 如果陣列-j的加I--因此如果所述一個 這就是我們正在尋找在一前一後 大於前一， 這將成為最低。 所以在這裡我們可以看到，5 是不遜色。 因此，這將不會是5。 我們看到，1小於2，對不對？ 所以，現在我們知道，我們的最低是 將是0，1，2的指數值。 是嗎？ 然後當你到這裡， 你可以交換正確的價值觀。 所以，當你們剛剛有第j 之前，你是不是在看一 後。 你在看 相同的值，這 就是為什麼它只是沒有做任何事情。 這是否有意義給大家， 為什麼我們需要一個加1呢？ 確定。 現在，讓我們只運行通過它來作 確認代碼的其餘部分是正確的。 這是為什麼發生？ 啊，這是分就在這裡。 我們比較了錯誤的值。 哦，不。 哦，是的，在這兒我們 交換了錯誤的值也是如此。 因為我們在看i和j。 這些都是那些我們被檢查。 事實上，我們希望交換的 至少，目前最低， 與任何一個外面。 正如你們所看到下跌 在這裡，我們有一個排序的數組。 這只是不得不做 事實，當 我們被檢查 值的我們相比， 我們不看正確的價值觀。 我們在看的同一個 在這裡，沒有實際交換它。 你要看看一個接一個 它，然後你可以交換。 所以，這是什麼樣的 前纏著我們的代碼。 而我在這裡所做的一切 調試器可以為你做 我只是做了它的 板，因為它更容易 看而不是試圖 可放大的調試器。 這是否有意義給大家？ 酷。 好的。 我們可以繼續談 漸近符號，這 是說的只是一種奇特的方式 所有這些各種各樣的運行時間。 所以我知道大衛在演講中， 在運行時感動。 他走遍了整個公式 如何計算的運行時。 關於無後顧之憂。 如果你真的很好奇 其工作原理， 隨時節後跟我說話。 我們可以穿行 公式在一起。 但是，所有你們要真 知道是n的平方超過2 是同樣的事情為N的平方。 因為最大數目， 該指數增長最。 所以我們的目的， 我們關心的 是巨大的數量也在不斷增長。 那麼，什麼是最好的情況下， 選擇排序的運行時間？ 如果你想有 遍歷列表 然後遍歷 該列表的其餘部分， 多少次都 你要大概， 在最壞的case--在 最好的情況下，sorry--跑過來嗎？ 也許更好的問題是 要問，什麼是最壞的情況下 運行時選擇排序的。 聽眾：N的平方。 ANDI彭：這n值的平方，正確的。 因此，一個簡單的方法來認為這是喜歡， 任何時候你有兩個嵌套的for循環， 它會為n的平方。 因為不僅是你 通過再次運行， 你要回去 周圍，並通過它運行 裡面的每一個值一次。 因此，在這種情況下，你在行駛中N n次平方，這is--抱歉， n次N，這等於N的平方。 和排序也有點 在這個意義上獨特 它不如果這些關係 值已經在秩序。 它仍然會通過反正運行。 遠的不說，這是1，2，3，4。 不管它是否是在 命令，它仍然會通過跑 並且仍然檢查的最小值。 它會作出 檢查相同數量的 每一次，即使它 實際上並沒有碰任何東西。 因此，在這樣的情況下，最好和最差 運行時實際上是等價的。 因此，預計運行時間 選擇排序的， 這是我們指定的符號 的θ，θ-，在這種情況下， 還將為n的平方。 所有這三個為N的平方。 是為什麼每個人都清楚 運行時間為n的平方？ 好的。 所以我只是要快速運行 通過對各種休息。 該算法 泡泡類別 - 記住， 這是第一個 大衛走過去的講座。 從本質上講，你一步 整個列表 你剛才swap--你 同時比較兩個。 而如果一個人的更大， 比你只是換他們。 因此，如果這些是更大的，你就掉。 我已經得到了官方的就在這裡。 因此，讓我們只說你有8個，6個，4個，2。 你會比較8和6。 你需要交換它們。 您會比較8和4。 你需要交換它們。 如果您有交換8 2，改變他們。 因此，在這樣的意義上，你可以看到， 發揮出了相當長的時間週期， 怎麼樣值泡沫來 兩端，這就是為什麼我們叫它 冒泡排序。 我們只想上運行再次通過 我們的二傳，而我們的第三關， 而我們的第四個階段。 從本質上講，冒泡排序只是運行 直到你不作任何更多的互換。 因此，在這個意義上，這僅僅是 一般偽它。 不用擔心，這些都將在網上。 我們沒有真正去了這一點。 我們只是初始化一個計數器 從0開始的變量。 而我們通過整個數組迭代。 如果一個值is--如果這 值大於該值， 你要交換它們。 然後，你只是 要繼續下去。 而你要算。 而你只是要繼續做 這同時計數器的值大 大於0，這意味著 每次你要交換， 你知道你想要去 回去檢查一次。 你要繼續檢查，直到你知道 你不必換了。 那麼，什麼是最好的和最差 情況下的運行時間冒泡排序？ 這hint--實際上是不同的 從某種意義上選擇排序 這兩個答案是不一樣的。 想想會發生什麼 的情況下，如果它已經被排序。 想想什麼 如果它是會發生 在的情況下在它被排序。 你可以種運行 通過為什麼會發生的事情。 我給你們一樣，30 秒，想想。 確定。 是否有人在猜測什麼 冒泡排序的最壞情況下的運行時間是？ 是啊。 聽眾：會是一樣，n次 ñ減1或類似的東西？ 像，每次運行時， 它只是一樣，一個交換少 這不管是什麼。 ANDI彭：是啊，所以 你是完全正確的。 這是在這種情況下你 答案竟是更複雜 比我們需要給。 因此，這將run--我 要刪除這一切都在這裡。 是每個人都好？ 我能抹去嗎？ 確定。 你會到n運行 第一次時間，對吧？ 他們正在經歷的運行 Ñ​​減去1秒的時間，對吧？ 然後，你要保持 去，N礦2，等等。 大衛這樣做的講座，其中， 如果你加起來所有的值， 你得到的東西，是like-- yeah-- 超過2，這本質上只是減少 下降到n的平方。 你會得到一個 怪異的部分在裡面。 所以只要知道 第n總是平方 優先於分數。 因此在這種情況下，最壞的 運行時間為N的平方。 如果它是在降 順序，想想，你 不得不做出交換每一次。 什麼是潛在的， 最好的情況下運行？ 這麼說吧，如果列表已經 為了，你會在運行時？ 聽眾：N。 ANDI彭：這是N，正好。 為什麼是這N + 聽眾：因為你剛才 必須檢查每一次。 ANDI鵬：沒錯。 因此，在可能的最佳運行時， 如果此列表中已經 sorted--比方說，1，2，3，4--您 只想去實現它，你會檢查， 你會看到，哦，他們都做成。 我沒得換。 我完成了。 因此，在這種情況下，它僅僅局限於N 或步數，你只是 不得不檢查的第一個列表。 及後，我們現在打 插入排序，其中， 該算法本質上是鴻溝 它變成一個排序和未排序的部分。 然後一個接一個， 未排序值 在其相應插 在列表的開頭位置。 因此，例如，我們有一個 的3名單，5,2，6,4試。 我們知道，這是目前 未分類的，因為我們剛剛 開始尋找它。 我們來看看，我們知道， 第一個值進行排序，對吧？ 如果你只關注一個數組 尺寸之一，你知道它的排序。 於是我們知道， 其他四個都是無序。 我們通過和我們看到的價值。 讓我們回去。 見5的價值？ 我們來看看它。 我們把它比作3。 我們知道，它是大於 3，讓我們知道，多數民眾贊成排序。 所以，現在我們知道，前兩個 進行排序和最後三個不是。 我們來看看2。 我們首先檢查一下與5。 是小於5？ 事實並非如此。 因此，我們必須繼續找下去。 然後檢查2關閉3。 是小於？ 第 所以，你知道2必須插入 入前和3和5 都必須被推出。 6和4再次做到這一點。 我們只是保持檢查從本質上講， 在這裡我們只是檢查，檢查，檢查。 而直到它在正確的 樣的位置，我們只是 將其插入合適的位置， 這就是它的名字是從哪裡來的。 所以，這僅僅是算法， 那種偽代碼本身， 關於我們如何實現 插入排序。 偽代碼是在這裡。 這一切都在網上。 不，如果你們有隱憂 試圖複製下來。 所以再次，相同的問題 - 是什麼 將是最好的和最差的運行時間 插入排序？ 這是非常相似的最後一個問題。 我給你們一樣，30 秒想想這一點。 確定有沒有人要 給我最糟糕的運行？ 是啊。 聽眾：N的平方。 ANDI彭：這n值的平方。 為什麼它Ñ平方？ 聽眾：因為在 相反的順序，你有 要經過n次N，其中is-- ANDI彭：是的，沒錯。 所以，同樣的事情在冒泡排序。 如果此列表中 降序排列，你 不得不先檢查一次。 然後每 額外的價值，你 將不得不對檢查 每一個值，對不對？ 所以乾脆，你會做 正通時代另外N通，這 為n的平方。 那麼最好的情況？ 是啊。 聽眾：N減1，因為 第一個是已經平方。 ANDI彭：那麼，關閉。 其實答案ñ。 因為當第一個是 排序，也可以不actually--它 我們只是走運了，在 即例如，2 正好是最小的數目。 但是，這不會總是這種情況。 如果2已經排序的開始 但是你看，有一個1在這裡， 1將要碰撞。 而這將結束 最多被撞毀反正。 因此，在最好的情況下， 它實際上只是要為n。 如果有1個，2個，3個， 4，5，6，7，8，你 經過運行 這整個列表一次 檢查，如果一切都很好看。 在其上運行大家清楚 選擇的時候呢？ 我知道我經歷 這些真快。 但是，僅僅知道，如果你知道 一般概念，您應該不錯。 確定。 所以，我只是給你們也許一樣， 一分鐘談談你的鄰居 什麼都只是一些 的主要區別 與這些類型的排序。 我們一起去了很快。 聽眾：哦，好。 ANDI彭：是的。 確定。 酷，讓我們重新召集的一類。 確定。 所以，這是一種一 在這個意義上開放式的問題 這有很多他​​們的答案的。 我們將介紹一些他們的簡要介紹。 我只想讓你們 思考什麼區別 這三種類型的排序。 而且我聽說，也有很大 的問題 - 是什麼歸併排序呢？ 大的問題，因為這是 我們正在覆蓋下一個。 所以，歸併排序是 一個分類的功能 非常不同於其他種類。 正如你們可以see-- David是不是做演示 在那裡，他把所有的酷 看到如何合併的聲音 排序跑了一樣，無限 比其他兩種類型的快？ 確定。 所以，這是因為合併 排序實現了鴻溝 而治之的概念，我們已經 談到了很多在課堂上。 在這個意義上，我們喜歡的工作 更聰明，而不是更辛苦，當你把 而治之的問題，並打破他們 下來，然後把它們放在一起， 美好的事物總是發生。 這樣合併的方式 排序基本工作原理 是，它把一個 無序陣列中的一半。 然後它有陣列的兩半。 它只是排序那些兩半。 它只是保持在半分，在 一半，一半，直到萬事俱備 然後遞歸 把他們放在一起。 這就是真正的抽象。 所以，這只是一個有點偽的。 這是否有意義的 它的運行方式？ 因此，讓我們只說你有一個 n個元素的數組，對不對？ 如果n小於2，可以退貨。 因為你知道，如果有 只有一件事，它必須被排序。 否則，你排序左前衛， 然後排序的右半​​部分， 然後合併。 因此，雖然看起來很容易， 在現實中，思考它的 樣的困難。因為你喜歡， 嗯，這是運行的一種自身。 對嗎？ 它本身運行。 因此，在這個意義上，大衛·感動 在遞歸類。 這是一個概念 我們將談論更多。 那就是這一點，這兩條線 在這裡，其實只是節目 告訴它運行本身 與不同的輸入。 因此，而不是與運行本身 n個元素的全部， 你可以把它分解成的 左半部和右半 然後再運行它。 然後我們來看看它在視覺上， 因為我是一個視覺學習者。 它為我好。 所以，我們來看看一個可視化的例子在這裡。 比方說，我們有一個數組，六 元素，3，5，2,6，4,1，不進行排序。 好吧，有很多這個頁面上。 所以，如果你們可以看看 這裡第一步驟中，3，5，2,6，4,1， 您可以在一半分裂它。 您有3個，5個，2，6,4，1。 你知道這些aren't--您 不知道他們正在排序或沒有， 所以你把它們分解，在上半年， 成兩半，一半，直至最後， 你只有一個元素。 而一個元素總是排序，對吧？ 因此，我們知道，3，5，2，4，6， 1，由本身，進行排序。 現在，我們可以把他們重新走到一起。 因此，我們知道的3,5。 我們把這些在一起。 我們知道這是排序。 2.仍然存在。 我們可以把4和6一起。 我們知道，多數民眾贊成排序， 所以我們這身打扮。 而1是存在的。 然後你只要看看 這兩個半就在這裡。 你有3,5，2，2，3，5。 你可以只比較 開始的一切。 因為你知道，這是排序 你知道，多數民眾贊成排序。 所以，那麼你甚至沒有給 對比5，你只要比較一下3。 和2小於3，所以 你知道2必須走到底。 同樣的事情在那邊。 1.必須在這裡。 然後，當你去把 這兩個值加在一起， 你知道，這是分類和 你知道這是排序。 於是在1和 圖2中，1是小於2。 這告訴你，1 應該在本月底 看也不看3或5。 然後是4，你可以 檢查，它會就在這裡。 你不必看5。 同樣的事情在6。 你知道6--它只是 並不需要研究。 所以這樣一來，你是 只是拯救自己 很多步驟，當你比較。 你不必比較每 元素與其他元素。 你只是比較反對的人 你需要將它與比較。 所以這是一種抽象的概念。 不用擔心，如果它不是 相當擊中你的權利呢。 但是總體來說，這是 如何合併排序工作。 問題，簡單的問題， 之前，我繼續前進？ 是啊。 聽眾：所以你說，你拿 1，然後在4和6 並把他們進來。 所以不those--不 你看他們 作為單獨的元素，而不是整？ ANDI彭：是的。 所以發生了什麼 是，你基本上 正在創造一個全新的陣列。 所以，你知道，在這裡，我有 尺寸3的兩個數組，對不對？ 所以，你知道，我的排序的數組 需要有六個要素。 所以，你只要創建一個 新的內存量。 所以，你是那種喜​​歡 被浪費的存儲器， 但是，這並不重要 因為它是如此之小。 所以，你看1 你看2。 而你知道，1小於2。 所以，你知道，1應該在 所有這些的開始。 你甚至都不需要 看3和5。 所以，你知道1去那裡。 然後，你基本上砍掉1。 這是一樣，死了我們。 然後，我們只是有2個， 3，5，然後4和6。 然後你知道，你 比較4和2， 呵呵，2應該在那裡。 所以，你撲通2下來，你砍了下來。 所以，那麼你只需要3 和5中的4個和6個。 而你只是不斷砍它關閉 直到你把他們到數組中。 聽眾：所以，你只是總是 比較[聽不清]？ ANDI鵬：沒錯。 因此，在這個意義上說，你是 只是相比較，從本質上講， 一個號碼對另一個號碼。 而且因為你知道 ，它的排序， 不必翻閱 所有的數值。 你只需要看看第一個。 然後你可以撲通 下來，因為你知道 他們屬於他們需要屬於。 是啊。 好問題。 然後，如果哪 有點雄心勃勃， 隨意看看這段代碼。 這實際上是 物理實現 我們如何會寫歸併排序。 你可以看到，這是非常短的。 但背後的想法 這是相當複雜的。 所以，如果你覺得自己畫了這一點 在你的功課今晚，隨意。 確定。 大衛也去了這個講座。 什麼是最好的情況下， 運行時，最壞的情況下運行時， 和合併排序的預計運行時間？ 幾秒鐘思考。 這是相當困難的，但那種 直觀的，如果你仔細想想。 好的。 聽眾：是最壞的情況的n log N + ANDI鵬：沒錯。 為什麼說它是N日誌ñ。 聽眾：是不是因為它 成為指數更快， 因此它就像一個函數 而不只是單純的為N 平方什麼？ ANDI鵬：沒錯。 這樣之所以 運行時在此為n日誌 n是因為 - 你是什麼人 在做所有這些步驟？ 你只是砍了一半，對不對？ 所以，當我們正在做的 日誌，所有它做 被分割的問題在一半， 成兩半，一半，在更半部。 而在這個意義上，可以種 對消除線性模型 我們一直在使用。 因為當你砍 事情的一半，這是一個記錄。 這只是數學 代表它的方式。 然後終於，到了最後，你 只是讓通過一個最後一關 把所有的人都在秩序，對不對？ 所以，如果你只需要 查一件事，那n值。 所以你是那種 乘兩者結合起來。 因此，這就像你已經得到了最終的 檢驗N-下來日誌的n這裡 在這裡。 如果你乘 他們，那是N日誌ñ。 所以，最好的和最壞 情況和預期是所有N日誌N。 它也像另一個排序。 這就像選擇排序 在某種意義上說，它 不要緊，你的 列表，它只是會 做同樣的事情，每一次。 確定。 所以當你們可以看到，即使 我們已經走了through-- n中的種種 平方，這不是很有效。 而即使是這樣的n log n是 不是最有效的。 如果你們是好奇， 有某種機制 這是如此有效，以至於他們 幾乎是基本持平的運行時間。 你有一些日誌ñ的。 你有一些loglogN個的。 我們不觸及他們 在這個類現在。 但是，如果你們是好奇， 隨意谷歌，什麼是 最有效的分類機制。 我不知道，有 一些很搞笑的人， like--有一些真的 有趣的那些人做。 你想知道他們是如何 沒有想過這一點。 因此谷歌，如果你有一些空閒 時間上，都有些什麼有趣的方式 該people--以及 高效ways--人 之所以能夠實現排序。 確定。 而這裡只是一個方便的小圖。 我知道在座的各位，是競猜0之前， 會在你的房間可能是試圖 記住這一點。 所以這是很好的在那裡為你們。 但不要忘記，made--邏輯 為什麼這些數字正在發生。 如果你總是輸了，只是讓 確保你知道什麼是排序是。 你可以貫穿 它們在你的心中 弄清楚為什麼那些 答案是這些問題的答案。 好的。 所以，我們要動 在最後，在搜索。 因為那些對你 誰看過處理器集， 搜索也是部分 這個星期的習題集。 你會被要求執行 兩種類型的搜索。 一個是線性搜索和 一個是一個二進制搜索。 所以線性搜索是相當容易的。 你只是想搜索的元素 列表，看看你得到它。 你只需要遍歷。 如果它等於什麼， 你可以返回它，對嗎？ 但是，一個我們最 興趣談論 是二進制搜索，右，這是 分而治之的機制， 大衛被證明在講座。 還記得電話簿的例子 他不斷拉扯大， 一個那種他掙扎 有點過去的一年， 在那裡你把這個問題了一半， 一半，一半，一遍又一遍， 直到你找到你想要的？ 而你已經得到了 那運行時也是如此。 你可以看到，它的 顯著更高效 比任何其他類型的搜索。 所以我們會去的方式 實現的二進制搜索 是，如果我們有一個數組， 索引為0到6，7的元素， 我們可以看看在中間，right-- 很抱歉，如果我們的問題first-- 如果我們要問的問題，請問 該陣列含有的7的元件， 顯然，是人類，並且具有 這樣一小陣，很容易讓我們 說是。 但方式來實現二進制 搜索將是尋找在中間。 我們知道，指數3 中間，因為我們 知道有七個要素。 什麼7除以2？ 你可以額外1砍掉。 你在中間得到了3。 所以為3數組等於7？ 它是不是，對不對？ 但是，我們可以做一對夫婦的檢查。 是3小於7或陣列 是3陣列大於7？ 我們知道，這是不到7。 因此，我們知道，哦，就必須 不會在左半部。 我們知道，它必須是 在右前衛，對不對？ 因此，我們可以只砍掉一半的陣列。 我們甚至不有 看它了。 因為我們知道， 一半的problem--的 我們知道答案是 我們的問題的右半部分。 因此，我們只看現在。 所以，現在我們來看看 中間還剩下些什麼。 該指數5。 我們再次做同樣的檢查 而且我們看到，它的體積更小。 因此，我們期待的是左邊。 然後我們看到檢查。 是在陣列值 索引4等於7？ 是的。 因此，我們可以返回true，因為 我們發現在我們的列表中選擇值。 我是否通過去的方式 是否有意義給大家？ 確定。 我給你們也許一樣， 三，四分鐘，以搞清楚 如何在偽代碼本。 所以，想像一下，我問你寫 函數調用搜索（）的返回 一個值，布爾值， 這是真的還是false--類似， 如果你找到了真正的 值，如果你沒有假的。 然後你 在值傳遞你 在尋找到值， 是array--哦，我一定會把 在錯誤的地方。 確定。 不管怎樣，應該有 到過的值的右側。 然後INT n是數 在該數組元素。 你會如何去努力 偽代碼在這個問題？ 我給你們喜歡 三分鐘的時間做到這一點。 不，我認為有only-- 是啊，有一個正確的在這裡。 聽眾：可以嗎？ ANDI彭：是啊，我給你。 是不是工作？ OK，涼。 確定。 好球員，我們 要收服入。 確定。 因此，假設我們已經有了這個可愛的 小數組在它的n值。 我沒有畫線。 但是我們怎麼能去 嘗試寫這個？ 有沒有人要 給我的第一行？ 如果你想給我 第一行該偽代碼。 聽眾：[聽不清] 聽眾：你想要 遍歷through-- 聽眾：只為循環的另一個？ 聽眾：──。 ANDI彭：所以這一塊是有點棘手。 想想about--你想 要繼續運行這個循環 一遍又一遍，直到什麼時候呢？ 聽眾：直到[聽不清] 值等於該值。 ANDI鵬：沒錯。 所以，你可以真正地寫 - 我們甚至可以把它簡化了。 我們可以寫一個while循環，對不對？ 所以，你可以有loop-- 我們知道，這是一段時間。 但現在，我要去 說“循環” - 通過什麼？ 環until--是什麼 我們結束條件？ 我想我聽到了。 我聽到有人說了吧。 聽眾：值等於中間。 ANDI彭：再說一遍。 聽眾：或者，直到 值要搜索 為等於中間值。 ANDI彭：如果有什麼是不是在那裡？ 如果你正在尋找的價值 對於實際上不是在這陣？ 聽眾：你返回1。 ANDI鵬：但是我們要 循環，直到如果我們有一個條件？ 是啊。 聽眾：直到有只有一個值？ ANDI彭：你可以循環 until--讓你知道，你是 將有一個最大值，對不對？ 而你知道，你會 有一個最小值，對不對？ 也因為，這東西 我忘了之前的說法， 這東西是 約二分查找關鍵 是你的數組已經排序。 因為沒有辦法做 這一點，如果他們只是隨機值。 你不知道，如果一個人的 比另一個大，對吧？ 所以，你知道你的最大和 您分鐘都在這裡，對不對？ 如果你將要調整 你最大的您分鐘和mid-- 就讓我們假設你的 中間值右這裡 - 你要基本 循環，直到你的最小值是 大致相同的最大，右，或 如果你的max是不一樣的分。 對嗎？ 因為當發生這種情況，你知道， 你最終擊中了相同的值。 所以，你要循環，直到你分鐘 小於或等於用於：哎呀， 不小於或等於 around--最大的另一種方法是。 這是否有意義？ 我花了一些嘗試，以獲得這一權利。 但循環，直到你的最大值 基本上是差不多少 大於或等於您的最低，對不對？ 當你知道這是 你已經收斂。 聽眾：當你將最大 值是小於最小？ ANDI彭：如果你保持 調整它，這 就是我們要 在做這個。 這是否有意義？ 最小和最大只是 整數，我們可能 將要創建的保留 賽道上，我們正​​在尋找的。 因為數組存在 無論我們在做什麼的。 就像，我們沒有實際的物理 斬去陣列，對不對？ 我們只是調整 我們正在尋找。 這是否有意義？ 聽眾：是的。 ANDI彭：OK。 所以，如果這對我們的循環中的條件， 我們需要什麼這個循環裡面？ 什麼是我們將要想要做什麼？ 所以，現在，我們已經有了 一個最大和最小，權， 可能產生在這裡的某個地方。 我們將可能希望 找一個中間的，對不對？ 我們該如何為 能找到中間？ 什麼是mathematical-- 聽眾：最大加分除以2。 ANDI鵬：沒錯。 這是否有意義？ 做你們明白為什麼我們 不只是use--為什麼我們這樣做 而不是做了2只除以n？ 這是因為n是一個值 那將保持不變。 對嗎？ 但是，當我們調整我們的最低和 最大值，他們將改變。 其結果，我們的中間 都不會改變太多。 所以這就是為什麼我們要 在這裡做的權利。 確定。 然後，現在 我們發現our--耶。 聽眾：只是一個快速的問題 - 當你說最大和最小， 在我們假設 它已經排序？ ANDI彭：是啊，這實際上是一個 先決條件二進制搜索， 你必須知道它​​的排序。 這就是為什麼排序，你寫你的 您的二進制搜索之前，習題集。 確定。 所以，現在我們知道我們的中點 是，你要什麼做的嗎？ 聽眾：我們想比較 即到另一個。 ANDI鵬：沒錯。 所以，你要比較 月中的價值，對不對？ 而這是什麼告訴 我們，當我們比較？ 什麼是我們想要做的之後？ 聽眾：如果該值越大 比中期，我們希望把它割下來。 ANDI鵬：沒錯。 因此，如果該值大 比中旬，我們 會想改變這些 最小和馬克塞斯，對不對？ 我們需要什麼改變？ 因此，如果我們知道價值的地方 在這裡，你有什麼，我們要改變？ 我們要改變我們的 最小的是中端，對不對？ 然後否則，如果它在這個 上半年，有什麼事我們要改變？ 聽眾：你最大的。 ANDI彭：是的。 然後，你只是去 保持循環，對不對？ 因為現在，一次迭代後， 通過，你已經有了一個最大這裡。 然後你就可以重新計算中間。 然後你就可以比較。 而你要堅持下去 直到分鐘和馬克塞斯 已經基本收斂。 而且，當你知道這是 你打它的結束。 而無論你已經找到了 或者你有沒有在這一點上。 這是否有意義給大家？ 確定。 這是非常重要的， 因為你有 在您的代碼今晚這樣寫。 但是你們有一個相當不錯的 什麼，你應該做的意義， 這是很好的。 確定。 所以，我們已經得到了大約七 離開分鐘一節。 所以，我們要談談 這pset的，我們會做。 因此的pset分為兩半。 上半年涉及 實施發現 在你寫一個線性搜索，一 二進制搜索，和一個排序算法。 因此，這是第一個 一次在PSET哪裡 我們會給予你們什麼所謂 分配代碼，這是代碼 我們已經預先寫好， 只是留下了一些棋子落 為你完成寫作。 所以你們這些傢伙，當你看這個 代碼中，你可能會真是嚇壞了。 如果你只是想，啊，我 不知道這是什麼在做， 我不知道一樣，這似乎 這麼複雜，啊，放鬆。 這是確定的。 閱讀規格。 該規範將解釋你到底 什麼所有這些方案都在做。 例如，generate.c是一個程序 這會是你的pset中。 你實際上並沒有去觸摸它，但 你應該明白它在做什麼。 而generate.c，所有它做的是 或者產生隨機數 或者你可以給它一個種子，像 預先安排的號碼，它需要， 它產生更多的數字。 因此，有一種特定的方式來 實施generate.c其中 你可以做一串數字 為您測試您的其他方法上。 所以，如果你想為 例如，測試你的發現， 你想運行generate.c， 生成一串數字， 然後運行你的助手功能。 你的助手功能就是你 實際的物理寫代碼。 並認為傭工作為庫文件 你寫的那些發現正在呼叫。 所以在helpers.c，你會 做搜索和排序。 然後，你要基本上 只是把它們放在一起。 該規範將告訴你如何 把在命令行上。 你就可以測試是否 不是你的排序和搜索工作。 酷。 有沒有人已經開始， 遇到問題或疑問 他們現在所擁有的這個嗎？ 確定。 聽眾：等待。 我有一個問題。 ANDI彭：是的。 聽眾：所以我就開始做 在helpers.c線性搜索 它並沒有真正的工作。 但後​​來，我發現我們只是 要刪除它，做二進制搜索。 因此，它的問題，如果它不能正常工作？ ANDI彭：簡短的答案是否定的。 但由於我們是不是 - 聽眾：但是，沒有一個人的 其實檢查。 ANDI彭：我們從來沒有 要看到這一點。 但是，你可能想使 確保你的搜索工作。 因為如果你的線性 搜索無法正常工作， 那麼機會是你的二進制 搜索是不會正常工作。 因為你也有類似的 邏輯在兩人面前。 不，這其實並不重要。 所以唯一的，你轉 在有排序和二進制搜索。 是啊。 而且，很多孩子們 嘗試編譯helpers.c。 你沒有真正允許 要做到這一點，因為helpers.c 不具有的主要功能。 所以，你只應該 是實際編制 產生和發現，因為找不到電話 helpers.c並在它的職能。 這樣就使得調試 一個痛苦的對接。 但是，這就是我們要做的。 聽眾：你剛才做的所有，對不對？ ANDI彭：你可以 讓所有的嗯，是的。 確定。 所以這是它在什麼條件 pset的要求你都做。 如果您有任何問題，請隨時 免費區之後問我。 我會在這裡一樣，20分鐘。 和是的，處理器集的 真的沒有那麼糟糕。 你們應該沒問題。 這些，只是遵循的指導方針。 一種有意識，從邏輯上講，是什麼 應該發生，你會沒事的。 不要太害怕。 有很多的代碼 已經寫在那裡。 不要太害怕，如果你不 明白了這一切手段。 如果這是一個很大，這是完全罰款。 而來到辦公時間。 我們會幫你看看。 聽眾：用多餘的 功能，我們看這些嗎？ ANDI彭：是的，這些都是在代碼中。 在遊戲中的15，一半的 它已經為你寫的。 因此，這些功能 已經在代碼中。 是的。 好的。 那麼，最好的運氣。 這是一個噁心的一天。 所以希望你們不要覺得太 不好呆在裡面和編碼。