所有的權利，所以，計算複雜度。 只是有點警告 在我們深入太far-- 這很可能是其中 最數學重的東西 我們談論的CS50。 希望這將不會過於龐大 我們會盡力引導你 通過的過程中，但 只是有點公平的警告。 有一點點 數學這裡涉及。 好了，所以為了使 利用我們的計算資源 在現實天下 - 這是真的 重要的是要了解算法 以及如何處理數據。 如果我們有一個非常 高效的算法， 可的資源量最小化 我們可用來對付它。 如果我們有一個算法， 是要採取了很多工作， 處理一個真正 大量的數據，這是 將需要更 和更多的資源，這 就是金錢，RAM，所有的那種東西。 

所以，能夠分析一個 使用這種算法工具集， 基本上，詢問的問題 -  如何做到這一點的算法規模 因為我們在它扔越來越多的數據？ 在CS50，數據量我們 有工作是非常小的。 一般情況下，我們的節目會 在第二或less--運行 大概少了很多 尤其是早期。 

不過想想一個公司的交易 擁有億萬顧客。 他們需要處理 客戶數據。 作為客戶數量它們 有變得越來越大， 這將需要 越來越多的資源。 還有多少資源？ 嗯，這取決於如何 我們分析的算法， 使用該工具箱中的工具。 當我們談論的複雜性 一種算法 - 有時你會 聽到它稱為時間 複雜度和空間複雜度 但我們正要 調用complexity-- 我們通常講 在最壞的情況。 由於絕對最差樁 數據，我們可以扔吧， 該算法將如何 處理或處理這些數據？ 我們一般稱之為最壞情況下的 運行時的算法大O的。 這樣一種算法可能被說 在n或n鄰鄰運行平方。 而更多的是什麼 這意味著在第二。 

然而，有時候，我們做護理 關於最好的情況。 如果數據是一切我們想要的 它是，它是絕對完美 和我們發送此完美 設置數據通過我們的算法。 在這種情況下會如何處理？ 我們有時指的是作為 大歐米茄，所以在與大O相反， 我們有大歐米茄。 大歐米茄在最好的情況。 大O在最壞的情況。 一般情況下，當我們談論 所述的算法的複雜性， 我們正在談論的 最壞的情況。 所以記住這一點。 

而在這個類中，我們通常會 到一邊離開了嚴格的分析。 有科學和領域 專門用於這種東西。 當我們談論的推理 通過算法， 我們會做件逐件進行多 算法，我們談論的類。 我們真的只是在談論 通過它推理常識， 不與公式或證明， 或類似的東西。 所以不要擔心，我們不會 變成一個大的數學課。 

所以我說，我們關心的複雜性 因為它要求的問題，怎麼樣 做我們的算法處理大， 被扔在他們更大的數據集。 那麼，什麼是數據集？ 什麼我的意思是當我說？ 這意味著不管是什麼讓最 在上下文中意義上說，是誠實的。 如果我們有一個算法，該 流程Strings--我們可能 說起字符串的大小。 這是該數據set-- 的大小，數量 字符組成的字符串。 如果我們談論的 算法處理的文件， 我們可能會談論如何 千字節包含該文件。 這就是今天的數據集。 如果我們談論的算法 處理數組更普遍， 如排序算法 或搜索算法， 我們可能談論的數 的組成的陣列元素。 

現在，我們可以測量 算法 - 特別是 當我說我們可以 測量的算法，我 意味著我們可以衡量 很多資源，它佔用了。 無論這些資源是多少 RAM--字節或兆字節的RAM 它使用。 或多少時間才能運行。 我們可以把這種 測量，隨意，F N的。 其中n是數 在數據集中的元素。 而F N是多少出頭。 有多少資源的單位呢 它要求以處理該數據。 

現在，我們其實並不關心 什麼F N的正是。 事實上，我們很少will-- 肯定永遠不會在這個分類 - 我 潛入任何非常深 分析什麼樣的F n為。 我們只是要談論什麼的F n近似或者什麼也容易。 和算法的傾向是 其最高階項決定。 我們可以看到我 意思是，通過採取 一看一個更具體的例子。 

所以我們可以說，我們有 三種不同的算法。 其中第一個佔據N 資源立方，一些單位 處理規模為n的數據集。 我們有第二個算法，需要 ñ立方加N的平方資源 處理規模為n的數據集。 而且我們有第三 算法運行in--的 需要n個立方減去8N平方 加上20 N單位的資源 處理的算法 與數據集大小為n的。 

現在，再次，我們真的不打算 進入這種詳細程度。 我真的只是這些了 這裡作為一個點的圖示 那我將是 使在第二，這 是我們唯一真正關心 關於物聯網的趨勢 隨著數據集變得越來越大。 因此，如果數據集為小，有 實際上是一個非常大的差異 在這些算法。 第三種算法有 需要13倍以上， 資源的13倍的量 運行相對於第一個。 

如果我們的數據集的大小為10，這 是大的，但不一定是巨大的， 我們可以看到，有 其實有點區別。 第三種算法 變得更加有效。 這是關於實際上40％ -  或60％更有效。 需要40％的時間量。 它可以run--它可以採取 400單位的資源 處理規模10的數據集。 而第一 算法，相比之下， 需要1000單位的資源 處理規模10的數據集。 但是，看看會發生什麼的 我們的數字得到更大。 

現在，所不同的 這些算法之間 開始變得有點不那麼明顯。 而事實上，有 低階terms--或者說， 低exponents--條款 開始變得無關緊要。 如果數據集是大小 1000和第一算法 運行在一個十億步驟。 和第二算法在運行 一個十億和一百萬的步驟。 而第三個算法運行 在略低於一十億步驟。 這幾乎是一個十億步驟。 那些低階項啟動 要成為真正無關緊要。 而就真的 錘回家的point-- 如果輸入的數據是大小 million--所有這三個幾乎 採取一quintillion--如果 我的數學是correct--步驟 以處理的數據輸入 規模百萬。 這是一個很大的步驟。 而事實上，他們中的一個可能 採取一對夫婦10萬或一對夫婦100 萬元甚至更少的時候 我們談論了許多 這big--它是一種無關緊要的。 他們都傾向於採取 大約ñ立方， 所以我們實際上是指 所有這些算法 作為n的順序上 立方或大，O n立方的。 

下面是一些比較列表 常見的計算複雜性類 我們會遇到 算法，一般。 而在CS50還專門。 這些是從訂購 通常最快在頂部， 到通常最慢的下方。 因此，固定的時間算法往往 是最快的，而不管 的大小的 數據輸入你通過研究。 他們總是需要一個操作或 資源的一個單位來處理。 它可能是2，它可能 是3，它可能是4。 但這是一個常數。 它不改變。 

對數時間算法 是略勝一籌。 而一個真正的好例子 對數時間算法 你一定已經被看到現在是 撕裂電話簿 找到邁克·史密斯在電話簿。 我們切成兩半的問題。 所以，當n變大 和更大和larger-- 其實，每次增加一倍 N，只需要一個步驟。 所以這是好了很多 比說，線性時間。 這是你的兩倍N，它 採取的步驟數量的兩倍。 如果你三倍N，它需要 三倍的步驟的數量。 每單位的一個步驟。 

然後，事情變得有點緩慢 -  從那裡少一點大。 你有線性的節奏，時而 所謂的對數線性時間或只是N日誌ñ。 我們會為例 的算法的那 運行中的n log N，這仍然是更好的 比二次時間 - ñ平方。 或者多項式時間，n兩個 任何數目大於2。 或指數的時間，這 甚至worse-- C到n個。 因此，一些常數提高到 輸入的大小的功率。 所以，如果有1,000--如果 數據輸入是大小1000， 它會採取C到第1,000權力。 這是一個很多比多項式時間差。 

階乘時間更是雪上加霜。 而事實上，也確實 有無限的時間算法， 例如，所謂的愚蠢類別 - 其 工作是隨機洗牌數組 然後檢查 無論是排序。 如果它不是，隨機 再次洗牌陣列 並檢查是否它的排序。 正如你可能imagine-- 你能想像一個情況 其中在最壞的情況下，這種意願 從來沒有真正開始的數組。 該算法將永遠運行。 因此，這將是一個 無限時間的算法。 希望你會不會寫 任何因子或無限的時間 算法CS50。 

那麼，讓我們多了幾分 具體看一些簡單的 計算複雜性類。 因此，我們有一個example-- 兩個例子這裡 -  恆定時間算法， 它始終以 在最壞的情況下，單一的操作。 因此，第一個example-- 我們有一個函數 所謂的4對你來說，這 取大小1000的數組。 但後​​來顯然 實際上不看 在它 - 並不真正關心什麼 裡面那個陣吧。 永遠只是返回四個。 所以，這算法， 儘管事實上，它 需要1000元不 做他們什麼。 剛剛返回四個。 它總是一個步驟。 

其實，加2 nums--這 我們以前作為well--見過 只是處理兩個整數。 這不是一個單一的步驟。 它實際上是一對夫婦的步驟。 你得到了，你就會得到B，你加他們 在一起，你的輸出結果。 因此，這84步。 但是，它總是不斷的， 不管a或b。 你要得到一個，拿到B，加 在一起，輸出其結果。 所以這是一個恆定的時間算法。 

這裡有一個例子 線性時間算法 -  這gets--接受一個算法 一個附加步驟，可能的話， 作為輸入增長了1。 因此，我們說，我們正在尋找 數5內的陣列。 你可能會遇到這樣的情況 你可以找到它相當早。 但你也可以有 的情況下它 可能是該陣列的最後一個元素。 在大小5，數組，如果 我們正在尋找的數字5。 這將需要5個步驟。 而事實上，想像有 不隨地5此數組中。 我們實際上仍然要看看 該陣列的每一個元素 為了確定 無論是否5是存在的。 

因此，在最壞情況下，這是 該元素是最後一個陣列中 或不存在的。 我們還是來看看 所有的n個元素。 因此該算法 以線性時間運行。 您可以確認通過 說外推一點點， 如果我們有一個6-元件陣列和 我們正在尋找5號， 它可能需要6個步驟。 如果我們有一個7-元件陣列和 我們正在尋找的數字5。 這可能需要7個步驟。 當我們增加一個元素，我們的 陣列，它需要一個步驟。 這是一個線性算法 在最壞的情況下。 

夫婦簡單的問題給你。 什麼是runtime--什麼 最壞情況下的運行時 的代碼，這個特殊的片段？ 所以我有一個4環路這裡運行 從第j等於0，一路為m。 而我所看到這裡，是， 循環體運行在固定的時間。 因此，使用術語 我們已經談過about--什麼 將是最壞的情況 該算法的運行時間？ 拿第二。 環路的內側部分 運行在固定的時間。 和的外側部分 迴路將運行的m倍。 那麼什麼是最壞的情況下運行嗎？ 你猜大O m的？ 你是對的。 

要不要再來一個？ 這一次，我們有一個 環路的環路的內側。 我們有一個外環 運行從零到第 我們有一個運行內環 從零到p和的裡面， 予指出，人體的 環在固定時間內運行。 那麼，什麼是最壞情況下的運行時間 的代碼，這個特殊的片段？ 好了，再次，我們有一個 運行P乘以外環。 而且每個時間 - 迭代 該循環，而。 我們有一個內環 也運行P乘以。 然後那裡面，還有的 恆時間 - 小片段存在。 

因此，如果我們有一個外循環 運行P乘以其內部是 內環那 運行p times--是什麼 最壞情況下的運行時 這個代碼片段？ 你猜大O的P平方？ 

我是道格·勞埃德。 這是CS50。