Complexidade e Notação Big O

Prévia do material em texto

Complexidade de Algoritmos e Notação Big O
Ficha de estudo original • Ciência da Computação / TI
Conceitos essenciais
• A análise de complexidade estima como o custo de um algoritmo cresce com o tamanho da entrada. Big O descreve um limite assintótico superior e é muito usada para comparar escalabilidade.
• O(1) indica custo constante; O(log n), crescimento lento; O(n), crescimento linear; O(n log n), comum em boas ordenações; O(n²), típico de dois laços aninhados sobre a mesma entrada.
• Complexidade de tempo e de espaço são analisadas separadamente. Um algoritmo pode economizar tempo usando mais memória, ou o contrário.
• Constantes e termos de menor ordem são omitidos na notação assintótica: 3n + 10 é O(n).
	Exemplo prático: Exemplo: buscar um item em lista não ordenada é O(n); em vetor ordenado, a busca binária é O(log n).
Revisão rápida
1. O que Big O representa?
2. Por que O(n log n) costuma ser melhor que O(n²)?
3. Qual a complexidade da busca binária?
Material autoral para estudo e revisão. Revise o tema em exercícios práticos para consolidar o conteúdo.