[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ⁿ）算法， 增長最快的類型之一， 你真的會開始注意到經濟放緩 當你開始大量的數據。 

這是漸進複雜度。謝謝。