哪裏可以找到O（n^2）和O（n）等的含義？

Question

我一直在注意堆棧溢出的使用這些條款的答案，但我不知道他們的意思。他們叫什麼，有沒有一個很好的資源可以用簡單的術語來解釋它們？

Answer 1

這符號被稱爲Big O notation，並且被用作速記以表達算法複雜性（基本上定algorithim將花費多長時間的輸入大小上運行（n）的增長）

一般來說，你會碰上下列主要類型algorithims的：

1. O（1） - 常量 - 的時間，這需要algorithim完成的長度不依賴於該algorithim必須處理的項目的數目。
2. O（log n） - 對數 - 此算法需要完成的時間長度取決於該算法必須處理的項目數。隨着輸入尺寸變大，每個新輸入需要更少的時間。
3. O（n） - 線性 - 此算法需要完成的時間長度直接取決於該算法必須處理的項目數。隨着輸入規模的增長，所需時間也會相應增長。
4. O（n^2） - Polynominal - 隨着輸入大小的增加，處理輸入所花費的時間越來越大 - 這意味着大輸入大小變得難以解決。
5. O（2^n） - 指數 - 最複雜的問題類型。處理時間根據輸入大小增加到極端程度。

一般來說，您可以通過查看它的使用方式來粗略判斷算法的複雜性。例如，在看下面的方法：

function sum(int[] x) { 
    int sum = 0; 
    for (int i = 0; i < x.length; i++) { 
     sum += x[i]; 
    } 
    return sum; 
} 

有有在這裏做了幾件事情：

• 初始化變量稱爲總和
• 初始化變量叫我
• 對於i的每次迭代：添加x [i]求和，給i加1，檢查我是否小於x。長度
• 返回總和

有，在固定的時間在這裏（前兩個和最後一個）上運行一些操作，因爲x的大小也不會影響他們需要多長時間才能運行。而且，有些操作在線性時間內運行（因爲它們對x中的每個條目運行一次）。隨着大O符號，在algorithim被簡化到最複雜的，所以這筆錢algorithim將在運行爲O（n）

Answer 2

先閱讀Computational Complexity，然後嘗試一些關於像Introduction to Algorithms這樣的算法的書籍。

維基百科頁面：

大O符號根據其增長率表徵功能

如果不將不會鑽到詳細信息您可以經常近似算法複雜度由分析它的代碼：

void simpleFunction(arg); // O(1) - if number of function instructions is constant and don't depend on number of input size 

for (int i=0;i<n;i++) {simpleFunction(element[i]);} // O(n) 

for (int i=0;i<n;i++) { // this one runs O(n^2) 
    for (int j=0;j<n;j++) { 
     simpleFunction(element[i]); 
    } 
} 

for (int i=0;i<n;i*=2) { // O(lgn) 
    simpleFunction(element[i]); 
} 

有時，估計函數/算法的大O表示法複雜性並不那麼簡單h使用amortized analysis。以上代碼只能用作快速入門。

Answer 3

這就是所謂的Big O notation，用來量化算法的複雜性。 （1）表示無論處理多少數據，該算法都需要一個恆定的時間。 O（n）表示算法速度隨着數據量的增加而線性增長。

等等...

所以在O符號n次方越低越好你的算法是要解決的問題。最好的情況是O（1）（n = 0）。但是在許多問題中存在固有的複雜性，因此幾乎在所有情況下都不會找到這樣一種理想的算法。

Answer 4

到目前爲止答案是好的。網頁搜索的主要術語是「大O符號」。

「someformula是O（someterm）」數學背後的基本思想是，隨着變量趨於無窮大，「someterm」是公式的一部分。

例如，假設您有0.05*x^3 + 300*x^2 + 200000000*x + 10。對於非常小的x（x == 1或x == 2），200000000*x將是最大的部分。那時公式的圖表看起來是線性的。隨着你的前進，在某些時候300*x^2部分會更大。然而，如果你繼續讓x更大，就像你關心的那樣大，0.05*x^3部分將是最大的，並且最終將完全超過公式的其他部分。從圖中可以清楚地看到，您正在查看立​​方函數。所以我們會說公式是O(x^3)。