Bem-vindo à aula 72! Hoje vamos mergulhar em um dos tópicos mais importantes para quem quer dominar a linguagem C: a análise de complexidade de algoritmos, também conhecida como notação Big O. Se você já se perguntou por que alguns programas rodam em milissegundos enquanto outros travam com entradas grandes, a resposta está na eficiência algorítmica. Nesta aula, você vai entender o que é Big O, como identificar a complexidade de trechos de código em C e por que isso é crucial quando você está lidando com recursos limitados, como em sistemas embarcados ou processamento de alto desempenho.

Dominar Big O não é apenas uma habilidade acadêmica — é uma ferramenta prática que influencia decisões de design desde o início de um projeto. Em C, onde você gerencia memória manualmente e tem acesso direto ao hardware, a escolha do algoritmo certo pode significar a diferença entre um sistema responsivo e um que sofre com gargalos. Vamos construir essa base juntos, com exemplos concretos e análises que você poderá aplicar imediatamente.

O que é

A notação Big O descreve o comportamento assintótico de um algoritmo, ou seja, como o tempo de execução (ou o uso de memória) cresce à medida que o tamanho da entrada (n) aumenta. Ela ignora constantes multiplicativas e termos de menor ordem, focando no termo que domina o crescimento. Por exemplo, se um algoritmo executa 3n^2 + 5n + 10 operações, dizemos que ele é O(n^2), pois o termo quadrático domina para valores grandes de n.

Formalmente, dizemos que f(n) = O(g(n)) se existem constantes positivas c e n0 tais que 0 ≤ f(n) ≤ c * g(n) para todo n ≥ n0. Isso nos dá uma cota superior para o crescimento. Na prática, usamos Big O para comparar algoritmos e prever seu desempenho em entradas grandes.

Vamos ver um exemplo simples em C. Considere uma função que soma os elementos de um vetor:

int soma(int v[], int n) {
    int total = 0;
    for (int i = 0; i < n; i++) {
        total += v[i];
    }
    return total;
}

O loop executa n iterações, e cada iteração faz um número constante de operações. Portanto, a complexidade é O(n). Se dobrarmos o tamanho do vetor, o tempo de execução aproximadamente dobra.

Exemplos comuns

Existem algumas complexidades que aparecem com frequência em algoritmos. Vamos analisá-las com exemplos em C.

  • O(1) — Constante: O tempo não depende do tamanho da entrada. Exemplo: acessar um elemento de um array por índice.
  • O(log n) — Logarítmica: O tempo cresce logaritmicamente. Exemplo: busca binária em um array ordenado.
  • O(n) — Linear: O tempo cresce proporcionalmente à entrada. Exemplo: percorrer um array.
  • O(n log n) — Linearítmica: Comum em algoritmos de ordenação eficientes, como Merge Sort.
  • O(n^2) — Quadrática: Típica de loops aninhados. Exemplo: ordenação por seleção.
  • O(2^n) — Exponencial: Crescimento explosivo, comum em recursão sem otimização, como calcular Fibonacci ingênuo.

Vejamos um exemplo de O(log n) com busca binária:

int busca_binaria(int v[], int n, int alvo) {
    int esq = 0, dir = n - 1;
    while (esq <= dir) {
        int meio = (esq + dir) / 2;
        if (v[meio] == alvo) return meio;
        if (v[meio] < alvo) esq = meio + 1;
        else dir = meio - 1;
    }
    return -1;
}

Em cada iteração, o intervalo de busca é dividido pela metade, então o número de iterações é log2(n), resultando em O(log n).

Um exemplo clássico de O(n^2) é a ordenação por bolha:

void bolha(int v[], int n) {
    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < n - i - 1; j++) {
            if (v[j] > v[j+1]) {
                int temp = v[j];
                v[j] = v[j+1];
                v[j+1] = temp;
            }
        }
    }
}

Os dois loops aninhados executam aproximadamente n^2/2 comparações, então a complexidade é O(n^2).

Por que importa em C

Em C, a eficiência é frequentemente a prioridade máxima. Diferente de linguagens como Python, onde você pode ignorar a complexidade por um tempo, em C você está próximo do hardware e qualquer ineficiência se torna crítica. Por exemplo, em sistemas embarcados com clock limitado, um algoritmo O(n^2) pode inviabilizar um projeto se n for grande.

Além disso, C é usado em áreas como processamento de sinais, gráficos em tempo real, sistemas operacionais e simulações científicas, onde o desempenho é essencial. Dominar Big O permite que você escolha a melhor estrutura de dados e algoritmo desde o início, evitando retrabalho.

Outro ponto: em C, você tem controle sobre a memória, e a complexidade de espaço também importa. Por exemplo, um algoritmo recursivo pode ter complexidade O(n) de espaço devido à pilha de chamadas, enquanto uma versão iterativa usa O(1). Saber analisar isso ajuda a evitar estouro de pilha em sistemas com memória limitada.

Vamos comparar duas implementações de Fibonacci: a recursiva ingênua e a iterativa. A recursiva tem complexidade O(2^n) de tempo, enquanto a iterativa é O(n).

// Recursiva ingênua (O(2^n))
int fib_rec(int n) {
    if (n <= 1) return n;
    return fib_rec(n-1) + fib_rec(n-2);
}

// Iterativa (O(n))
int fib_iter(int n) {
    if (n <= 1) return n;
    int a = 0, b = 1;
    for (int i = 2; i <= n; i++) {
        int temp = a + b;
        a = b;
        b = temp;
    }
    return b;
}

Para n = 40, a versão recursiva pode levar segundos, enquanto a iterativa é instantânea. Isso mostra na prática como a complexidade afeta o desempenho.

Análise prática

Analisar a complexidade de um trecho de código envolve identificar os loops e recursões, e contar quantas vezes as operações principais são executadas. Vamos praticar com alguns exemplos.

Exemplo 1: Loop simples com incremento constante.

for (int i = 0; i < n; i++) {
    printf("%d\n", i);
}

Executa n vezes, então O(n).

Exemplo 2: Loop com passo variável.

for (int i = 1; i < n; i *= 2) {
    printf("%d\n", i);
}

O valor de i dobra a cada iteração, então o número de iterações é log2(n). Complexidade O(log n).

Exemplo 3: Dois loops aninhados independentes.

for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
        printf("(%d,%d)\n", i, j);
    }
}

O loop interno executa n vezes para cada i, totalizando n * n iterações. Complexidade O(n^2).

Exemplo 4: Loops com dependência.

for (int i = 0; i < n; i++) {
    for (int j = i+1; j < n; j++) {
        printf("(%d,%d)\n", i, j);
    }
}

O número de iterações é a soma de 1 a n-1, que é n(n-1)/2, que é O(n^2).

Exemplo 5: Recursão com duas chamadas.

void f(int n) {
    if (n <= 1) return;
    f(n-1);
    f(n-1);
}

A cada chamada, o problema é reduzido em 1, mas são feitas duas chamadas recursivas. Isso gera uma árvore binária de profundidade n, totalizando 2^n chamadas. Complexidade O(2^n).

Para medir na prática, você pode usar a função clock() da biblioteca time.h para cronometrar a execução. Veja um exemplo:

#include <stdio.h>
#include <time.h>

int main() {
    clock_t inicio = clock();
    // chama a função que quer testar
    int resultado = soma(vetor, 1000000);
    clock_t fim = clock();
    double tempo = (double)(fim - inicio) / CLOCKS_PER_SEC;
    printf("Tempo: %f segundos\n", tempo);
    return 0;
}

Lembre-se de compilar com otimizações (-O2 ou -O3) para ter uma medição realista.

Boas práticas e observações finais

Ao analisar algoritmos, alguns cuidados são importantes:

  • Considere o pior caso, o caso médio e o melhor caso. Big O geralmente se refere ao pior caso.
  • Constantes e fatores menores podem importar para entradas pequenas, mas para entradas grandes, a ordem de crescimento domina.
  • Em C, também preste atenção à complexidade de espaço, especialmente ao usar recursão ou alocar memória dinamicamente.
  • Use ferramentas de profiling (como gprof) para identificar gargalos reais, mas a análise teórica ajuda a evitar problemas antes mesmo de codificar.
  • Sempre que possível, prefira algoritmos com complexidade menor, mas considere também a implementação prática e a legibilidade.

Com essas noções, você está pronto para analisar e otimizar código C de forma sistemática.

Referências

Exercícios

  1. Determine a complexidade Big O da seguinte função em C: 
    int funcao(int n) {
    int cont = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < 10; j++) {
            cont++;
        }
    }
    return cont;
}

    ✓ Resposta: O loop externo executa n vezes, e o interno executa 10 vezes (constante). Portanto, o total de iterações é 10n, que é O(n).
  2. Qual é a complexidade da seguinte busca em um array não ordenado? 
    int buscar(int v[], int n, int alvo) {
    for (int i = 0; i < n; i++) {
        if (v[i] == alvo) return i;
    }
    return -1;
}

    ✓ Resposta: No pior caso, o elemento não está presente e o loop percorre todos os n elementos, resultando em O(n).
  3. Analise a complexidade da seguinte função recursiva: 
    int f(int n) {
    if (n <= 1) return 1;
    return f(n-1) + f(n-1);
}

    ✓ Resposta: Cada chamada gera duas novas chamadas, formando uma árvore binária de profundidade n. O número total de chamadas é 2^n - 1, então a complexidade é O(2^n).
  4. Qual a complexidade do seguinte trecho que processa uma matriz? 
    for (int i = 0; i < linhas; i++) {
    for (int j = 0; j < colunas; j++) {
        matriz[i][j] = 0;
    }
}

    ✓ Resposta: Se n for o número total de elementos (linhas × colunas), a complexidade é O(linhas * colunas). Se considerarmos linhas ≈ colunas ≈ n, é O(n^2). Mas se definirmos n como o total de células, é O(n). A resposta mais comum é O(linhas * colunas).
  5. Dado o seguinte algoritmo de ordenação por inserção, qual é a complexidade no pior caso? 
    void insertion_sort(int v[], int n) {
    for (int i = 1; i < n; i++) {
        int chave = v[i];
        int j = i - 1;
        while (j >= 0 && v[j] > chave) {
            v[j+1] = v[j];
            j--;
        }
        v[j+1] = chave;
    }
}

    ✓ Resposta: No pior caso (vetor em ordem decrescente), o loop while executa i vezes para cada i, totalizando 1+2+...+n-1 = O(n^2). Portanto, a complexidade é O(n^2).