Algoritmos e complexidade: questões para praticar com explicações

1O que a complexidade mede

Um algoritmo é uma lista finita de passos precisos que resolve um problema, como ordenar uma lista ou achar um nome numa lista telefônica.

Dois algoritmos podem resolver o mesmo problema, mas levar tempos muito diferentes. A complexidade descreve como o trabalho cresce quando a entrada aumenta.

O tamanho da entrada se chama n: o número de itens a ordenar, o comprimento de uma lista, o número de nós de um grafo.

Pense em procurar um nome numa lista telefônica de 1000 páginas. Ler todas as páginas leva até 1000 passos. Abri-la no meio e dividir ao meio a cada vez leva cerca de 10 passos.

A complexidade de tempo conta os passos. A complexidade de espaço conta a memória extra. Ambas são escritas como função de n.

Em geral você olha o pior caso: o maior trabalho entre todas as entradas de tamanho n. Às vezes pede-se o caso médio ou o melhor caso.

2Big O e as classes de crescimento

A notação Big O mantém apenas o que importa para n grande. Você descarta fatores constantes e mantém apenas o termo que cresce mais rápido.

Para n = 1000 o termo n² é 3 000 000, enquanto 5n é apenas 5000. Os termos menores quase não alteram o total.

Estas classes aparecem repetidamente, do crescimento mais lento ao mais rápido:

• O(1), constante: ler um elemento de um vetor pelo seu índice.
• O(log n), logarítmica: a busca binária, que divide o problema ao meio a cada passo.
• O(n), linear: uma passada por todos os itens, como achar o maior valor.
• O(n log n): bons algoritmos de ordenação, como o merge sort.
• O(n²), quadrática: dois laços aninhados sobre os itens, como o bubble sort.
• O(2ⁿ), exponencial: testar todos os subconjuntos. Torna-se inutilizável rapidamente.

Big O é um limite superior: o trabalho cresce no máximo tão rápido. Ω (Big Omega) é um limite inferior, e Θ (Theta) é um limite justo, tanto superior quanto inferior.

A base de um logaritmo não importa em Big O, porque logaritmos de bases diferentes diferem apenas por um fator constante.

3Busca, ordenação e recursão

Alguns algoritmos aparecem em quase todo curso. Aprenda as suas complexidades como fatos.

• A busca linear verifica os itens um a um: O(n). A busca binária precisa de um vetor ordenado e divide o intervalo ao meio a cada passo: O(log n).
• O bubble sort, o insertion sort e o selection sort comparam e trocam itens em laços aninhados: O(n²). O insertion sort é O(n) em um vetor que já está ordenado.
• O merge sort divide o vetor em metades, ordena-as e as intercala: O(n log n) em todos os casos, com O(n) de memória extra.
• O quicksort divide em torno de um pivô: O(n log n) em média, mas O(n²) no pior caso, por exemplo um vetor ordenado com o primeiro elemento como pivô.
• Nenhuma ordenação que apenas compara itens consegue superar Ω(n log n) no pior caso. O counting sort é mais rápido porque não compara.

Uma função recursiva chama a si mesma com uma entrada menor até chegar a um caso base que ela responde diretamente. Seu tempo de execução é escrito como uma recorrência:

• T(n) = T(n/2) + O(1) dá O(log n), como a busca binária.
• T(n) = 2T(n/2) + O(n) dá O(n log n), como o merge sort.
• T(n) = T(n − 1) + O(n) dá O(n²).
• T(n) = 2T(n − 1) + O(1) dá O(2ⁿ).

Vale conhecer três ideias de projeto. Dividir e conquistar divide, resolve e combina. O método guloso escolhe a melhor opção local a cada passo. A programação dinâmica guarda as respostas de subproblemas sobrepostos para que sejam calculadas uma só vez.

4O método passo a passo

Para encontrar a complexidade de tempo de um trecho de código:

1. Decida o que é n: o tamanho da entrada.
2. Conte quantas vezes cada laço executa. Um laço que soma 1 a cada vez executa cerca de n vezes. Um laço que dobra ou divide ao meio executa cerca de log₂ n vezes.
3. Laços um dentro do outro se multiplicam. Laços um após o outro se somam.
4. Para uma função recursiva, escreva a recorrência: quantas chamadas, com que tamanho, mais o trabalho por chamada.
5. Mantenha o termo que cresce mais rápido e descarte as constantes.
6. Verifique com um número pequeno, por exemplo n = 8 ou n = 1024.

Para uma questão teórica, primeiro nomeie o algoritmo ou a ideia que ela descreve e depois recorde a sua complexidade e as suas condições (entrada ordenada, pesos não negativos, subproblemas sobrepostos).

5Um exemplo resolvido

Acompanhe cada passo. Tente prever o próximo antes de abri-lo.

6Erros comuns

• Multiplicar laços que executam um após o outro. n + n = 2n continua sendo O(n).
• Manter constantes, como em O(2n) ou O(n/2). Ambos são O(n).
• Contar um laço que dobra como n voltas. Ele executa cerca de log₂ n vezes.
• Usar busca binária em dados não ordenados, ou em uma lista encadeada em que o meio não pode ser alcançado em um passo.
• Dar o caso médio do quicksort quando o pior caso é pedido.
• Pensar que Big O significa “exatamente”. O(n²) é um limite superior; Θ(n²) é o crescimento exato.

7Como são as questões de prova

• Fácil: termos e fatos-chave. A complexidade da busca binária, do merge sort ou do acesso a um vetor, o significado de O, Ω e Θ, o que é recursão.
• Médio: aplicação dos conceitos. A complexidade de um trecho de código, uma recorrência para resolver, como o tempo muda quando n dobra, qual algoritmo serve para uma tarefa.
• Difícil: casos e análise. O teorema mestre, os piores casos do quicksort, guloso versus programação dinâmica e as classes P, NP e NP-completo.

P contém os problemas que podem ser resolvidos em tempo polinomial. NP contém os problemas cujas soluções podem ser verificadas em tempo polinomial. Todo problema de P está em NP; se P = NP ainda é desconhecido.