⏱️ Análise de Loops

Antes de falar em notações mais formais, vamos aprender a medir o esforço de um algoritmo de forma simples.

A ideia aqui é contar quantas vezes cada parte do código é executada e representar isso como uma expressão em função de n.

Pense nisso como transformar o algoritmo em uma "fórmula de esforço".

A regra de ouro na análise de loops é: quantas vezes o bloco de código será executado em relação ao tamanho da entrada n?

A. O loop simples

Este é o padrão mais comum. O algoritmo percorre a entrada uma única vez.

def sum_elements(items: list) -> int:
    total = 0            # Executa 1 vez
    for num in items:    # Controla n iterações
        total += num     # Executa n vezes
    return total         # Executa 1 vez

Análise

Podemos representar o esforço total como:

1 (inicialização) + n (repetições do loop) + 1 (retorno)

Ou seja:

1 + n + 1

Simplificando:

n + 2

O ponto aqui não é decorar a expressão final, mas entender como o número de execuções depende de n.

Para visualizar esse crescimento, veja o gráfico da função f(n) = n + 2:

B. Loops sequenciais

O que acontece se tivermos dois loops, um depois do outro?

def process_data(items: list) -> None:
    for x in items:
        print(x)

    for y in items:
        print(y)

Análise

O primeiro loop executa n vezes. O segundo também executa n vezes.

Esforço total:

n + n = 2n

Neste momento, ainda estamos interessados na contagem exata.

Para visualizar esse comportamento, veja o gráfico comparando f(n) = n e f(n) = 2n:

C. Loops aninhados

Aqui a escala começa a pesar. Um loop dentro de outro significa que, para cada iteração do primeiro, o segundo roda inteiro.

def compare_all(items: list) -> None:
    for i in items:          # Roda n vezes
        for j in items:      # Roda n vezes para cada i
            print(i, j)

Análise

Para cada uma das n iterações do primeiro loop, o segundo executa n vezes.

Esforço total:

n × n = n²

Se n = 10, temos 100 execuções do bloco interno. Se n = 1.000, saltamos para 1.000.000 execuções.

É por isso que loops aninhados em listas grandes rapidamente podem se tornar caros.

Para visualizar esse crescimento, veja o gráfico da função f(n) = n²:

Um resumo prático

Duas regras aparecem com bastante frequência:

• Se os blocos acontecem um depois do outro, somamos os esforços.
• Se um bloco acontece dentro do outro, multiplicamos os esforços.

Em outras palavras:

• Dois loops separados sobre a mesma entrada costumam gerar algo como n + n.
• Um loop dentro de outro sobre a mesma entrada costuma gerar algo como n × n.

Essa forma de contar execuções é a base para analisar algoritmos com mais segurança. O mais importante é desenvolver o reflexo de olhar para o código e perguntar:

• Quantas vezes este trecho roda?
• O que depende de n?
• Estou somando repetições ou multiplicando repetições?

Nas próximas seções, veremos que, para comparar algoritmos, não precisamos de números exatos como n+2 ou 2n – apenas da ordem de crescimento. Isso nos leva à Notação Big‑O.