Complexidade de Algoritmos
Complexidade de Algoritmos para Concursos Públicos
1. Conceitos Básicos
Complexidade de Algoritmos estuda o consumo de recursos (tempo e espaço) de um algoritmo em função do tamanho da entrada (n).
Objetivo: Comparar eficiência entre algoritmos e prever desempenho em cenários reais.
2. Análise Assintótica
Notação Big-O (O): Limite superior do crescimento (pior caso). Ex: O(n²).
Notação Theta (Θ): Limite apertado (caso médio). Ex: Θ(n log n).
Notação Omega (Ω): Limite inferior (melhor caso). Ex: Ω(n).
Concursos frequentemente cobram Big-O.
3. Classes de Complexidade
Constante: O(1) – Operações independentes de n.
Logarítmica: O(log n) – Divisões sucessivas (ex: buscas em árvores).
Linear: O(n) – Percorrer todos os elementos.
Quadrática: O(n²) – Loops aninhados.
Exponencial: O(2ⁿ) – Soluções por força bruta.
4. Complexidade de Algoritmos Clássicos
Busca Linear: O(n) no pior caso.
Busca Binária: O(log n) em vetores ordenados.
Ordenação (Bubble/Insertion/Selection Sort): O(n²).
Merge Sort/Quick Sort: O(n log n) no caso médio.
Dijkstra (com heap): O((V+E) log V).
5. Dicas para Concursos
• Identifique loops aninhados para determinar a complexidade.
• Ignore termos de menor ordem (ex: O(n² + n) = O(n²)).
• Algoritmos recursivos: analise chamadas e árvore de recursão.
• Questões comuns: comparar complexidades ou identificar a notação correta.