快速注意，這幾乎肯定會混淆Big O符号(這是一個上限)與Theta符号(這是一個雙邊界限)。根據我的經驗，這實際上是非學術環境中的典型讨論。對所引起的任何混亂道歉。
使用此圖可以顯示Big O複雜度：
我可以為Big-O表示法給出的最簡單的定義是：
Big-O表示法是算法複雜性的相對表示。
在這句話中有一些重要且刻意選擇的詞：親戚：你隻能比較蘋果和蘋果。您無法将算法與算術乘法進行比較，而是對整數清單進行排序。但是比較兩個算法進行算術運算(一次乘法，一次加法)會告訴你一些有意義的東西;
表示： Big-O(最簡單的形式)減少了算法與單個變量之間的比較。該變量基于觀察或假設來選擇。例如，通常基于比較操作來比較排序算法(比較兩個節點以确定它們的相對排序)。這假設比較昂貴。但是，如果比較便宜但交換費用昂貴呢？它改變了比較; 和
複雜性：如果需要一秒鐘才能對10,000個元素進行排序，那麼我需要多長時間才能排序一百萬個元素？在這種情況下，複雜性是對其他事物的相對衡量。
當你讀完其餘部分後，回過頭來重讀上面的内容。
我能想到的Big-O最好的例子就是做算術。取兩個數字(123456和789012)。我們在學校學到的基本算術運算是：加成;
減法;
乘法; 和
師。
這些都是操作或問題。解決這些問題的方法稱為算法。
增加是最簡單的。您将數字向上排列(向右)并在列中添加數字，在結果中寫入該添加的最後一個數字。該數字的“十”部分将轉移到下一列。
讓我們假設添加這些數字是該算法中最昂貴的操作。按理說，要将這兩個數字加在一起，我們必須将6位數加在一起(并且可能帶有7位數)。如果我們将兩個100位數字加在一起，我們必須做100次加法。如果我們添加兩個 10,000位數字，我們必須進行10,000次添加。
看模式？的複雜性(即操作的次數)正比于數字數量Ñ在較大的數量。我們稱之為O(n)或線性複雜度。
減法是類似的(除了你可能需要借用而不是随身攜帶)。
乘法是不同的。你将數字排成一行，取下面數字中的第一個數字，然後依次将它與頂部數字中的每個數字相乘，依此類推。是以，要将兩個6位數相乘，我們必須進行36次乘法運算。我們可能需要多做10或11列添加才能獲得最終結果。
如果我們有兩個100位數字，我們需要進行10,000次乘法和200次加法。對于兩百萬個數字，我們需要進行一萬億(10 12)次乘法和兩百萬次加法。
當算法按n 平方縮放時，這是O(n 2)或二次複雜度。這是介紹另一個重要概念的好時機：
我們隻關心複雜性中最重要的部分。
精明的人可能已經意識到我們可以将操作次數表示為：n 2 + 2n。但正如你從我們的例子中看到的那樣，每個數字有兩個數字，第二項(2n)變得微不足道(占該階段總運算的0.0002％)。
人們可以注意到我們已經假設了最糟糕的情況。如果其中一個是4位數而另一個是6位數，則乘以6位數字，那麼我們隻有24次乘法。我們仍然計算'n'的最壞情況，即當兩者都是6位數時。是以，Big-O表示法是關于算法的最壞情況
電話簿
我能想到的下一個最好的例子是電話簿，通常稱為白頁或類似的，但它會因國家而異。但我說的是那個按姓氏列出人名，然後是姓名首字母或名字，可能是位址，然後是電話号碼的人。
現在，如果您訓示計算機在包含1,000,000個名字的電話簿中查找“John Smith”的電話号碼，您會怎麼做？忽略一個事實，你可以猜到S的開始有多遠(讓我們假設你不能)，你會做什麼？
一個典型的實作可能是開到中間，拿50萬個，并把它比作“史密斯”。如果恰好是“史密斯，約翰”，我們真的很幸運。更有可能的是，“約翰史密斯”将在該名稱之前或之後。如果是在我們之後，我們将電話簿的後半部分分成兩半并重複。如果是在那之前，我們将電話簿的前半部分分成兩半并重複。等等。
這稱為二進制搜尋，無論您是否意識到，它每天都會在程式設計中使用。
是以，如果您想在一百萬個名字的電話簿中找到一個名字，您最多可以通過這樣做20次來找到任何名稱。在比較搜尋算法時，我們認為這種比較是我們的'n'。對于3個名字的電話簿，它需要進行2次比較(最多)。
對于7最多需要3個。
15歲需要4個。
...
1,000,000需要20。
那是驚人的好不是嗎？
在Big-O術語中，這是O(log n)或對數複雜度。現在，所讨論的對數可以是ln(基數e)，log 10，log 2或其他一些基數。無論如何它仍然是O(log n)就像O(2n 2)和O(100n 2)仍然都是O(n 2)。
在這一點上值得解釋的是Big O可用于通過算法确定三種情況：最佳案例：在電話簿搜尋中，最好的情況是我們在一次比較中找到了名稱。這是O(1)或不變的複雜性 ;
預期案例：如上所述，這是O(log n); 和
最壞情況：這也是O(log n)。
通常我們不關心最好的情況。我們對預期和最壞的情況感興趣。有時這些中的一個或另一個将更重要。
回到電話簿。
如果您有電話号碼并想要找到名字怎麼辦？警方有一本反向電話簿，但這些查詢被公衆拒絕。或者是他們？從技術上講，您可以在普通電話簿中反向查找數字。怎麼樣？
您從名字開始并比較數字。如果它是一場比賽，那麼很棒，如果沒有，你繼續前進。你必須這樣做，因為電話簿是無序的(無論如何通過電話号碼)。
是以要給出一個給出電話号碼的名字(反向查詢)：最佳案例： O(1);
預期案例： O(n)(500,000); 和
最壞情況： O(n)(1,000,000)。
旅行推銷員
這是計算機科學中一個非常着名的問題，值得一提。在這個問題上你有N個城鎮。這些城鎮中的每一個都通過一定距離的道路與一個或多個其他城鎮相連。旅行推銷員的問題是找到通路每個城鎮的最短旅行。
聽起來很簡單？再想想。
如果您有3個城鎮A，B和C，所有城市之間都有道路，那麼您可以去：A→B→C
A→C→B
B→C→A
B→A→C
C→A→B
C→B→A
實際上還不到那個，因為其中一些是等價的(例如，A→B→C和C→B→A是等價的，因為它們使用相同的道路，正好相反)。
實際上有3種可能性。把它帶到4個城鎮，你有(iirc)12種可能性。
5歲就是60歲。
6變為360。
這是稱為階乘的數學運算的函數。基本上：5！= 5×4×3×2×1 = 120
6！= 6×5×4×3×2×1 = 720
7！= 7×6×5×4×3×2×1 = 5040
...
25！= 25×24×...×2×1 = 15,511,210,043,330,985,984,000,000
...
50！= 50×49×...×2×1 = 3.04140932×10 64
是以，旅行商問題的大O是O(n！)或階乘或組合複雜性。
當你到達200個城鎮時，宇宙中沒有足夠的時間來解決傳統計算機的問題。
需要考慮的事情。
多項式時間
我想要快速提及的另一點是，任何具有O(n a)複雜度的算法都被認為具有多項式複雜性或者在多項式時間内是可解的。
O(n)，O(n 2)等都是多項式時間。有些問題在多項式時間内無法解決。是以，世界上使用了某些東西。公鑰加密是一個很好的例子。在計算上很難找到兩個非常大的素數因子。如果不是，我們就無法使用我們使用的公鑰系統。
無論如何，這就是我對Big O(修訂版)的解釋(希望是簡單的英語)。