BIG O Анализ циклов

Question

Может ли кто-нибудь представить примеры циклов, которые являются PolynomialO O (n^2), экспоненциальными O (2^n) и Factorial O (n1). Кажется, я не обволакиваю голову.

Я понимаю понятия
O (журнал N) 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--).
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++; 
    } 
} 

Это довольно просто, для каждого вложенного цикла вы будете увеличивать свою силу , Так что если у вас было 3 для петель вместо двух, то это было бы O(n^3)

O (2^п):

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

Для каждой итерации этого метода, две другие «ветви» будет создана (до n < = 1), поскольку он имеет два рекурсивных вызова. Таким образом, рост удваивается для каждой итерации.

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) эквивалентен любому O(c^N), где c является константой. В качестве номинальной константы принято использовать e; i, e O(e^N)
2. Вы не можете получить суперполиномиальную сложность с помощью простых вложенных циклов. Вам нужна рекурсия или динамическая структура данных.