Bem-vindo à primeira parte da nossa série sobre análise e projeto de algoritmos. Aqui no blog, já exploramos diversos tópicos de ciência da computação, e agora vamos mergulhar em um dos pilares fundamentais: os algoritmos. Neste artigo, vamos definir o que é um algoritmo, discutir por que a análise de complexidade é importante, apresentar a notação assintótica, entender recursão e conhecer os principais paradigmas de projeto. Tudo isso no estilo caderno de estudos, direto e prático.

O que são algoritmos?

Um algoritmo é uma sequência finita de passos bem definidos que resolvem um problema. No dia a dia, usamos algoritmos o tempo todo: uma receita de bolo, as instruções de montagem de um móvel, ou o passo a passo para trocar um pneu. Na computação, os algoritmos estão no coração de todo software — desde uma simples função de busca até sistemas complexos de inteligência artificial.

Formalmente, um algoritmo deve ter entradas bem definidas, produzir uma saída, ser finito (terminar após um número finito de passos), ser efetivo (cada passo pode ser executado) e ser determinístico (dada a mesma entrada, produz o mesmo resultado). Essas características garantem que podemos confiar no comportamento do algoritmo.

Análise de algoritmos

Quando temos várias soluções para o mesmo problema, precisamos de uma forma objetiva de compará-las. A análise de algoritmos nos permite medir a eficiência em termos de tempo de execução (complexidade temporal) e uso de memória (complexidade espacial). Normalmente, estamos interessados no comportamento assintótico — o que acontece quando o tamanho da entrada cresce muito.

Dois fatores principais influenciam o tempo de execução: o tamanho da entrada (n) e a eficiência do algoritmo. Um algoritmo que executa em 100n passos é melhor que um que executa em n² passos para valores grandes de n, mesmo que 100 seja uma constante grande. É aí que entra a notação assintótica, que abstrai constantes e termos de menor ordem.

Notação assintótica

As notações mais comuns são:

  • Big O (O): limite superior, descreve o pior caso. Ex: O(n) para busca linear, O(n²) para algoritmos com loops aninhados.
  • Omega (Ω): limite inferior, melhor caso. Ex: Ω(1) para acesso direto em array.
  • Theta (Θ): limite justo, quando o algoritmo executa exatamente na mesma ordem para qualquer entrada. Ex: Θ(n log n) para Merge Sort no pior caso.

A notação Big O é a mais usada na prática. Entender as diferenças entre O(1), O(log n), O(n), O(n log n), O(n²) e O(2ⁿ) é crucial para escolher o algoritmo certo. Por exemplo, algoritmos de ordenação como Merge Sort são O(n log n), enquanto Bubble Sort é O(n²). Para entradas grandes, a diferença é drástica.

Recursão

Recursão é uma técnica onde uma função chama a si mesma para resolver subproblemas menores. Muitos problemas têm uma estrutura recursiva natural: percorrer árvores, calcular fatorial, ou resolver o problema das Torres de Hanói.

A análise de algoritmos recursivos geralmente envolve resolver recorrências. O Teorema Mestre é uma ferramenta poderosa para determinar a complexidade de recorrências comuns da forma T(n) = aT(n/b) + f(n). Por exemplo, o Merge Sort tem recorrência T(n) = 2T(n/2) + O(n), resultando em T(n) = O(n log n).

Principais paradigmas de projeto

Existem várias estratégias para projetar algoritmos. Cada paradigma tem seus pontos fortes e fracos, e a escolha depende do problema e das restrições.

  • Divisão e conquista: quebrar o problema em partes menores, resolver cada parte e combinar. Ex: Merge Sort, Quick Sort.
  • Programação dinâmica: armazenar soluções de subproblemas para evitar recálculo. Ex: problema da mochila, sequência de Fibonacci com memorização.
  • Algoritmos gulosos: tomar a decisão local ótima em cada passo, esperando alcançar o ótimo global. Ex: algoritmo de Dijkstra (menor caminho), algoritmo de Huffman.
  • Busca completa: explorar todas as possibilidades (força bruta). Útil para problemas pequenos ou como baseline.

Exemplos práticos

Vamos ver dois exemplos clássicos que ilustram a diferença de complexidade:

  • Busca linear: percorre o array elemento por elemento. Complexidade O(n).
  • Busca binária: divide o array ordenado pela metade a cada comparação. Complexidade O(log n).

Implementação simplificada em Python:

def busca_linear(arr, alvo):
    for i, val in enumerate(arr):
        if val == alvo:
            return i
    return -1

def busca_binaria(arr, alvo):
    esq, dir = 0, len(arr)-1
    while esq <= dir:
        meio = (esq+dir)//2
        if arr[meio] == alvo:
            return meio
        elif arr[meio] < alvo:
            esq = meio+1
        else:
            dir = meio-1
    return -1

Perceba como a busca binária é muito mais rápida para listas grandes. Teste com uma lista de 1 milhão de elementos: a busca linear pode levar até 1 milhão de comparações, enquanto a binária no máximo 20.

Perguntas frequentes

O que é a notação Big O?

Big O descreve o comportamento de um algoritmo no pior caso, ignorando constantes e termos de menor ordem. É a medida mais comum de eficiência e permite comparar algoritmos de forma independente de hardware.

Qual a diferença entre complexidade de tempo e espaço?

Tempo mede a quantidade de operações (ou passos) que o algoritmo executa; espaço mede a quantidade de memória utilizada (variáveis, pilha de recursão, etc.). Muitas vezes há um trade-off: algoritmos mais rápidos podem usar mais memória e vice-versa.

O que é uma recorrência?

É uma equação que define uma sequência com base em termos anteriores. Surge naturalmente na análise de algoritmos recursivos, como T(n) = T(n-1) + O(1) ou T(n) = 2T(n/2) + O(n).

Como escolher entre programação dinâmica e algoritmo guloso?

Se a escolha local ótima leva sempre à solução ótima global (propriedade da escolha gulosa), um algoritmo guloso pode funcionar e geralmente é mais eficiente. Caso contrário, programação dinâmica é mais segura, mas pode ser mais custosa em tempo e memória.

Onde posso praticar mais?

Confira nossos outros posts na seção Posts e explore as tags para encontrar mais conteúdo sobre algoritmos e ciência da computação.

Esta primeira parte cobriu os fundamentos essenciais. Nas próximas partes, vamos nos aprofundar em cada paradigma com exemplos detalhados e exercícios. Fique de olho no blog!