Algoritmos e Estruturas de Dados · 1.º ano (indicativo)
Como determinar a complexidade de um algoritmo?
Resposta curta
Escolha o tamanho da entrada n, conte quantas vezes a operação principal se repete em função de n, mantenha só o termo que mais cresce e ignore as constantes. Um ciclo simples dá O(n), dois ciclos encaixados dão O(n2) e um ciclo que reduz n a metade dá O(log n).
Quando se aplica
A análise de complexidade serve para comparar algoritmos sem depender do computador. Medir segundos depende da máquina, da linguagem e até do que está aberto no sistema. Contar operações em função do tamanho da entrada diz como o tempo cresce quando os dados aumentam: se a lista passar de 1 000 para 2 000 elementos, o algoritmo demora o dobro, o quádruplo ou quase o mesmo?
Pré-requisitos
- Ler código com ciclos (
for,while) e condições. - Saber o que é uma função de n e a noção de logaritmo de base 2: log2 16 = 4, porque 24 = 16.
As classes mais comuns
| Notação | Nome | Exemplo típico |
|---|---|---|
| O(1) | constante | aceder a v[3] |
| O(log n) | logarítmica | pesquisa binária |
| O(n) | linear | percorrer uma lista |
| O(n log n) | linearítmica | merge sort |
| O(n2) | quadrática | dois ciclos encaixados |
| O(2n) | exponencial | testar todos os subconjuntos |
A ordem de crescimento é a da tabela, de cima para baixo.
Método passo a passo
- Defina n: o que cresce (número de elementos, valor de um número, dimensão de uma matriz).
- Escolha a operação principal: a que mais se repete (comparação, soma, troca).
- Conte as repetições em função de n. Ciclos em sequência somam-se; ciclos encaixados multiplicam-se.
- Escreva a expressão exata, por exemplo T(n) = 3n + 2.
- Mantenha o termo dominante (o que cresce mais depressa) e retire as constantes multiplicativas: 3n + 2 passa a O(n).
- Indique o caso: melhor, pior ou médio, se o algoritmo se comporta de forma diferente conforme os dados.
Nota
A notação O(...) dá um limite superior do crescimento. Quando não se diz nada, costuma analisar-se o pior caso.
Exemplos resolvidos
Exemplo 1 — Um ciclo simples
Enunciado: Determine a complexidade de: soma = 0, depois for x in v: soma += x, onde v tem n elementos.
Resolução:
- n = número de elementos de
v. - A operação principal é
soma += x. - O ciclo executa-a exatamente n vezes;
soma = 0executa 1 vez. - T(n) = n + 1.
- O termo dominante é n.
Resposta: O(n). Verificação: com n = 1 000 são cerca de 1 001 operações; com n = 2 000 são cerca de 2 001, o dobro, o que é típico de uma função linear.
Exemplo 2 — Ciclos encaixados
Enunciado: Qual é a complexidade do código seguinte, que compara todos os pares de uma lista de n elementos?
| Linha | Recuo | Código |
|---|---|---|
| 1 | 0 | contador = 0 |
| 2 | 0 | for i in range(n): |
| 3 | 1 | for j in range(n): |
| 4 | 2 | contador += 1 |
Resolução:
- O ciclo exterior repete n vezes.
- Em cada volta, o interior repete n vezes.
- Os ciclos encaixados multiplicam-se: n × n = n2 execuções da linha 4.
- T(n) = n2 + 1.
Resposta: O(n2). Verificação: para n = 10, a linha 4 executa 100 vezes; para n = 20, executa 400, quatro vezes mais para o dobro da entrada.
Exemplo 3 — Ciclo que reduz o problema a metade
Enunciado: Determine a complexidade de while n > 1: n = n // 2, contando as voltas para n = 16.
Resolução:
- n = 16 → 8 (volta 1), 8 → 4 (volta 2), 4 → 2 (volta 3), 2 → 1 (volta 4). Depois n = 1 e o ciclo pára.
- Foram 4 voltas, e 4 = log2 16.
- Em geral, quantas vezes se pode dividir n por 2 até chegar a 1? Cerca de log2 n.
Resposta: O(log n). Verificação: 24 = 16. Para n = 1 024 seriam apenas 10 voltas.
Exemplo 4 — Nível de exame: ciclo triangular e soma de partes
Enunciado: Determine a complexidade do trecho, onde a primeira parte percorre a lista uma vez e a segunda compara cada elemento apenas com os seguintes.
| Linha | Recuo | Código |
|---|---|---|
| 1 | 0 | for i in range(n): |
| 2 | 1 | pass |
| 3 | 0 | for i in range(n): |
| 4 | 1 | for j in range(i + 1, n): |
| 5 | 2 | comparar(v[i], v[j]) |
Resolução:
- Primeiro bloco (linhas 1-2): n repetições.
- Segundo bloco: para i = 0 a linha 5 executa n − 1 vezes; para i = 1, n − 2; … ; para i = n − 1, 0 vezes.
- A soma é (n − 1) + (n − 2) + … + 0 = n(n − 1) / 2 = n2/2 − n/2.
- Total: T(n) = n + n2/2 − n/2. Os blocos em sequência somam-se.
- O termo dominante é n2/2; retirando a constante 1/2, fica n2.
Resposta: O(n2). Verificação: com n = 4, a linha 5 executa 3 + 2 + 1 + 0 = 6 vezes, e 4 × 3 / 2 = 6.
Erros frequentes
- Contar linhas em vez de repetições. Um programa curto pode ser lento; conte quantas vezes cada operação corre.
- Somar quando devia multiplicar (ou ao contrário): ciclos em sequência somam-se, encaixados multiplicam-se.
- Manter constantes e termos menores: O(3n2 + 5n + 2) escreve-se O(n2).
- Ignorar o que cresce: num ciclo
while i < n: i = i * 2o tamanho cresce em potências de 2, logo são log n voltas, não n. - Esquecer o custo de funções chamadas dentro do ciclo. Se cada volta chama uma função que percorre a lista, o custo multiplica.
- Confundir pior caso com caso médio. Na pesquisa linear, o melhor caso é O(1) e o pior é O(n).
Exercícios propostos
1Exercício 1
Indique a complexidade de T(n) = 3n2 + 5n + 2 e calcule T(10).
Ver solução
O termo dominante é 3n2; sem a constante, a complexidade é O(n2). T(10) = 3 × 100 + 5 × 10 + 2 = 300 + 50 + 2 = 352.
2Exercício 2
Dois ciclos seguidos, cada um de 1 a n, com uma operação em cada volta. Qual é a complexidade?
Ver solução
T(n) = n + n = 2n. Em sequência somam-se; a constante 2 desaparece: O(n).
3Exercício 3
Um ciclo externo repete n vezes e, dentro dele, um ciclo interno repete sempre 5 vezes (valor fixo). Qual é a complexidade?
Ver dica
O 5 não depende de n.
Ver solução
Total = n × 5 = 5n, logo O(n). Um ciclo que executa um número fixo de vezes é uma constante.
4Exercício 4
O ciclo i = 1, while i < 64: i = i * 2 quantas voltas dá? Qual é a complexidade em função do limite n?
Ver solução
i toma os valores 1, 2, 4, 8, 16, 32 (todos menores que 64). Em i = 64 pára. São 6 voltas, e 6 = log2 64. Em função do limite n, a complexidade é O(log n).
5Exercício 5
Para n = 1 000, compare o número aproximado de operações de um algoritmo O(n2) com um O(n log n). Quantas vezes é o primeiro maior?
Ver dica
Use log2 1 000 ≈ 10.
Ver solução
O(n2): 1 0002 = 1 000 000. O(n log n): 1 000 × 10 = 10 000 (aproximadamente). A razão é 1 000 000 ÷ 10 000 = 100, ou seja, cerca de 100 vezes mais operações para o algoritmo quadrático.
Perguntas frequentes
Posso ignorar as constantes mesmo que sejam grandes?
Para o crescimento assintótico, sim: um algoritmo de 1 000n é O(n). Mas para valores pequenos de n, uma constante grande pode fazer um algoritmo «mais lento» na teoria ser mais rápido na prática. A notação O descreve o comportamento para n grande.
Qual é a diferença entre O, Ω e Θ?
O dá um limite superior, Ω um limite inferior e Θ um limite justo (superior e inferior ao mesmo tempo). Em muitas aulas usa-se O de forma informal para o pior caso.
Como analiso um algoritmo recursivo?
Escreva a relação de recorrência. Por exemplo, o merge sort satisfaz T(n) = 2T(n/2) + n, que resolve para O(n log n). Depois resolva-a por expansão ou pelo teorema mestre, que vê nos livros de referência.
A complexidade de espaço também conta?
Sim. Mede-se a memória extra necessária em função de n. Um algoritmo pode ser rápido mas gastar muita memória, e a escolha depende do problema.
Resumo
- Complexidade mede como o número de operações cresce com o tamanho n da entrada.
- Ciclos em sequência somam-se; ciclos encaixados multiplicam-se.
- Mantém-se o termo dominante e retiram-se constantes e termos menores.
- Ciclos que dividem ou duplicam a variável dão O(log n).
- Indique o caso analisado: melhor, pior ou médio.
Onde aprofundar
- O programa e o manual da sua cadeira de Algoritmos e Estruturas de Dados.
- Cormen, Leiserson, Rivest e Stein, Introduction to Algorithms, capítulos sobre crescimento de funções e recorrências (confirme a edição).
- Sedgewick e Wayne, Algorithms, na parte de análise de algoritmos.
Continue a estudar
Como implementar o merge sort passo a passo?
O merge sort divide a lista ao meio, ordena cada metade com a própria função (recursão) e depois intercala as duas metades já ordenadas num único resultado ordenado. A…
4 exemplos5 exercícios com solução✓ Estudado