>> 所有的權利，所以，計算複雜度。
只是有點警告 在我們深入太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。