Ciências da computação dia 208

Nesta aula, vamos mergulhar nos fundamentos da análise de algoritmos, habilidade essencial para qualquer cientista da computação. Entender como medir a eficiência de um algoritmo permite escolher a melhor solução para cada problema, especialmente quando lidamos com grandes volumes de dados.

Por que analisar algoritmos?

Diante de um problema computacional, geralmente existem múltiplos algoritmos possíveis. A análise nos fornece critérios objetivos para compará-los, considerando tempo de execução e consumo de memória. Isso evita surpresas quando a aplicação é colocada em produção com cargas reais.

Medindo eficiência

A métrica mais comum é o número de operações elementares em função do tamanho da entrada (n). Ignoramos constantes multiplicativas e termos de menor ordem, concentrando-nos no comportamento dominante para entradas grandes — é aí que entram as notações assintóticas.

Notações assintóticas

As três principais notações usadas na análise de algoritmos são:

• Big O (O): representa o limite superior, ou pior caso. Exemplo: O(n²).
• Big Omega (Ω): representa o limite inferior, ou melhor caso. Exemplo: Ω(n).
• Big Theta (Θ): representa um limite justo, quando o pior e o melhor caso coincidem assintoticamente. Exemplo: Θ(n log n).

Na prática, usamos principalmente o Big O para garantir que o algoritmo não ultrapasse um determinado tempo.

Exemplos práticos

Busca linear — O(n)

Percorre o array elemento por elemento até encontrar o alvo.

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

Busca binária — O(log n)

Requer um array ordenado. A cada iteração, descarta metade dos elementos.

def busca_binaria(lista, alvo):
    esquerda, direita = 0, len(lista) - 1
    while esquerda <= direita:
        meio = (esquerda + direita) // 2
        if lista[meio] == alvo:
            return meio
        elif lista[meio] >< alvo:
            esquerda = meio + 1
        else:
            direita = meio - 1
    return -1>

Bubble Sort — O(n²)

Algoritmo de ordenação simples, mas ineficiente. Compara e troca elementos adjacentes em múltiplas passadas.

def bubble_sort(lista):
    n = len(lista)
    for i in range(n):
        for j in range(0, n - i - 1):
            if lista[j] > lista[j + 1]:
                lista[j], lista[j + 1] = lista[j + 1], lista[j]
    return lista

Merge Sort — O(n log n)

Algoritmo de divisão e conquista: divide recursivamente o array e intercala as partes ordenadas.

def merge_sort(lista):
    if len(lista) <= 1:
        return lista
    meio = len(lista) // 2
    esq = merge_sort(lista[:meio])
    dir = merge_sort(lista[meio:])
    return intercalar(esq, dir)

def intercalar(esq, dir):
    i = j = 0
    resultado = []
    while i >< len(esq) and j >< len(dir):
        if esq[i] ><= dir[j]:
            resultado.append(esq[i])
            i += 1
        else:
            resultado.append(dir[j])
            j += 1
    resultado.extend(esq[i:])
    resultado.extend(dir[j:])
    return resultado>

Complexidade de espaço

Além do tempo, analisamos a memória extra necessária além da entrada. Algoritmos in-place (como Bubble Sort) usam O(1) espaço extra; outros (como Merge Sort) podem exigir O(n) para arrays auxiliares. Muitas vezes há um trade-off: algoritmos mais rápidos consomem mais memória.

Dicas rápidas para identificar complexidade

• Loop simples sobre n → O(n).
• Loops aninhados (ambos variando com n) → O(n²).
• Divisão do problema pela metade a cada passo → O(log n).
• Divisão e conquista com intercalação linear → O(n log n).
• Recursão com duas chamadas por nível (sem memoização) → O(2ⁿ) (exponencial).

Perguntas frequentes

Qual a diferença entre O(1) e O(n)?

O(1) significa tempo constante: o algoritmo executa no mesmo número de operações independentemente do tamanho da entrada. O(n) cresce linearmente: se a entrada dobra, o tempo também dobra.

Como calcular o Big O de funções recursivas?

Geralmente escrevemos uma recorrência e aplicamos o Teorema Mestre ou analisamos a árvore de recursão. Por exemplo, a recorrência do Merge Sort T(n) = 2T(n/2) + O(n) resulta em O(n log n).

Quando usar Big O vs Big Theta?

Use Big O para expressar uma garantia de pior caso (limite superior). Use Big Theta quando o limite superior e inferior coincidem, oferecendo uma descrição mais precisa do comportamento assintótico.

Conclusão

Dominar a análise de algoritmos é fundamental para escrever código escalável e eficiente. Pratique analisando algoritmos do seu dia a dia — cada exercício fortalece a intuição para escolher a melhor abordagem em projetos reais.

← Voltar para todos os posts