top of page

Estrutura de Dados | Notação Big-O

A notação Big-O é uma notação matemática usada para descrever o desempenho ou a complexidade de um algoritmo em termos de tempo ou espaço em relação ao tamanho da entrada do problema. A notação Big-O fornece uma descrição assintótica do comportamento do algoritmo quando o tamanho da entrada se aproxima do infinito. É usada para classificar algoritmos de acordo com a rapidez com que o tempo de execução ou o uso de espaço cresce à medida que o tamanho da entrada aumenta.

Para que serve a Notação Big-O

A notação Big-O é fundamental na análise de algoritmos porque permite:

  1. Comparar Algoritmos: Ajuda a comparar diferentes algoritmos com base em seu desempenho teórico.

  2. Prever Desempenho: Facilita a previsão de como um algoritmo se comportará com grandes entradas.

  3. Identificar Gargalos: Ajuda a identificar partes de um algoritmo que podem ser otimizadas.


Casos de Uso


  1. Ordenação de Arrays:

  • QuickSort: O algoritmo QuickSort tem uma complexidade média de O(nlog⁡n)O(n \log n)O(nlogn). Em casos piores, pode ser O(n2)O(n^2)O(n2), mas isso é raro com a escolha adequada do pivô.

  • MergeSort: O algoritmo MergeSort sempre tem uma complexidade de O(nlog⁡n)O(n \log n)O(nlogn), tornando-o uma escolha estável para ordenação.

  1. Busca em Grafos:

  • Busca em Largura (BFS): A complexidade de tempo do BFS é O(V+E)O(V + E)O(V+E), onde VVV é o número de vértices e EEE é o número de arestas no grafo.

  • Busca em Profundidade (DFS): A complexidade de tempo do DFS também é O(V+E)O(V + E)O(V+E), tornando ambos eficientes para travessia de grafos.

  1. Estruturas de Dados:

  • Árvore Binária de Busca (BST): Operações de busca, inserção e exclusão em uma BST têm complexidade média de O(logn) se a árvore estiver balanceada. No pior caso, a complexidade pode ser O(n) se a árvore estiver desequilibrada.

  • Tabela Hash: Operações de busca, inserção e exclusão em uma tabela hash têm complexidade média de O(1), mas no pior caso, a complexidade pode ser O(n) se houver muitas colisões.


Exemplos de Notações Big-O


  • O(1): Constante – O tempo de execução não depende do tamanho da entrada. Exemplo: acesso a um elemento de array por índice.

  • O(n): Linear – O tempo de execução cresce linearmente com o tamanho da entrada. Exemplo: iteração simples através de um array.

  • O(n2): Quadrático – O tempo de execução cresce proporcionalmente ao quadrado do tamanho da entrada. Exemplo: ordenação por bolha (Bubble Sort).

A notação Big-O é uma ferramenta essencial para qualquer programador ou cientista da computação, pois permite a análise e a compreensão da eficiência dos algoritmos, auxiliando na escolha do mais adequado para resolver um problema específico.

1 visualização0 comentário

Posts recentes

Ver tudo

Comments


bottom of page