Complexidade de Algoritmos

A complexidade de algoritmos é uma medida teórica que estima o desempenho de um algoritmo em termos de tempo de execução e uso de memória, com base no tamanho da entrada (geralmente representado por n).

Tipos de Complexidade

• Complexidade de tempo: indica quantas operações um algoritmo realiza à medida que o tamanho da entrada cresce.
• Complexidade de espaço: indica a quantidade de memória que o algoritmo utiliza.

Essas medidas ajudam a prever o comportamento do algoritmo em cenários reais, mesmo antes da implementação.

Notação Big-O

A notação Big-O (O-grande) expressa o crescimento da complexidade de forma simplificada, ignorando constantes e termos de menor ordem. Alguns exemplos comuns:

• \( \mathcal{O}(1) \): tempo constante (independe do tamanho da entrada);
• \( \mathcal{O}(\log n) \): tempo logarítmico (buscas em árvores balanceadas, por exemplo);
• \( \mathcal{O}(n) \): tempo linear (ex.: percorrer um vetor);
• \( \mathcal{O}(n \log n) \): tempo linearitmico (eficiente para ordenações complexas);
• \( \mathcal{O}(n^2) \): tempo quadrático (cresce rapidamente com o tamanho da entrada);
• \( \mathcal{O}(2^n) \): tempo exponencial (ineficiente para entradas grandes).

Exemplos

\( \mathcal{O}(1) \) – Tempo constante:

int retorna_primeiro(int vetor[]) {
    return vetor[0];  // Acesso direto, tempo constante
}

\( \mathcal{O}(\log n) \) – Tempo logarítmico (busca binária):

int busca_binaria(int vetor[], int n, int valor) {
    int inicio = 0, fim = n - 1;
    while (inicio <= fim) {
        int meio = (inicio + fim) / 2;
        if (vetor[meio] == valor) return meio;
        else if (vetor[meio] < valor) inicio = meio + 1;
        else fim = meio - 1;
    }
    return -1;
}

\( \mathcal{O}(n) \) – Tempo linear (varre todo o vetor):

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

\( \mathcal{O}(n \log n) \) - Tempo linearitmico

void mergeSort(int arr[], int l, int r) {
    if (l < r) {
        int m = l + (r - l) / 2;

        // Divisão recursiva do vetor
        mergeSort(arr, l, m);
        mergeSort(arr, m + 1, r);

        // Mescla das metades ordenadas
        merge(arr, l, m, r);
    }
}

\( \mathcal{O}(n^2) \) – Tempo quadrático (duplo for):

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

\( \mathcal{O}(2^n) \) – Tempo exponencial (ex: cálculo de Fibonacci sem otimização):

int fibonacci(int n) {
    if (n <= 1) return n;
    return fibonacci(n - 1) + fibonacci(n - 2);
}

A um custo mínimo de memória pode-se alterar o algoritmo acima para tornar a mesma função de complexidade \( \mathcal{O}(n) \), veja:

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

Nota: este é o objetivo de um engenheiro, fazer com USD 1.00 o que outros fazem com USD 2.00! Mas neste caso específico, o objetivo é reduzir o custo de processamento, que não deixa de ser uma economia 😄!

Importância na Engenharia de Controle e Automação

A análise de complexidade é fundamental para:

• Escolher algoritmos eficientes em sistemas com tempo real ou recursos limitados;
• Prever o comportamento do software em controladores embarcados;
• Otimizar rotinas de leitura de sensores, processamento de sinais e controle de processos;
• Avaliar viabilidade de algoritmos em função do tempo de resposta exigido pelo sistema.

Compreender a complexidade permite ao engenheiro tomar decisões conscientes ao implementar soluções que equilibram desempenho, precisão e uso de recursos.