[音樂播放] 教授：好的。 這是CS50，這是 三星期結束。 所以，我們今天在這裡，而不是在桑德斯 劇場，而是在韋德納圖書館。 其內部是一個工作室 被稱為豪瑟工作室， 或者我們應該說工作室H，或應 我們say--如果你喜歡這個笑話， 它實際上是從 同學，馬克，網上， 誰通過Twitter提出之多。 現在，有什麼很酷 是在工作室在這裡 是，我被這些綠色包圍 牆，綠屏或色度， 可以這麼說，這意味著，CS50的 製作團隊，我並不知道 現在，可以把 我最在世界任何地方， 是好還是壞。 現在是什麼樣的未來，問題集 二是在你的手中本週， 但問題集 三此接下來的一周， 你將受到挑戰 所謂遊戲的15 一個老黨員贊成票 你可能還記得接受 作為一個孩子，有一大堆 可滑動的上，下的數字， 左，右，以及有一個缺口 在拼圖，您在其中 實際上可以滑動的拼圖。 最終你收到此 拼圖一些半隨機的順序， 和目標是 頂級排序，到下， 從左到右，從一個 一路攀升至15。 不幸的是，實施 你手邊 將是軟件 根據，不是身體。 你實際上將不得不寫 代碼與學生或用戶可以 打15場比賽。 而事實上，在黑客 遊戲的15版， 你會是一個挑戰來實現， 這種老派的不只是播放 遊戲，而是求解 這一點，實現上帝模式， 可以這麼說，實​​際上 解決這一難題的人， 向他們提供線索， 提示後，在提示。 因此，更多的在下週。 但是，這是什麼樣的未來。 現在還記得，在本週早些時候 我們有這個懸念，如果你願意， 因此，我們正在做排序的最好 明智的是一個上限的大O的n 平方。 換句話說，冒泡排序， 選擇排序，插入排序， 所有的人，而不同 在執行過程中， 演化成一個n平方運行 時間在非常最壞情況。 而我們通常認為 最糟糕的情況下進行排序 是一個你投入 是完全倒退。 事實上，花了相當多的步驟 要實現每個算法。 現在，在類的盡頭 回想一下，我們比較冒泡排序 反對對另外一個選擇排序 我們稱之為合併排序的時候， 我建議它採取 優勢從一周一節課 零，分而治之。 並以某種方式達成某種 對數運行時間最終， 而不是東西 這是純粹的二次。 而且它不是相當的對數， 這是多一點比。 但是，如果你從類回憶， 這是更多，更快。 讓我們來看看，我們不放過。 冒泡排序與選擇 排序與歸併排序。 現在，他們都在運行，在 理論上講，在同一時間。 CPU被以相同的速度運行。 但是你能感覺到有多無聊本 是很快將成為， 並有多快，當我們注入 有點星期零的算法， 我們可以加快速度。 所以標記排序看起來令人驚訝。 我們怎樣才能利用它，為了 更快速的數字進行排序。 好吧，讓我們回想起 一個成分，我們 有回零一周，那 在電話簿中尋覓， 並且記得， 偽代碼，我們建議， 通過它我們可以找到 有人喜歡邁克·史密斯， 看起來有點這樣的事情。 現在來具體看看 在第7行和8，以及10和11， 這導致該循環，因此我們維持 回到第3行一次，又一次， 又一次。 但事實證明，我們可以查看 這種算法，這裡在偽代碼中， 一點更全面。 事實上，我在尋找什麼 在這裡，屏幕上， 是一種算法，用於搜索 邁克·史密斯在一些組頁面。 事實上，我們可以簡化 算法在這些線路7和8， 而10和11，只是這麼一說， 我在這裡介紹了黃色。 換句話說，如果麥克 史密斯早在書中， 我們並不需要指定步驟 一步現在怎麼去找他。 我們沒有指定 回到3號線， 我們為什麼不只是代替， 比方說，更一般地， 搜索麥克在 書的左半邊。 相反，如果麥克 實際上後來在書中， 為什麼我們不只是引用引文結束搜索 麥克在書中的右半部分。 換句話說，我們為什麼不只是 排序撐船對自己說， 搜索麥克在這 書的一部分， 並把它留給我們現有的 算法告訴我們 如何在搜索麥克 即左書的一半。 換句話說，我們的 算法的工作無論是 電話簿該厚度的，這 厚度，或者任何任何厚度。 因此，我們可以遞歸 定義這個算法。 換句話說，對 屏幕這裡，是一個算法 為尋找麥克·史密斯 之間的電話簿的網頁。 因此，在管線7和10所示，讓我們 只說這一點。 我用這個詞了一下 以前，而事實上，遞歸 是的流行語現在， 和它的這個過程 做一些週期性通過某種方式的 使用您已有的代碼， 並再次調用它， 又一次，又一次。 現在，這將是重要的 我們莫名其妙地底 出來了，不這樣做無限長。 否則，我們將 有確實是一個無限循環。 但是讓我們看看我們是否能借這個想法 遞歸的，又做什麼 一次又一次，來解決 通過合併排序問題 排序，更加有效。 所以，我給你歸併排序。 讓我們一起來看看。 因此，這裡是偽代碼，用 這是我們可以實現分選， 採用這種算法稱為歸併排序。 這是相當簡單，就是。 在n個元素的輸入， 換句話說，如果你 給定n個元素和數字 字母或任何輸入是， 如果你給定的n個元素，如果 n小於2，只是返回。 對嗎？ 因為，如果n小於2，即 意味著我的元素列表 可以是0或1號，並 在這兩個瑣碎的情況下， 名單已經排序。 如果沒有清單，它的排序。 而且如果有長度的列表 1，這顯然排序。 所以該算法僅需要 真正做一些有趣的事情， 如果我們有兩個或更多的 元素給我們。 因此，讓我們來看看神奇的話。 元件的左半其他排序， 然後排序元素的右半 然後合併排序半。 什麼樣的心態彎曲 在這裡，是，我真的不 似乎已經告訴過你 任何事情，只是還沒有，對不對？ 所有我已經說過了，給定名單 n個元素，排序的左半邊， 然後右半，然後 合併排序的一半， 但如果是實際的秘密武器？ 哪裡的算法？ 那麼事實證明，這兩條線 首先，要素排序左前衛， 和排序右半元件， 是遞歸調用，可以這麼說。 畢竟，在這個 時間點上，我必須 一種算法，用以 排序一大堆的元素？ 是。 就是這裡。 這是就在屏幕上，並 這樣我就可以使用同一套步驟 在左半排序， 我可以右半部分。 事實上，一次，又一次。 因此，好歹，我們將很快 看到這種情況，歸併排序的魔力 嵌入在非常最終 線，合併排序的半部。 而這似乎相當直觀。 你把兩半，而你， 不知何故，把它們合併起來， 我們將看到這個 具體在某一時刻。 但是，這是一個完整的算法。 而讓我們看看究竟為什麼。 那麼假設我們給這些相同 八種元素在這裡在屏幕上，人們 通過八個，但他們 在看似隨機的順序。 而這一目標的手 這些元素進行排序。 嗯，我怎麼能去 做它用，再次， 歸併排序，按本偽？ 再次，這種根深蒂固的 你的頭腦，就一下。 第一種情況是相當 瑣碎，如果它小於2， 剛回來，沒有工作要做。 所以真的有只有三個 步驟要真正記住。 又一次，又一次，我 會希望有 在左半排序， 排序的右半 然後一旦其 兩個半部進行排序， 我想將它們合併在一起 成一個排序列表。 所以記住這一點。 因此，這裡的原始列表。 讓我們把這個作為 陣列，因為我們開始 兩個星期，這是一個 連續的內存塊。 在這種情況下，含有8 數字，背靠背回來。 而且，我們現在申請歸併排序。 所以，我首先想要排序 這個列表的左邊一半， 讓我們，因此， 集中4,8，6和2上。 現在，我怎麼去 分揀大小4的名單？ 嗯，我必須現在考慮 排序的左半的左側。 再次，讓我們倒帶只是一瞬間。 如果偽代碼是這樣的， 而我給八素， 8顯然是更大 大於或等於2。 因此，與第一種情況下不適用。 因此，八個元素進行排序，我第一次 排序元件的左半部， 接著我的右半邊，然後我合併 兩個半排序，每個大小為4。 確定。 但如果你只是告訴我，排序 左半部分，也就是現在的大小為4， 我怎麼排序的左半邊？ 好吧，如果我有一個 四個要素投入， 我第一次排序的左 二，則對二， 然後我把它們合併起來。 如此反复，就顯得有點 一記彎曲在這裡比賽， 那種因為你，要 還記得你在哪裡的故事， 但在一天結束時， 給定任意數量的元素， 你首先要排序的 左半，然後右半邊， 然後把它們合併起來。 讓我們開始這樣做。 以下是八種元素的輸入。 現在，我們正在尋找的左半部分在這裡。 我怎麼排序四個要素？ 嗯，我第一次排序的左半邊。 現在，我怎麼排序的左半邊？ 嗯，我一直在給定的兩個元素。 因此，讓我們這兩個元素進行排序。 圖2是大於或 等於2，當然。 所以這第一種情況下不適用。 所以，我現在有向左排序 上半年這兩個元素。 左半部分，當然，僅僅是4。 所以，我怎麼排序一個元素的列表？ 現在好了，特別的基本情況 往上頂，可以這麼說，適用。 1小於2，和我的 名單確實是大小為1。 所以我就回來。 我沒有做任何事情。 事實上，看看我有 完成後，4已經排序。 就像我已經 部分成功在這裡。 現在看來很愚蠢 權利要求，但它是真實的。 圖4是尺寸1的列表。 它已經排序。 這是左半部。 現在我排序的右半​​部分。 我的輸入是一個元素，8 同樣，已經排序。 愚蠢，太，但同樣， 這一基本原則 將會讓我們現在建 在此之上成功。 4排序，8排序，現在 什麼是最後一步？ 因此第三和最後的步驟，任何 一次你排序列表，召回， 是要合併的兩半， 左和右。 因此，讓我們這樣做。 我的左半邊，當然，4。 我的右半邊是8。 因此，讓我們做到這一點。 首先我要分配 一些額外的內存， 我將在這裡代表， 因為只是一個輔助陣列， 這是足夠大，以適應這一點。 但是，你能想像延伸 該矩形的整個長度， 如果我們需要更長時間之後。 我如何採取4和8，和合併 尺寸1在一起的那兩個名單？ 在這裡，也很簡單。 4是第一位的，然後是8。 因為如果我要排序的 左半，然後右半邊， 然後合併這兩個半 同時，在有序， 4是第一位的，然後是8。 因此，我們似乎正在取得進展，甚至 雖然我沒有做任何實際工作。 但是，請記住，我們是在故事中。 我們最初採取了八大要素。 我們的排序左半，這是4。 然後，我們整理了左半 的左半部分，為2。 在這裡，我們走了。 我們正在與該步驟完成。 因此，如果我們排序 左半邊的2，現在我們 得的2右半排序。 這樣的2的右半邊是 這裡這兩個值，6和2。 因此，讓我們現在就採取大小的輸入 2，和排序左半，然後 右半，然後 把它們合併起來。 那麼我怎麼排序大小的列表 1，僅包含數6？ 我已經做了。 大小為1的那個列表進行排序。 我如何排序的另一個列表 尺寸如圖1所示，所謂的右半。 那麼它也已經排序。 數字2是孤獨的。 所以，現在我有兩個半，左， 好吧，我需要將它們合併在一起。 讓我給自己做一些額外的空間。 並把2在那裡， 然後在那裡6，從而 排序該列表，左，右， 和合併在一起，最終。 所以，我在稍微好一點的形狀。 我不這樣做，是因為清楚4，8，2， 6是不是我想要的最終排序。 但是我現在有2號兩個列表，該 雙方都分別進行了排序。 所以，現在，如果你在你的心中的倒帶 眼睛，哪裡是離開我們？ 我開始與八素，然後我 又縮減到了4左半部分， 然後2左半，和 然後為2的右半邊， 我完成了，因此，左排序 一半的2，以及2的右半 那麼什麼是第三次，也是最後一步嗎？ 我必須合併到一起 2號兩個列表。 因此，讓我們繼續前進。 在這裡，在屏幕上，給 我一些額外的內存， 雖然在技術上，注意，我 有一大堆的空白向上頂 那裡。 如果我想特別 有效的空間明智的， 我剛開始運動的元素 來回，頂部和底部。 但只是為了視覺清晰， 我打算把它放在樓下， 讓事情變得非常乾淨。 所以，我有大小2的兩個列表。 第一個列表有4個和8個。 第二個列表中有2和6。 讓我們合併這些 一起排序順序。 當然，2，是第一位的， 然後4，然後6，然後8。 而現在，我們似乎越來越 有趣的地方。 的現在，我已經來分類的一半 列出，而巧合的是，這是 所有的偶數，但 確實是，只是一個巧合。 而我現在已經整理左 一半，所以，它的2，4，6，和8。 沒有什麼是壞了。 那感覺就像進展。 現在感覺我已經 在討論永遠的現在， 所以剩下，如果這待觀察 算法確實是更有效的。 但是，我們正在經歷 它的超級有條不紊。 當然，一台電腦，， 會做這樣的。 因此，我們在哪裡？ 我們開始與八個元素。 我排序的4左半部。 我似乎與完成。 所以，現在的下一個步驟是 排序的4的右半部分。 而這一部分，我們可以去 通過多一點 很快，雖然你 歡迎後退或暫停，只是 想通過它在 自己的節奏，但什麼 我們現在是一個機會， 做同樣的算法在四個 不同的號碼。 因此，讓我們繼續前進，並專注於 右半部分，我們在這裡。 的那左半 右前衛，現在的 左側的左半邊 一半的右半部， 以及如何排序大小的列表 1只包含數字1？ 它已經完成。 我該怎麼做相同的列表 中只包含7尺寸1？ 它已經完成。 步驟三本半，然後 被合併這兩個元件 成大小為2,1和7的一個新的列表。 似乎沒有所做的一切 那麼多有趣的工作。 讓我們看看接下來會發生什麼。 我只是排序的左半 我原來輸入的右半部分。 現在讓我們來排序的權利 半，它包含5和3。 讓我們再次看一下左邊 上半年，分類，右半邊，排序， 並合併這兩個在一起， 到了一些額外的空間， 3是第一位的，然後是5。 所以，現在，我們已經整理了 右半部分左半 原問題的，並 右邊一半的右邊一半 的原始問題。 什麼是第三步也是最後一步？ 那麼這兩個半融合在一起。 因此，讓我得到我自己的一些 額外的空間，但同樣，我 可以使用備用空間往上頂。 但是，我們要保持 它簡單直觀。 讓我在現在1合併，並 然後3，然後5，然後7。 現在，從而留下了我的 原問題的右半 這是完全排序。 那麼剩下？ 我覺得我一直在說的 同樣的事情又一次，又一次， 但是這反映了 事實是，我們正在使用遞歸。 使用的方法 算法再次，並再次， 對較小的子集 原來的問題。 所以，我現在有一個左排序 原來的一半問題。 我有一個正確排序的一半 的原始問題。 什麼是第三個也是最後一步？ 哦，這是合併。 因此，讓我們做到這一點。 讓我們來分配一些額外的 記憶，但我的上帝，我們 可以把它的任何地方了。 我們提供這麼大的空間 給我們，但我們會保持它的簡單。 而不是回去和 第四我們原來的記憶， 我們只能這樣做 視覺這兒下面， 完成了合併 左半和右半部分。 因此，通過合併，請問我需要做什麼？ 我想藉此元素的順序。 所以看左半邊， 我看到的第一個數字是2。 看看我的右半邊， 我看到的第一個號碼 是1，所以很明顯這 一些做我想剜出， 並把第一個在我的最後名單？ 當然，1。 現在我要問同樣的問題。 在左前衛，我已經 仍然得到了2號。 在右半， 我已經得到了3號。 哪一個我想選擇？ 當然，數字2和 現在通知考生 是4上的右左，3。 讓我們，當然，選擇3。 現在的候選人4 右側的左，5。 我們，當然，選擇4。 6上右側的左，5。 我們，當然，選擇5。 6上右側的左，7。 我們選擇6，然後我們 選擇7，然後我們選擇8。 瞧。 話那麼一個龐大的數字之後，我們 已經整理了八種元素列表 成一個通過八個列表， 它將與每一步增加， 但多少時間 它帶我們去做到這一點。 嗯，我特意 奠定了東西出來形象化 在這裡，讓我們可以種 看到或體會到師 征服一個已經發生的事情。 事實上，如果你回頭看看之後， 我已經離開所有這些虛線 在佔位符，就可以了， 樣的，看到的，以相反的順序， 樣的，如果你回頭看的 現在的歷史，我原來的名單 是大小8，當然，。 然後以前，我是 處理規模4的兩個列表， 然後大小為2的四個列表， 然後大小為1的八個列表。 那麼，這， 樣的，提醒你？ 嗯，事實上，任何 我們已經算法 看著迄今我們 鴻溝和差距，並且差距， 再次保持有東西， 再次，結果在這個總體思路。 所以有什麼東西 對數回事。 而且這不是n相當日誌，但 有一個對數組件 ，這是我們剛剛做。 現在，讓我們來考慮，實際上是如何。 所以日誌N的，又是 一個偉大的運行時間， 當我們不喜歡的東西 二進制搜索，因為我們現在稱呼它， 分而治之的策略 通過我們找到邁克·史密斯。 現在技術上。 這是n個日誌基地2個，甚至 儘管大多數數學課， 通常10是你假設的基礎。 但計算機科學家幾乎總是 思考和談論的基地2個方面， 所以我們一般只說日誌 而不是n日誌基地2 N， 但他們只有一個與 在計算機的世界一樣 科學，順便說一句， 有一個常數因子 兩者之間的差別，因此它的 反正沒有實際意義，更多的正式理由。 但現在，我們關心 大約是這樣的例子。 因此，讓我們不由的例子證明，但 至少使用數字的一個例子 手頭作為一個全面的檢查，如果你願意。 所以以前的公式是日誌基地 2 n個，但什麼是正在這種情況下。 我有N個原始號碼，或8 原有的一些具體。 現在，它已經有點 一段時間，但我敢 確保日誌基地2 值8是3， 而事實上，有什麼好的關於這是 該圖3是次完全數 你可以將一個列表 又一次，又一次的長度為8， 又一次，直到你離開 只有大小為1的列表。 對嗎？ 8變為4，進到2， 變為1，這是 反光正是中 圖片我們有剛才。 那麼一點點神智檢查到哪裡 對數是實際參與。 所以，現在，還有什麼是這裡涉及？ ñ。 所以請注意，每 一次我分裂名單， 儘管以相反的順序歷史 在這裡，我還在做ñ的事情。 要求合併的步驟， 我接觸的每一個數字， 為了將其滑入 其適當的位置。 因此，即使這個高度 圖為大小日誌N或3的n個， 具體地，換言之， 我做了三個部門在這裡。 我沒有多少工作要做水平 沿著這個圖表每一次？ 好吧，我做了n步的 工作，因為如果我 有四個元素和四個元素， 我需要將它們合併在一起。 我需要經過 這四個和這四個， 最終合併它們 回八素。 相反，如果我有八手指 在這裡，我不這樣做，八 fingers-- sorry--如果我 有四個手指在這裡， 這是我做的，四根手指 在這裡，這是我做的， 那麼這同樣 像以前的例子，如果我做 有八個手指雖然 總的來說，我可以，那種，做的。 我可以準確地在這裡做， 那麼我可以肯定 合併所有這些名單 尺寸1在一起。 不過，我當然要看看 在每個元素一次。 所以該方法的高度是log N， 這個過程的寬度，可以這麼說， 為n，所以，我們似乎 有，最終，是 大小n次的運行時間n記錄。 換句話說，我們將 列表，記錄了n次， 但我們做到了每一次，我們有 觸摸的每一個元素 為了將它們合併 總之，這 為：N步，所以我們有n次日誌N， 或者作為一個計算機科學家會說， 漸近，這 將是很大的​​字 來描述的上 勢必在運行的時候， 我們正處在一個大O運行 日誌N次的，可以這麼說。 現在，這是顯著的，因為 回顧一下運行時間分別為 與冒泡排序和選擇 排序和插入排序， 甚至有幾個人的存在， Ñ​​平方是我們在那裡的。 你也可以，那種，看到這個在這裡。 如果n的平方顯然是n倍 N，但在這裡我們有N次登錄N， 我們已經知道，從週 零，即日誌n時，對數， 是不是一些線性好。 畢竟，回憶圖片 與紅色和黃色的 而綠線，我們畫的 綠色對數線要低得多。 因此，更好更快 比直黃色和紅色的線， n次N日誌，著實更好 比n次N，或N的平方。 因此，我們似乎有 識別算法合併 那種運行在多 更快的時間，而事實上， 這就是為什麼，在本週早些時候，當 我們看到泡沫之間的較量 排序，選擇排序，並合併 排序，歸併排序真的，真的贏了。 事實上，我們甚至沒有等待 對於冒泡排序和選擇排序 完成。 現在讓我們來一個其他通 在此，從一個稍微更 正式的角度來看，只要在 情況下，這種共振效果更佳 高於層面的討論。 因此，這裡的算法了。 讓我們捫心自問， 什麼的運行時間 是這個算法的各個步驟？ 讓我們把它分為第一 殼體和第二殼體。 中頻和ELSE在IF的情況下， 如果n小於2時，只返回。 感覺像固定時間。 這是，那種，像兩個步驟， 如果n小於2時，然後返回。 但是，正如我們週一表示， 固定時間，或大O 1， 可以是兩個步驟，三 步驟，甚至是1000步。 重要的是，它的 的步驟的數目恆定。 因此，黃色高亮偽 在這裡試車時，我們會打電話給它， 恆定的時間。 所以更正式，和 我們將用於：此 將在多大程度上我們 正式這種權利now-- n個T， 一問題的運行時間 這佔據N出頭作為輸入， 等於大O之一， 如果n小於2。 因此，它是有條件的。 所以要清楚，如果n小於 2，我們有一個很短的列表，然後 的運行時間，T的n，其中n是 1或0，在這種非常具體的情況下， 它只是將是恆定的時間。 這將需要一個 一步，兩步，等等。 它是一個固定的步數。 因此，多汁的部分肯定是在 在偽另一種情況。 該ELSE情況。 排序左元素的一半，排序權 半元件，合併排序的半部。 多久每一這些步驟走？ 好吧，如果運行 時間到n個元素進行排序 是，我們很叫它 一般，n個T， 然後左排序 一半的元素 一種是，好像是說， ñ對T除以2， 並且類似地排序的右半 因素之一是，那種，好像說， n個牛逼分2，然後 合併排序的一半。 那麼，如果我有一些 元件的數目在這裡， 樣四，有的數 這裡的元素，如4， 我必須合併這四個中 在，並在各一個的這四個 後等，從而使 最終我有八個元素。 這感覺就像那是大O n個步驟？ 如果我有n個指和各 它們已被合併到的地方， 這是像另一個n步。 因此，我們確實通過公式， 我們可以表達這一點， 雖然有點scarily在第一 一目了然，但它是 捕捉正是這樣的邏輯。 T N的運行時間，如果n 是大於或等於2。 在這種情況下，在ELSE情況下，是正對T 除以2的n個除以2，再加上T， 再加上大O n的一些 步線數， 也許正是N，也許2倍 N，但它的大概，n階。 所以這也就是我們如何 通過公式表達這一點。 現在，你不會不知道這一點，除非 你已經記錄了它在你的心中， 或看它在 背課本，那 可能有一點 備忘單底， 但這是，事實上，將要 給我們一個大O的n log n個， 因為復發了 你現在看到的在屏幕上， 如果你真的做到了出來，用 無限多的例子， 或者你通過公式做了，你會 看到這一點，因為此公式 本身是遞歸的，與叔 ñ過的東西就沒事了， 並在左邊ñ超過T，這樣可以 實際上被表達，最終 的n log n個大去了。 如果不相信，這是 精細現在，只要 採取的信念，那這就是，的確， 什麼復發導致， 但是這僅僅是多了一個有點 數學方法尋找 在合併排序的運行時間 根據它的偽孤獨。 現在，讓我們有點 從所有這一切歇口氣， 看一看在 某些前參議員​​，誰 可能看起來有點眼熟， 誰坐下來與谷歌的埃里克 施密特，前一段時間，接受採訪 在舞台上，在一大堆的前面 人，談話最終約 一個話題，那是相當熟悉的現在。 讓我們一起來看看。 埃里克·施密特：現在參議員， 你在這裡在谷歌， 我喜歡想的 總統作為一個工作面試。 現在很難找到一份工作作為總統。 奧巴馬：對。 埃里克·施密特：你是 該怎麼辦[聽不清]現在。 它也很難找到工作，在谷歌。 奧巴馬：對。 埃里克·施密特：我們有疑問， 我們要求我們的候選人的問題， 而這一次是從拉里·施維默。 奧巴馬：好。 埃里克·施密特：什麼？ 你們以為我在開玩笑？ 就是這裡。 什麼是最有效的方式來 排序一百萬的32位整數？ 奧巴馬總統：Well-- 埃里克·施密特：有時候， 也許我很抱歉，maybe-- 奧巴馬總統：不，不， 不，不，不，我think-- 埃里克·施密特：這不是它 - 奧巴馬總統：我 想想，我覺得泡沫 排序將是錯誤的路要走。 埃里克·施密特：來吧。 誰告訴他的？ 確定。 我沒有計算機科學on-- 奧巴馬：我們已經 得到了在那裡我們的間諜。 教授：好的。 讓我們後面現在離開 算法理論界 在漸近分析 物，並返回到某些主題 從週零和一，並開始 除去一些輔助輪， 如果你願意。 讓你真正了解 最終從地上爬了起來，什麼是 怎麼回事引擎蓋下，當你 編寫，編譯和執行程序。 特別記得，這是 第一個C程序中，我們看了一下， 一個典型的，簡單的程序 不爽，相對來說， 其中，它打印，你好世界。 而回想一下，我說，這個過程 該源代碼經過 也正是這一點。 你把你的源代碼，通過 它通過一個編譯器，像鏘， 進出自帶目標代碼，那 可能是這樣的，零和的 計算機的CPU，中央 處理單元或腦， 最終可以理解的。 事實證明，這是一個 過於簡單的一點， 我們現在正處在一個 位置梳理出 要了解什麼是真正被 怎麼回事引擎蓋下 每次運行時間 鐺，或更一般地， 每次你犯了一個程序， 使用make和CF 50 IDE。 尤其是，這樣的東西 這首先產生， 當你第​​一次編譯程序。 換句話說，當 把你的源代碼 並編譯它，什麼是第一 被輸出由鏘 是一些被稱為彙編代碼。 而事實上，它看起來完全一樣。 我在跑的命令 命令行前面。 鐺破折號大寫字母S的hello.c， 這個創建的文件 我叫hello.s， 這裡面都是一模一樣 這些內容，而多了幾分 上述多一點的下方， 但我已經把最豐厚 這裡，屏幕上的信息。 如果你仔細觀察，你會看到 至少有幾個熟悉的關鍵字。 我們主要在頂部。 我們在中間的printf下來。 而且我們也有世界你好 反斜杠N的報價樓下。 和其他一切在這裡 是非常低的水平指示 計算機的CPU可以理解的。 該移動存儲CPU指令 各地，從內存中加載的字符串， 最終，打印 事情在屏幕上。 現在發生什麼事雖歷經 此彙編代碼生成的？ 最終，你這樣做，事實上， 還是生成目標代碼。 但步驟都是真正 已經持續引擎蓋下 看起來有點像這樣。 源代碼變得彙編代碼， 然後變成目標代碼， 這裡的工作的話是， 當您編譯源代碼， 走出來的彙編代碼，然後 當你組裝你的彙編代碼， 出來自目標代碼。 現在鏘是超級複雜， 像很多的編譯器， 而且它所有這些步驟 在一起，它不一定 輸出任何中間 文件，您甚至可以看到。 它只是編譯的東西， 這是一般術語，其 描述了整個過程。 但是，如果你真的想 要特別地，有 多了很多事也有。 但是，讓我們現在也考慮，即使 該超級簡單的程序，hello.c中， 叫的功能。 它呼籲printf的。 但我沒寫printf的，事實上， 隨C，可以這麼說。 這是一個函數調用這 在標準io.h，宣稱這 是一個頭文件，它 是一個主題，我們將實際 深入到更深入沒多久。 但是，一個頭文件 通常伴隨著 由一個代碼文件，源代碼文件，所以 就像存在標準io.h. 不久以前，一個人， 或某人，也寫 一個稱為標準io.c中，在文件 它的實際定義， 或printf的實現， 和其他功能束， 實際上寫的。 因此考慮到，如果我們考慮有 這裡在左邊，hello.c中，當 編譯後，給了我們hello.s，即使 鏘不打擾保存在一個地方 我們可以看到它，並彙編代碼 被組裝成hello.o，這 確實是，默認名稱 每當你編譯源代碼給 編碼成目標代碼，但不 完全準備好執行它， 因為又邁進了一步 必須發生，並且具有 已經發生的事情在過去幾年 週，也許不知情的你。 特別的地方 在CS50 IDE，而這一點， 也將是一個比特的 過於簡單化了一會兒， 有，或者是很久以前， 一個稱為標準io.c中的文件， 有人編譯成 標準io.s或相當於 有人再組裝 成標準io.o， 還是原來成 稍有不同的文件 可以有一個不同的格式 共文件擴展名， 但在理論和概念上，正好 這些步驟必須發生某種形式。 這就是說，現在 當我寫一個程序， hello.c中，這只是說，你好世界， 而我使用別人的代碼 如printf，這是仙界 時間，在一個名為標準io.c中的文件， 後來不知怎的我得把我的 目標代碼，我的0和1 而那個人的對象 代碼，或0和1 並以某種方式連接成 最後一個文件，名為hello，即 擁有所有的零和 從我的主要功能的， 和所有的零 和那些像printf。 事實上，這最後一道工序是 所謂，鏈接您的目標代碼。 它的輸出 是一個可執行文件。 因此，在公平，在 的天，沒有結束 由於一個週也改變了，當我們 剛開始編譯程序。 事實上，所有的這一直 發生在引擎蓋下， 但現在，我們正處在一個位置 在這裡，我們實際上可以 梳理出這些不同的步驟。 事實上，在結束 這一天，我們仍然 留下零和一，這 實際上是一個很大的SEGUE現在 到C的另一能力，即 我們已經沒有利用最有可能 迄今為止，被稱為位運算符。 換句話說，迄今為止，任何時候我們已經 處理C或變量數據，C， 我們已經有像 字符，可漂浮，插件 和長和雙打之類的，但 所有這些都是至少八位。 我們從來沒有能夠 操縱單個位， 即使一個人位，我們 知道，可以代表一個0和1。 現在事實證明，在C，你 可以訪問各個位， 如果你知道的語法， 與得到他們。 因此，讓我們一起來看看 在位運算符。 所以圖為幾個符號 我們，那種類型的，以前見過。 我看到一個符號，一個垂直 酒吧和其他一些為好， 並且記得，符號與符號 是我們所見過的。 邏輯運算符，那就是你有 他們兩個人在一起，或者邏輯或 運營商，在那裡你 有兩個豎條。 位運算符，我們將 見位獨立運行， 只需使用一個符號，一個 單豎條，插入符號符號 隨之而來的，小 波浪線，然後離開 支架左支架，或 右括號右括號。 每個這些具有不同的含義。 事實上，讓我們一起來看看。 讓我們去老同學今天和使用 從昔日的觸摸屏， 已知，為白色板。 而這個白板 將會讓我們 發表一些相當簡單的符號， 或者更確切地說，一些相當簡單的公式， 我們可以再最終 槓桿率，為了 訪問個人 在C程序位。 換句話說，讓我們做到這一點。 讓我們先談了 矩符號， 這是按位與運算。 換言之，這是 運營商允許 我有一個左手變 典型地，和一個右側變量， 或者一個人的價值，如果我們和 他們在一起，給了我一個最終的結果。 所以，這是什麼意思？ 如果在一個程序中，你有一個變量 這些值的商店之一， 還是讓我們保持簡單，只 寫出零和一獨立， 這裡是如何的符號操作符。 0符號0將等於0。 現在，這是為什麼？ 這是非常相似 布爾表達式， 我們已經迄今為止的討論。 如果你以後都認為，在0 假的，0是假的，假的，假的 是，正如我們已經討論 從邏輯上講，也是假的。 所以，我們得到0在這裡。 如果拿0符號 1，清楚，也一樣， 將是0，因為對於這 左手邊表達式為true或1， 這將需要真正的和真實的。 但在這裡，我們有假 而真實，或0和1。 現在再次，如果我們有1符號 0，即，也將是0， 如果我們有1符號1， 最後我們有一個1位。 因此，換句話說，我們沒有做 什麼有趣的與該運營商 只是還沒有，這個符號運算符。 這是按位與運算。 但這些成分 通過它，我們可以做的 有趣的事情，因為我們很快就會看到。 現在，讓我們來看看剛才單 豎條在這裡就對了。 如果我有一個0位和我 或用，按位 OR運算符，另一0位， 這是怎麼回事，給我0。 如果我把一個0位和或用 1位，那麼我會得到1。 而事實上，只是 清晰，讓我回去， 所以，我的豎線 不能誤認為是1的。 讓我重寫所有的 我1是多一點 顯然，讓我們接下來看，如果我 有個1或0，這將是一個1， 如果我有1或1中， 也將是一個1。 所以，你可以在邏輯上看到或 經營者的行為非常不同。 這給了我0或0給了我0，但是 所有其他的組合給了我1。 只要我有一個1的 式，其結果將是1。 通過與和對比度 運營商的符號， 只有當我有兩個1的中 方程，我居然得到1了。 現在有一些其他的 運營商也是如此。 其中之一是一個涉及多一點。 因此，讓我繼續前進，抹去 此釋放一些空間。 而讓我們一起來看看 插入符號符號，只是一瞬間。 這通常是一個 字符，你可以鍵入 在鍵盤按住Shift 再一個你頂上美國的數字 鍵盤。 因此，這是獨家 OR運算，異或。 所以，我們剛才看到的或經營人。 這是異或運算符。 什麼是真正的區別是什麼？ 那麼就讓我們來看看公式， 並以此作為最終的成分。 0 XOR 0。 我要說的是始終為0。 這是異或的定義。 0 XOR 1將是1。 1異或0將是1， 1 XOR 1將是？ 錯了嗎？ 還是向右？ 我不知道。 0。 現在到底是怎麼回事嗎？ 那麼想想 該運營商的名稱。 異或，以便在 名種，顧名思義， 的回答為僅將是 1，如果輸入是排他性的， 完全不同。 因此，這裡的輸入是 相同的，所以輸出為0。 這裡的輸入是 相同的，所以輸出為0。 下面是輸出不同，它們 是互斥的，所以輸出1。 所以這是非常相似的 而且，它是非常相似的， 或者更確切地說，它是非常相似 或者，但只在專用方式。 這一個不再是1， 因為我們有兩個1的， 而不是排他地，它們中的一個。 好的。 怎麼樣的人？ 好了波浪線，同時， 其實不錯，簡單，謝天謝地。 這是一個一元 操作者，這意味著 它僅施加到一個輸入端， 一個操作數，可以這麼說。 不為左和右。 換句話說，如果你採取的波浪線 0，答案會是相反的。 如果你把波浪的1， 答案會有相反。 所以波浪線操作員 某種程度上否定了一下， 或者翻轉位來自 0至1或1至0。 這使我們最終 只有最後兩運營商， 所謂左移位，而 所謂向右移位運算符。 讓我們來看看如何將這些工作。 左移位運算符，寫 有兩個尖括號這樣， 操作如下。 如果我的輸入，還是我操作，向左 移位運算符是很簡單1。 我再告訴電腦 左移說明1，說七宿， 其結果是，好像我 採取1，並移動 七宿轉移到 左，默認情況下， 我們將假設 的空間權 打算用零填充。 換句話說，1左移7是要 給我一個1，其次是1，2，3， 4，5，6，7個零。 因此，在某種程度上，它可以讓你 取少量像1， 並明確使它更 多，在這種方式大得多， 但我們真的要見 更聰明的辦法吧 相反，還有， 好的。 這就是它了三個星期 我們會看到你下一次。 這是CS50。 [音樂播放] 揚聲器1：他是在小吃 酒吧吃熱軟糖聖代。 他擁有了一切在他的臉上。 他穿著巧克力像鬍子 揚聲器2：你在做什麼？ 揚聲器3：嗯？ 怎麼辦？ 揚聲器2：您剛才二次探底？ 你雙跌的芯片。 揚聲器3：對不起。 揚聲器2：你蘸了芯片， 咬了一口，並再次下跌。 揚聲器3： 揚聲器2：所以，這就像把 你的整個嘴就在暢遊。 下一次你把一個芯片， 只是沾了一次，並結束它。 揚聲器3：你知道嗎，丹？ 你沾要沾的方式。 我會沾，我要沾的方式。