Em geral, complexidade de tempo e complexidade de espaço são maneiras de medir a eficiência de um algoritmo com base em como seu uso de recursos é dimensionado com o tamanho de sua entrada. Vejamos o básico e alguns exemplos comuns.

Complexidade de tempo

A complexidade do tempo descreve a quantidade de tempo que um algoritmo leva para ser concluído com base no tamanho da entrada (geralmente denotado como n).

1. Tempo constante – O(1):

   • O tempo de execução do algoritmo não muda com o tamanho da entrada.
   • Exemplo: Acessando um elemento em um array por índice, como em arr[5].

2. Tempo logarítmico – O(log n):

   • O tempo de execução do algoritmo cresce logaritmicamente à medida que o tamanho da entrada aumenta, o que significa que ele divide o problema pela metade a cada etapa.
   • Exemplo: pesquisa binária em um array ordenado.

3. Tempo Linear – O(n):

   • O tempo de execução do algoritmo cresce linearmente com o tamanho da entrada.
   • Exemplo: percorrendo uma matriz de n elementos uma vez.

4. Tempo Linearítmico – O(n log n):

   • Comum em algoritmos de classificação eficientes onde cada elemento é tratado logaritmicamente, geralmente devido à divisão recursiva e fusão ou processamento linear.
   • Exemplo: classificação por mesclagem, classificação rápida.

5. Tempo quadrático – O(n²):

   • O tempo de execução cresce proporcionalmente ao quadrado do tamanho da entrada.
   • Exemplo: loops aninhados, como comparar cada elemento em uma matriz com todos os outros elementos.

6. Tempo Cúbico – O(n³):

   • O tempo de execução aumenta com o cubo do tamanho da entrada. Raro, mas pode ocorrer em algoritmos com três loops aninhados.
   • Exemplo: Resolvendo certas operações de matriz usando algoritmos de força bruta.

7. Tempo Exponencial – O(2^n):

   • O tempo de execução dobra com cada elemento adicional na entrada, normalmente a partir de algoritmos recursivos que resolvem subproblemas em todas as combinações possíveis.
   • Exemplo: A solução ingênua para a sequência de Fibonacci, onde cada chamada leva a mais duas chamadas.

8. Tempo fatorial – O(n!):

   • O tempo de execução cresce fatorialmente com o tamanho da entrada. Muitas vezes a partir de algoritmos que envolvem a geração de todas as permutações ou combinações possíveis.
   • Exemplo: Resolvendo o problema do caixeiro viajante com força bruta.

Complexidade Espacial

A complexidade do espaço mede a quantidade de memória que um algoritmo usa em relação ao tamanho da entrada.

1. Espaço Constante – O(1):

   • O algoritmo usa uma quantidade fixa de memória, independentemente do tamanho da entrada.
   • Exemplo: armazenar algumas variáveis, como números inteiros ou contadores.

2. Espaço Logarítmico – O(log n):

   • O uso de memória cresce logaritmicamente, geralmente visto com algoritmos recursivos que reduzem o problema pela metade a cada etapa.
   • Exemplo: pesquisa binária recursiva (complexidade de espaço devido à pilha de chamadas).

3. Espaço Linear – O(n):

   • O uso da memória cresce linearmente com o tamanho da entrada, o que é comum ao criar uma matriz ou estrutura de dados adicional para armazenar a entrada.
   • Exemplo: Criando uma cópia de um array de tamanho n.

4. Espaço Quadrático – O(n²):

   • O uso de memória aumenta com o quadrado do tamanho da entrada, como ao armazenar uma matriz 2D de tamanho n x n.
   • Exemplo: Armazenando uma matriz de adjacência para um grafo com n nós.

5. Espaço Exponencial – O(2^n):

   • O uso da memória cresce exponencialmente com o tamanho da entrada, geralmente em soluções recursivas que armazenam dados para cada subconjunto possível da entrada.
   • Exemplo: Memoização em algoritmos recursivos com muitos subproblemas sobrepostos.

Exemplos práticos

• Tempo Linear (O(n)) e Espaço Linear (O(n)):

  • Uma função que percorre um array e armazena cada elemento em um novo array.

• Tempo quadrático (O(n²)) e espaço constante (O(1)):

  • Uma função que possui dois loops aninhados em uma matriz, mas não requer armazenamento adicional além de algumas variáveis.

Analisando Complexidade

Ao analisar o código quanto à complexidade de tempo e espaço:

1. Identifique os loops: Loops aninhados geralmente aumentam a complexidade (por exemplo, um loop fornece ( O(n) ); dois loops aninhados fornecem ( O(n^2) )).
2. Procure por recursão: chamadas recursivas podem levar a uma complexidade exponencial de tempo e espaço, dependendo do fator de ramificação e da profundidade da recursão.
3. Considere estruturas de dados: o uso de estruturas de dados extras, como matrizes, listas ou mapas hash, pode afetar a complexidade do espaço.

Dicas Gerais

• Complexidade de tempo trata de contar operações em função do tamanho da entrada.
• Complexidade Espacial trata de contar a quantidade de memória extra necessária.

Ao avaliar esses fatores, você pode estimar a eficiência do desempenho de um algoritmo e quanta memória ele consome com base no tamanho da entrada.