Complexidade de Algoritmos¶

Introdução¶

A complexidade de algoritmos é uma medida de desempenho que busca estimar o tempo e o espaço necessários para executar um algoritmo, em função do tamanho da entrada. Compreender a complexidade ajuda a avaliar a eficiência de algoritmos e a escolher a melhor abordagem para resolver problemas específicos.

Notação assintótica - Big O¶

Para analisar algoritmos, utiliza-se a notação assintótica, que fornece uma forma de expressar a complexidade ignorando detalhes que não afetam o comportamento a longo prazo. As principais notações são:

O - Big O = limite superior do tempo de execução - notação mais comum para expressar o pior caso
Ω - Ômega) = representa o limite inferior - melhor caso
Θ (Theta) = indica o tempo de execução médio - limite superior e inferior são iguais
o = indica que a função de complexidade cresce mais lentamente que a função de referência
ω = indica que a função de complexidade cresce mais rapidamente que a função de referência

Escalas de complexidade¶

As escalas de complexidade comumente encontradas são:

Complexidade	Notação	Descrição	Exemplo
Constante	`O(1)`	tempo de execução não muda com o tamanho da entrada	Execução num tamanho fixo de vezes, como acessar um elemento específico de um array
Linear	`O(n)`	tempo cresce proporcionalmente ao tamanho da entrada	Percorrer todos os elementos de um array, estruturas de repetição
Logarítmica	`O(log n)`	tempo aumenta de forma lenta mesmo para grandes entradas	Algoritmos que dividem o problema em problemas menores - busca binária
Log-linear	`O(n log n)`	tempo de execução cresce de forma proporcional ao tamanho da entrada, multiplicado por um fator logarítmico	Algoritmos que dividem o problema em problemas menores, porém juntando posteriormente - MergeSort, HeapSort, QuickSort
Quadrática	`O(n²)`	tempo cresce rapidamente com o aumento da entrada, comum em algoritmos de ordenação mais simples	BubbleSort, InsertionSort, itens processados em pares
Cúbica	`O(n³)`	Tempo cresce muito rápido com o aumento da entrada, comum em algoritmos que envolvem três loops aninhados	Multiplicação de matrizes utilizando três loops aninhados
Exponencial	`O(2^n)`	o tempo de execução cresce rapidamente, tornando-se inviável para entradas grandes	Resolução de problemas de subconjuntos (Subset Sum), usos de "força bruta" - abordagem simples considerando especificidades de um problema
Fatorial	`O(n!)`	o tempo aumenta drasticamente, sendo utilizado apenas para problemas muito específicos	Problemas de permutação, como o Caixeiro Viajante

Complexidades Constantes¶

complexidade constante - O(1) = tempo de execução de um algoritmo não depende do tamanho da entrada
exemplos
- acessar um elemento específico de um array pelo índice
- verificar uma variável booleana
considerada a melhor complexidade possível
- não importa o tamanho da entrada, o tempo de execução é sempre o mesmo

  int a, b, c; // O(1)
  a = 1; // O(1)
  b = a * 10; // O(1)
  if (a > b) // O(1)
    c = a; // O(1)
  else // O(1)
    c = b; // O(1)

sequência de operações com complexidades constante também possui complexidade constante
O(1) + O(1) = O(1)

Observações¶

objetivo notação O = possibilitar que as constantes que multiplicam a função de tempo sejam ignoradas
não se deve utilizar a notação com soma ou multiplicação de constantes O(2n) ou O(n+1)
funções/métodos próprios da linguagem possuem complexidade especificada na documentação
ignorar as constantes aditivas e multiplicativas
utilizar o termo de maior grau - ressaltar o termo que domina a curva da função
Resumo
- complexidade de algoritmos = mede a eficiência em termos de tempo e espaço
- notação assintótica = ajuda a entender o comportamento a longo prazo de um algoritmo
- escalas de complexidade = variam de O(1) (constante) a O(n!) (fatorial), refletindo diferentes níveis de eficiência
- complexidade constante O(1) é a mais eficiente, pois não depende do tamanho da entrada

Exemplos¶

int funcao(int *vetor, int tam, int valor){
  int i;
  for (i=0; i<valor; i)
    if (vetor[i] == valor)
      return i;
  return -1;
}

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

// n * 1 = O(n)

for (i=0; o <n; i++){
  // O(n2)
}

// n * n2 = O(n3)

for (i=0; o <n; i++){
  // O(n)
}

// n * n = O(n2)

{
  for i(=0; o <n; i++){
    // O(n)
  }
  for i(=0; o <n; i++){
    // O(n2)
  }
}

// O(n2) + O(n3) = O(n3)

{
  for i(=0; o <n; i++){
    // O(n)
  }
  for i(=0; o <n; i++){
    // O(n2)
  }
}

// O (n2) + O(n3) = O(n3)

O(n) * O(n) + O(n) + O(n)

O(n2) + O(n) + O(n)
**O(n2)**