Aula 06
Algoritmos
Complexidade de Algoritmos
Saber que um algoritmo funciona é apenas o começo. Em Estruturas de Dados, também precisamos entender como o custo cresce quando a entrada aumenta. Nesta aula, vamos analisar algoritmos com a Notação Big O, distinguir melhor, pior e caso médio e separar dois recursos fundamentais: tempo de execução e uso de memória.
Como o custo cresce?
Notação Big O
A Notação Big O descreve o crescimento assintótico do custo de um algoritmo conforme o tamanho da entrada, normalmente chamado de n, aumenta. Em vez de medir apenas milissegundos em um computador específico, analisamos como o trabalho escala.
Ideia-chave: Big O não é um cronômetro. Ela abstrai detalhes de hardware,
linguagem e constantes para destacar a ordem de crescimento. Por isso comparamos classes
como
O(1), O(log n), O(n),
O(n log n), O(n²) e O(2ⁿ).
Constante
O trabalho relevante não cresce com n. Exemplo: acessar array[i].
Logarítmica
O espaço de busca é reduzido drasticamente a cada passo. Exemplo: busca binária.
Linear
O trabalho cresce proporcionalmente à quantidade de elementos.
Linearítmica
Comum em algoritmos eficientes de ordenação, como Merge Sort.
Quadrática
Dobrar n pode aproximadamente quadruplicar o trabalho.
Exponencial
Cresce tão rapidamente que pequenas entradas já podem se tornar caras.
Ajuste n para comparar as ordens de crescimento.
Por que ignoramos constantes?
Se um algoritmo executa aproximadamente 3n + 10 operações,
o termo dominante para entradas grandes é n. A constante 3 e o termo 10
afetam o tempo real, mas não mudam a classe de crescimento: O(n).
Por que O(n²) preocupa mais que O(n)?
Para n = 1.000, um crescimento linear fica na ordem de 1.000 unidades de trabalho, enquanto um quadrático chega à ordem de 1.000.000. A diferença aumenta muito com n.
Big O é o tempo exato?
Não. Big O descreve crescimento assintótico e, formalmente, um limite superior. Tempo real também depende de hardware, cache, compilador, linguagem, constantes e características específicas da entrada.
A mesma entrada pode exigir trabalhos diferentes
Melhor, Pior e Caso Médio
O tamanho n não é o único fator relevante. A posição da resposta e a organização dos dados também podem mudar o número de operações. Por isso analisamos diferentes cenários.
Melhor Caso
O cenário mais favorável. Na busca linear, o elemento está na primeira posição.
Caso Médio
O custo esperado segundo uma distribuição de entradas e probabilidades assumidas.
Pior Caso
O cenário de maior trabalho. Na busca linear, o item está no fim ou não existe.
Exemplo: na busca linear em n elementos, o melhor caso exige 1 comparação.
O pior caso pode exigir n comparações. Sob hipóteses usuais, o caso médio continua tendo
crescimento proporcional a n.
A busca começa no índice 0 e verifica uma posição por vez. Observe como a posição do valor altera o número de comparações.
Comparações
0
Escolha um valor para iniciar a simulação.
Melhor caso não define sozinho o algoritmo
A busca linear pode encontrar o primeiro elemento em O(1), mas o mesmo algoritmo pode exigir O(n) no pior caso. Sempre indique qual cenário está sendo analisado.
Por que o pior caso é importante?
Porque fornece uma garantia sobre o máximo crescimento esperado do trabalho, o que é útil quando previsibilidade e limites de desempenho são importantes.
O caso médio é sempre n/2?
Não. Isso depende de quais entradas são consideradas e de suas probabilidades. Uma análise média precisa declarar suas hipóteses.
Algoritmos consomem recursos diferentes
Análise de Tempo e Espaço
Dois algoritmos podem produzir a mesma resposta e ainda ter custos muito diferentes. A complexidade de tempo estima como o trabalho cresce. A complexidade de espaço estima como a memória necessária cresce.
Espaço auxiliar é a memória adicional usada pelo algoritmo além dos dados
de entrada. Uma solução pode ser rápida e consumir mais memória, ou economizar memória
e executar mais trabalho — um clássico time-space tradeoff.
Aumente n e compare algoritmos com perfis diferentes. As barras usam escala logarítmica apenas para permitir visualizar ordens de grandeza muito diferentes no mesmo painel.
Complexidade de tempo
Um laço que percorre n itens é tipicamente O(n). Dois laços dependentes de n frequentemente levam a O(n²). Reduzir o problema pela metade a cada passo pode resultar em O(log n).
Complexidade de espaço
Usar algumas variáveis auxiliares pode ser O(1). Criar uma cópia de todos os n elementos exige O(n) de memória auxiliar. A pilha de chamadas de uma recursão também deve ser considerada.
Troca entre tempo e memória
Algumas técnicas armazenam resultados intermediários para evitar recomputação. Isso pode aumentar o espaço necessário e reduzir muito o tempo de execução.
Aplicação direta na disciplina
Complexidade das Operações em Estruturas de Dados
A escolha de uma estrutura muda o custo das operações. Array, Lista Encadeada e Tabela Hash armazenam dados, mas oferecem compromissos diferentes para acesso, busca, inserção e uso de memória.
| Estrutura | Acesso por índice | Busca | Inserção no início | Inserção no fim | Observação |
|---|---|---|---|---|---|
| Array / Vetor | O(1) | O(n) | O(n) | O(1) amortizado* | Ótima localidade de memória |
| Lista Encadeada | O(n) | O(n) | O(1) | O(1)** | Usa ponteiros entre nós |
| Tabela Hash | não se aplica | O(1) médio | O(1) médio | não se aplica | Pior caso pode chegar a O(n) |
* Array dinâmico: inserir no fim é O(1) amortizado, mas uma realocação
isolada pode custar O(n). ** Lista: inserir no fim é O(1) quando
existe uma referência para a cauda; sem ela, localizar o final custa O(n).
Por que Array acessa índice em O(1)?
Porque o endereço da posição pode ser calculado diretamente a partir do endereço base, do índice e do tamanho do elemento.
Por que Lista Encadeada acessa posição em O(n)?
Porque é necessário começar pelo primeiro nó e seguir ponteiros sucessivamente até alcançar a posição desejada.
Existe uma estrutura sempre melhor?
Não. A escolha depende das operações mais frequentes, volume de dados, restrições de memória e garantias desejadas.
Modelo mental
O Que Você Precisa Guardar
Analisar complexidade é observar como o custo escala. Primeiro identifique n, depois a operação dominante, o cenário considerado e o recurso que está sendo medido.
Para exercícios: defina
n, conte quantas vezes a operação
relevante pode ocorrer, mantenha o termo dominante e diga explicitamente se está
analisando tempo, espaço e qual caso.