[Powered by Google Translate] 你可能聽說過人們談論的快速或高效的算法
用於執行特定的任務，
但究竟是什麼，它意味著一種算法要快或效率嗎？
那麼，它不是在談論一個實時測量，
像幾秒鐘或幾分鐘。
這是因為計算機硬件
和軟件的差異很大。
我的程序可能會遇到比你慢，
因為我較舊的計算機上運行它，
或者是因為我恰好是玩在線視頻遊戲
同時，這佔用了我所有的記憶，
我可能會通過不同的軟件運行我的程序
連通的不同的機器在一個低水平。
這就像比較蘋果和桔子。
只是因為我的速度較慢的計算機需要更長的時間
比你給一個答案
並不意味著你有更有效的算法。
>> 所以，既然我們不能直接比較程序的運行時間
以秒或分鐘，
我們應該如何比較2種不同的算法
無論他們的硬件或軟件環境？
要創建一個統一的方法來測量算法的效率，
計算機科學家和數學家們設計
測量程序的漸近複雜性的概念
和符號稱為“大Ohnotation”
用於描述。
正式的定義是，一個函數f（x）的
上運行的順序的g（x）
如果存在一些（x）的值中，x 0和
一些常數，C，
函數f（x）是小於或等於
該常數乘以克（x）的
對於所有的x比x₀。
>> 但是，不要被嚇跑了正式的定義。
這是什麼實際上意味著在更短的理論嗎？
那麼，它基本上是一個方法來分析
程序的運行速度有多快的增長漸近。
也就是說，您輸入的大小增加趨於無窮大，
說，你大小為10的數組排序數組的大小為1000。
你的程序運行時如何成長？
例如，假設計數的字符數
在一個字符串中最簡單的方法
走過整個字符串
信由字母，並加入1到一個計數器，用於每一個字符。
據說該算法以線性時間運行
相對於的字符數，
在字符串中的'N'。
總之，它運行在O（n）的。
這是為什麼？
那麼，使用這種方法，所需的時間
遍歷整個字符串
的字符數成正比。
計數20個字符的字符串中的字符數
是要採取的兩倍長，因為它需要
10個字符的字符串中的字符計數，
因為你必須在所有的字符
每個字符佔用相同數量的時間來看看。
當你增加的字符數，
運行時將輸入長度的增加而線性。
>> 現在，想像一下，如果你決定了線性的時間，
O（N），只為你的速度不夠快嗎？
也許你存儲很大的字符串，
您不能負擔額外的時間，將採取
遍歷所有的字符計數一。
所以，你決定嘗試不同的東西。
如果你會發生在已存儲的字符數
的字符串，例如，在一個變量稱為“LEN”，
早在節目中，
之前，你甚至存儲在字符串中的第一個字符？
然後，所有你現在要做的，找出字符串的長度，
檢查變量的值是什麼。
你不會看在所有的字符串本身，
和訪問的一個變量的值，如長度被認為
漸近穩定的操作，
O（1）。
這是為什麼？好了，記得漸近複雜性意味著什麼。
如何在運行時改變的大小
您輸入的增長呢？
>> 假設你試圖讓一個大字符串中的字符數。
好吧，那就不管你有多大的字符串，
即使是100萬個字符長，
你就必須這樣做，這種方法找到字符串的長度，
是讀出的值的變量的len，
你已經取得的。
輸入長度，也就是你想查找的字符串的長度，
在不影響你的程序運行的速度有多快。
這部分程序的運行速度同樣快一個字符的字符串
一千個字符的字符串，
這就是為什麼這個程序將運行在固定的時間
相對於輸入的大小。
>> 當然，也有一個缺點。
您可以在您的計算機上花費額外的內存空間
存儲變量
和它需要你額外的時間
做實際存儲的變量，
但問題仍然有效，
找出你的字符串多久
不依賴於在所有的字符串的長度。
因此，它運行在O（1）或固定的時間。
這當然不是意味著
您的代碼運行在1步，
但無論有多少個步驟是，
如果它不與輸入的大小，改變
它仍然是漸近常數，表示為O（1）。
>> 正如你可能已經猜到了，
有許多不同的大O的​​運行時間來衡量算法。
O（N）2比O（n）的算法，算法是漸近慢。
那就是，作為元素的數目（n）的增長，
最終O（n）的平方算法將花費更多的時間
比O（n）的算法來運行。
這並不意味著O（n）的算法，運行速度更快
比O（N）2的算法，即使是在同樣的環境下，
在相同的硬件上。
也許對於小輸入大小，
O（n）的平方算法實際上可能工作得更快，
但是，最終，作為輸入的大小增加
趨於無窮大，O（n）的平方算法的運行時間
最終將黯然失色O（n）算法的運行時間。
就像任何二次數學函數
最終將超越任何線性函數，
不管多少頭開始的線性函數開始。
如果你正在使用大量的數據，
運行的算法，在O（N）²時間才能真正結束減慢你的程序，
但對於小輸入大小，
你甚至可能不會注意到。
>> 另外一個漸進的複雜性是，
對數時間，O（log n）的。
運行此快速算法的一個例子
是經典二進制搜索算法，
找到已排序的元素列表中的元素。
>> 如果你不知道什麼樣的二進制搜索，
我會為你解釋得真快。
比方說，你要尋找的3號
在此整數數組。
它著眼於中間的元素的數組
，問道：“是的元素，我希望大於，等於或小於這個嗎？”
如果它是相等的，那麼巨大的。你找到的元素，你就大功告成了。
如果是的，那麼你知道元素
在陣列的右側，
你只能看，在未來，
以及，如果是較小的，那麼你知道它必須是在左側。
然後，這個過程被重複的小尺寸數組
直到找到正確的元素。
>> 這個強大的算法減少一半的數組的大小與每個操作。
因此，要找到一個元素排序的數組的大小為8，
最多（登錄₂8）
或這些操作，
檢查的中間元件，然後切割陣列的一半，將需要
而數組的大小為16需（登錄₂16），
或4個操作。
這只是更多的一倍大小的數組操作。
陣列的大小加倍
增加了運行這段代碼只有1塊。
此外，檢查中間的元素的列表，然後分裂。
因此，它的所述操作，在對數時間，
O（log n）的。
但是等一下，你說，
這不取決於在列表中的元素，你要找的是嗎？
如果你看的第一個元素恰好是正確的嗎？
然後，只需要1操作，
不管有多大的列表。
>> 好了，這就是為什麼計算機科學家有更多的條件
漸近複雜性，這反映在最好的情況下
和最壞情況下的性能的一種算法。
更正確地，上限和下限
在運行時。
二進制搜索在最好的情況下，我們的元素是
有權利在中間，
你得到它在固定的時間，
不管是有多大，其餘的數組。
用於此的符號Ω。
因此，該算法被所述Ω（1）運行。
在最好的情況下，迅速找到該元素，
不管有多大的數組，
但在最壞的情況下，
它有執行（log n）的分裂檢查
的數組中找到合適的元素。
最壞情況下的上界被稱為大“O”你已經知道了。
因此，它是O（log n）的，但Ω（1）。
>> 的線性搜索，相比之下，
在你走過的每一個元素的數組
找到一個你想要的，
是在最好Ω（1）。
同樣，第一個元素你想要的。
所以，它並不重要的數組是多大。
在最壞的情況下，它是在陣列中的最後一個元素。
所以，你必須步行通過所有n個元素的數組中找到它，
想，如果你正在尋找一個3。
因此，它運行在O（n）的時間
因為它是在數組中的元素的數目成比例。
>> 一個符號使用的是Θ。
這可以用來描述算法，算法的最好和最壞的情況下，
是相同的。
在我們前面談到的字符串長度的算法就是這種情況。
也就是說，如果我們將其存儲在一個變量之前
我們存儲的字符串，並在固定的時間稍後訪問。
不管是什麼號
我們存儲在該變量中，我們必須要看看它。
最好的情況是，大家看看吧
並找到的字符串的長度。
因此，Ω（1）或最好的情況下的恆定時間。
最壞的情況是，
大家看看吧，找到的字符串的長度。
所以，O（1），或固定的時間，在最壞的情況下。
因此最好的情況下，最壞的情況下，由於是相同的，
這可以說，運行在Θ（1）的時間。
>> 總之，我們有很好的方法，代碼效率的原因有關
不知道任何事情的真實世界的時間，他們採取的運行，
這是受很多外部因素，
包括不同的硬件，軟件，
或你的代碼的細節。
此外，它可以讓我們原因嘛，會發生什麼事
當輸入的大小增加。
>> 如果你正運行在O（n）的平方算法，
或更糟的，O（2ⁿ）算法，
增長最快的類型之一，
你真的會開始注意到經濟放緩
當你開始大量的數據。
>> 這是漸進複雜度。謝謝。