Comentário: Essa informação foi pincelada no livro
A complexidade de algoritmos pode ser explicada de forma clara ao separar dois aspectos principais: complexidade temporal e complexidade espacial.
Complexidade Temporal
Comentário: Essa informação foi pincelada no livro
É uma forma de medir como o tempo de execução cresce conforme aumentamos o tamanho dos dados de entrada.
Por que é importante? Queremos algoritmos que executem rapidamente, mesmo para entradas grandes.
Como é representada? Geralmente, utilizamos a notação Big-O para descrever o pior caso, como:
- O(1): Tempo constante, independente do tamanho da entrada.
- O(log n): Crescimento logarítmico, comum em algoritmos como busca binária.
- O(n) Crescimento linear, como em iterações simples.
- O(n²): Crescimento quadrático, comum em algoritmos de ordenação ingênuos como o Bubble Sort.
- O(2ⁿ): Crescimento exponencial, encontrado em problemas de força bruta.
- Exemplo prático: Um laço simples que percorre uma lista de tamanho nnn possui complexidade O(n)O(n)O(n):
Complexidade Espacial
Refere-se à quantidade de memória que um algoritmo necessita para executar, também em função do tamanho da entrada (n).
Por que é importante? Em sistemas com restrições de memória, é essencial escolher algoritmos que utilizem espaço de forma eficiente.
Como é representada? Assim como a complexidade temporal, usa-se a notação Notação Big O, como:
- O(1)O(1)O(1): Espaço constante. O algoritmo utiliza uma quantidade fixa de memória.
- O(n)O(n)O(n): Espaço linear. O algoritmo aloca memória proporcional ao tamanho da entrada.
const soma = (a, b) => a + b;
console.log(soma(1, 2)); // 3