Capítulo 1: Medindo o Caos

Imagine que você está na biblioteca da sua faculdade na véspera da prova final de Cálculo. Você precisa desesperadamente do livro “Cálculo - Volume 1”.

Você chega à seção de matemática e se depara com a seguinte cena de terror: a bibliotecária derrubou os mil livros da estante no chão. Há uma pilha gigantesca, caótica e sem ordem alguma.

Como você encontra o livro que precisa? Você pega o primeiro livro da pilha. É Cálculo? Não. Joga para o lado. Pega o segundo. É Cálculo? Não. Joga para o lado.

Neste exato momento, você está executando um algoritmo. Mais especificamente, uma Busca Linear. Se o seu livro for o último da pilha de mil livros, você terá que olhar os mil livros. Se a pilha tivesse um milhão de livros, você faria um milhão de verificações.

⏳ A Notação Big O

Na Ciência da Computação, nós não medimos a velocidade de um algoritmo em segundos. Segundos são mentirosos. O mesmo código vai rodar muito mais rápido no supercomputador da NASA do que no celular básico que você usa para ler e-mails.

Nós medimos a velocidade pelo crescimento do número de operações. Usamos a notação Big O (ou “Grande O”) para descrever isso de forma padronizada.

O Big O responde a uma única pergunta crucial: O quão rápido o tempo de execução do nosso algoritmo piora à medida que a quantidade de dados (n) aumenta?

As Duas Regras de Ouro

Antes de sairmos classificando todo e qualquer código que vemos pela frente, precisamos concordar em duas regras matemáticas que os cientistas da computação criaram para não enlouquecer:

1. A Regra do Pior Caso: Nós somos programadores pessimistas por natureza. Se você está procurando um nome numa lista telefônica gigantesca, você pode dar a incrível sorte de achar logo na primeira página. Nós ignoramos essa sorte. O Big O sempre olha para o pior cenário possível (o nome estar na última linha da última página).
2. Jogue fora as Constantes e os Termos Menores: Se um algoritmo faz O(2n) operações, nós o chamamos apenas de O(n). Se ele faz O(n² + 5n + 100), nós jogamos todo o lixo fora e o chamamos de O(n²). Conforme o número de itens (n) cresce para bilhões, as constantes e os termos não-dominantes viram poeira matemática. O que importa é a força dominante.

🦍 O Mapa das Complexidades

Aqui está a hierarquia do Big O, da melhor para a pior. Nos próximos subcapítulos, mergulharemos a fundo nas mais comuns do dia a dia.

• \( O(1) \) (Constante): Absolutamente nada muda. O tempo de execução é sempre o mesmo.
• \( O(\log n) \) (Logarítmico): O tempo cresce incrivelmente devagar. O problema é cortado ao meio a cada passo.
• \( O(n) \) (Linear): O tempo cresce na exata mesma proporção que os dados.
• \( O(n \log n) \) (Linearítmico): Comum nos melhores algoritmos de ordenação. Cresce um pouco pior que a linha reta.
• \( O(n^2) \) (Quadrático): O tempo multiplica rapidamente. Um desastre em grandes volumes de dados.
• \( O(2^n) \) (Exponencial): O tempo dobra para cada único item novo. Muito perigoso.
• \( O(n!) \) (Fatorial): Se adicionar alguns poucos itens a mais, o computador congela até o fim dos tempos.

Agora que conhecemos as regras do jogo e mapeamos as complexidades, precisamos aprender a medir isso no código de verdade.

Nos próximos subcapítulos, vamos entrar nos detalhes e ver como essas notações se comportam na prática, desde os cálculos mais simples até o poderoso logaritmo.