ループのBIG O分析

Question

誰かが、PolynomialO O（n^2）、指数関数O（2^n）、およびファクターO（n1）であるループの例を提供できますか？私はそれの周りに私の頭を包むように見えることはできません。

Iはfor (int i=0; i<=10; i=i*2) OR for (int i=0; i<=10; i=i/2)
O（N）for (int i=0; i<=10; i++)又は(int i=10; i<=0; i--)（ログn）
Oの概念を理解します。
はO（n^2） `

for (int i=0; i<=10; i++) 
 
{ 
 
    for (int i=0; i<=10; i++) 
 
    { 
 
     //DO SOMETHING 
 
    } 
 
}

Answer 1

はO（n^2）：

int count = 0; 
for (int i = 0; i < n; i++){ 
    for (int j = 0; j < n; j++){ 
    count++; 
    } 
} 

これはあなたがあなたの力を増加させるすべてのネストされたループのために、非常に単純です。あなたは、ループの代わりに、2のための3を持っていたのであれば、それはO(n^3)

O（2^n）は次のようになります。この方法のすべての反復のために

public int fibonacci(int n){ 
    if (n<= 1) return n; 
    return fibonacci(n- 2) + fibonacci(n- 1); 
} 

、他の二つの「枝は」（作成されます。 n < = 1）までは2回の再帰呼び出しがあるためです。だから、すべての反復で成長が倍増する。

はO（n！）：

public int factorialRuntime(int n) { 
    int count = 0; 
    for(int i=0; i<n; i++) { 
    count += factorialRuntime(n-1); 
    } 
    return count; 
} 

この例では、hereから引き出されました。

Answer 2

より明らかO(2^N)例は：

public int count2PowerN(int n) { 
    if (n <= 1) { 
    return n; 
    } else { 
    return count2PowerN(n - 1) + count2PowerN(n - 1); 
    } 
} 

注

1. O(2^N)をcが一定で任意O(c^N)と等価です。公称定数としてeを使用することは慣習的です。 O(e^N)
2. 単純なネストループで超多項式の複雑さを得ることはできません。再帰または動的データ構造のいずれかが必要です。