Pular para conteúdo

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) */
    }
}