Introdução a complexidade e Big-O

Contar a quantidade de operações é difícil, as vezes, é até viável, a ideia é medir ordem de grandeza de quantiade de operações:

Como o total de operações cresce ao longo que o tamanho cresce? Por meio da anotação assintótica.

Dizemos que uma função $f: \mathbb{N} \to \mathbb{N}$ é $O(g(n))$, com $g: \mathbb{N} \to \mathbb{N}$. Se existem constantes $C \in \mathbb{N}_0$ tais que:

\[ f(n) \leq c \cdot g(n), \quad \forall n \geq n_0 \]

Medidas Padrão

$O(1)$ : Constante
$O(\log n)$ : Logarítmico
$O(n \log n)$ : Linearítmico
$O(n^2)$ : Quadrático
$O(n^k)$ : K - Polinomial
$O(k^n)$ : Exponencial
$O(n!)$ : Fatorial

Com isso, os problemas passasm a ser classificados de acordo com a complexidade do melhor algoritmo que o resolve.

Casos de Análise de Complexidade

Acessar o i-ésimo elemento do vetor v:
- $V[i] = O(1)$
- Qual o endereço de memória ocupa v[i]?
  - $Endereço Base + 4 \times i$

Importante olhar para a iteração em sí:

Complexidade: $O(n)$

for(int i = 0; i < n; i++){
    /* O(1) */
}

Complexidade: $O(1)$

for(int i = 0; i < 1000000; i++){
    /* O(1) */
}

Complexidade: $O(n^2)$

for(int i = 0; i < n; i++){
    for(int j = 0; i < n; i++){
        /* O(1)*/
    }
}

Complexidade: $O(n \times m)$

for(int i = 0; i < n; i++){
    for(int j = 0; j < m; j++){
        /* O(1) */
    }
}

Complexidade: $O(n^2)$

for(int i = 0; i < n; i++){
    for(int j = 0; j < i; j++){
        /* O(1) */
    }
}

\[ S = (0 + n-1) \times \frac{n}{2} = \frac{1}{2} n^2 - \frac{1}{2} n \]

Multiplicação de matrizes

\[ C_{ij} = 2_{k=1}^m A_{ik} \cdot B_{kj} \]

Complexidade: $O(n \cdot m \cdot p)$

for(int i = 0; i < n; i++){
    for(int j=0; j < p; j++){
        C[i][j] = 0;
        for(int k = 0; k < m; k++){
            C[i][j] += A[i][k] * B[k][j];
        }
    }
}

Regra geral

A complexidade de um algoritmo é a soma das complexidades de seus blocos não aninhados. Nesse sentido, a complexidade sera aquela do bloco mais caro.

Ex.: $$ O(n) + O(n^2) + O(n^3) = O(n + n^2 + n^3) = O(n^3) $$
Complexidade: $O(\log n)$

for(int i = 1; i < n; i *= 2){
    /* O(1) */
}

Complexidade: $O(n)$

for(int i = 0; i > 0; i /= 2){
    for(int j = 0; j < i; j++){
        /* O(1) */
    }
}