Fundamentos

Algoritmos não são avaliados apenas por parecerem funcionar. Precisamos de um modelo de computação, um contrato para o resultado, um argumento de correção e uma forma de descrever o crescimento do uso de recursos.

Objetivos de aprendizado

Após esta seção, você deverá ser capaz de:

• declarar pré-condições e pós-condições;
• usar invariantes de laço para explicar a correção;
• distinguir limites assintóticos superiores, inferiores e justos;
• resolver relações de recorrência comuns; e
• explicar por que a organização da memória pode afetar o desempenho real sem alterar um limite Big-O.

Sequência principal

1. Correção e invariantes
2. Análise assintótica
3. Recursão e recorrências
4. Memória e localidade

Importante

A notação Big-O não é um cronômetro. Ela descreve como o uso de recursos cresce sob um modelo declarado; constantes, distribuições de entrada, alocação, comportamento de cache e otimizações do runtime ainda importam nos programas.