Analise assintotica

A análise assintótica é uma técnica usada para estudar o comportamento de um algoritmo à medida que o tamanho da entrada cresce, especialmente para entradas grandes. Ela nos ajuda a avaliar a eficiência de um algoritmo em termos de tempo de execução e uso de memória, sem precisar executar o algoritmo para diferentes entradas. A análise assintótica fornece uma forma de expressar o comportamento de longo prazo de um algoritmo, considerando o impacto do aumento do tamanho da entrada.

Principais conceitos

Notação Big O (Grande O)

Representa o limite superior do tempo de execução de um algoritmo no pior caso.

  • Exemplo: O(n2)1: indica que o tempo de execução cresce no máximo o quadrado do tamanho da entrada.

Notação Ω (Ômega)

Representa o limite inferior do tempo de execução no melhor caso.

  • Exemplo: Ω(n) significa que o tempo de execução não será menor que uma função linear do tamanho da entrada.

Notação Θ (Theta)

Representa o limite exato do tempo de execução. Isso significa que o tempo de execução de um algoritmo é limitado tanto superior quanto inferiormente por uma função.

  • Exemplo: Θ(n log(n))1 significa que o tempo de execução é aproximadamente proporcional a n log(⁡n) para grandes entradas.

Notação o (Pequeno o)

Representa um limite superior estrito. Isso significa que o algoritmo cresce mais lentamente do que a função indicada. * Exemplo: o(n2) significa que o algoritmo cresce mais lentamente do que n2 em grandes entradas.

Notação ω (Omega maiúsculo)

Representa um limite inferior estrito. Isso significa que o algoritmo cresce mais rápido do que a função indicada para entradas grandes.

Tipos Comuns de Complexidade Assintótica

  • O(1)1: complexidade constante, o algoritmo não depende do tamanho da entrada (ex.: acessar um elemento de um array).

  • O(log(n))1: complexidade logarítmica, comum em algoritmos de busca binária ou árvores balanceadas.

  • O(n)1: complexidade linear, o algoritmo realiza uma operação para cada elemento de entrada (ex.: busca sequencial).

  • O(n log(n))1: complexidade linear-logarítmica, típica de algoritmos eficientes de ordenação como merge sort e quicksort.

  • O(n2)1: complexidade quadrática, comum em algoritmos de ordenação ineficientes como bubble sort ou insertion sort.

  • O(2n)1: Complexidade exponencial, geralmente vista em algoritmos de força bruta, como resolver o problema da mochila sem otimizações.

Objetivo

A análise assintótica permite comparar a eficiência de diferentes algoritmos sem se preocupar com detalhes específicos de implementação ou hardware. Ela foca em como o algoritmo se comporta à medida que a entrada cresce em tamanho e ajuda a prever o desempenho em casos grandes, que é fundamental para escolher o algoritmo certo para resolver um problema.

  • Considerando dois algoritmos (A e B) para ordenar uma lista:
    • Algoritmo A: O(n log(⁡n));
    • Algoritmo B: O(n2).

Embora o algoritmo A e o algoritmo B possam ter o mesmo desempenho para pequenas entradas, para entradas grandes, o algoritmo A será significativamente mais rápido, pois cresce mais devagar que o algoritmo B.

Resumo:

A análise assintótica é uma ferramenta essencial para entender a eficiência dos algoritmos, permitindo que escolham-se as melhores soluções para problemas complexos em escalas grandes.

Por que assintótica ?

O comportamento assintótico de uma função f(n) descreve como o custo de determinado algoritmo se comporta à medida que n cresce indefinidamente. Na matemática e ciência de computação é importante entender o custo de determinada função/algoritmo para soluções ótimas e com baixo custo computacional.

Exemplo clássico

Vou explicar a análise assintótica de um algoritmo para calcular o número de Fibonacci e fornecer um exemplo de código em C para ilustrar. O algoritmo mais comum para calcular os números de Fibonacci é o algoritmo recursivo simples, que possui uma análise assintótica que pode ser interessante para estudarmos.

Algoritmo Recursivo para o algoritmo Fibonacci:

f(0) = 0 e f(1) = 1
f(n) = f(n − 1) + f(n − 2) 
para  n ≥ 2

Solução em C:

#include <stdio.h>

// Função recursiva para calcular o n-ésimo número de Fibonacci
int fibonacci(int n) {
    if (n <= 1) {
        return n; // Condição inicial: F(0) = 0, F(1) = 1
    } else {
        return fibonacci(n - 1) + fibonacci(n - 2); // Recursão
    }
}

int main() {
    int n;

    // Solicita o número para calcular f(n)
    printf("Digite um número para calcular o Fibonacci: ");
    scanf("%d", &n);

    // Chamada recursiva
    printf("Fibonacci de %d é: %d\n", n, fibonacci(n));

    return 0;
}

Análise Assintótica

Analisando a complexidade do algoritmo recursivo para o calculo do número de Fibonacci e passos para a análise do algoritmo.

  1. Análise da recursão: a função fibonacci(n) faz duas chamadas recursivas para calcular f(n - 1) e n - 2.

    • Estas chamadas geram duas árvores de chamadas recursivas;
  2. Cálculo da complexidade: como podemos perceber a quantidade de chamadas recursivas aumenta de forma rápida a medida que n cresce.

    • Dessa forma temos uma árvore com características semelhantes a um árvore binária, onde cada nó gera dois novos nós para (n − 1) e (n − 2).

    • Percebemos então, que a profundidade da árvore é aproximadamente O(n), e por consequência o número total de nós cresce de forma exponencial.

    • O número de chamadas recursiva é representado por aproximadamente 2n, pois a função faz duas chamadas para cada valor de n, até alcançar os casos base f(0) e f(1).

  3. Podemos então concluir:

    • A complexidade em função do tempo desse algoritmo é exponencial, ou seja, 0(2n), com indicação de que o tempo dobra para cada incremento de n, tornado essa solução ineficiente para n com maiores valores.
    • Exemplo de árvore binária para recursão com n = 4.
graph TB;
    A((4))-->B((3))
    A-->C((2));
    B-->E((3))
    B-->F((2))
    C-->H((1))
    C-->I((0))
    E-->G((1))
    E-->J((0))

Percebemos várias chamadas repetidas (f(3), f(2), f(1),f(0)). Esse fato mostra que a recursão exponencial leva a um grande número de cálculos redundantes.

Como contornar essa fragilidade da recursão exponencial?

Podemos utilizar algumas técnicas para contornar essa ineficiência, como a memoização, a programação dinâmica. Essa técnicas armazenam resultados já calculados de forma a evitar recálculos. Com a utilização dessas técnicas observa-se que a complexidade da solução é reduzida para O(n).

Algoritmo de Fibonacci com Memoização

#include <stdio.h>

// Defini um vetor para armazenar os resultados calculados
#define MAX 1000  // Valor máximo os componente do vetor
int memo[MAX];

// Função para calcular o n-ésimo número de Fibonacci usando memoização
int fibonacci(int n) {
    if (memo[n] != -1) {
        return memo[n];
    }

    if (n <= 1) {
        return n;
    }

    memo[n] = fibonacci(n - 1) + fibonacci(n - 2);
    return memo[n];
}

int main() {
    int n;

    // Inicialização do vetor para armazenar cálculos
    for (int i = 0; i < MAX; i++) {
        memo[i] = -1;
    }

    // Solicita um número
    printf("Digite um número para calcular o Fibonacci: ");
    scanf("%d", &n);

    // Chama a função recursiva com memoização
    printf("Fibonacci de %d é: %d\n", n, fibonacci(n));

    return 0;
}

Análise de Complexidade:

Com a técnica de memoização, a complexidade de tempo do algoritmo de Fibonacci é reduzida para O(n), porque cada número de Fibonacci é calculado apenas uma vez e depois armazenado para reutilização. A complexidade de espaço é também O(n), devido ao armazenamento dos valores no vetor memo.

Algoritmo de Fibonacci com Programação Dinâmica

#include <stdio.h>

// Função para calcular o n-ésimo número de Fibonacci usando programação dinâmica
int fibonacci(int n) {
    if (n <= 1) {
        return n;
    }

    int fib_0 = 0, fib_1 = 1, fib_n;

    // Calcula os números de Fibonacci iterativamente
    for (int i = 2; i <= n; i++) {
        fib_n = fib_0 + fib_1;
        fib_0 = fib_1;
        fib_1 = fib_n;
    }

    return fib_n;
}

int main() {
    int n;

    printf("Digite um número para calcular o Fibonacci: ");
    scanf("%d", &n);

    printf("Fibonacci de %d é: %d\n", n, fibonacci(n));

    return 0;
}

Análise de Complexidade:

  • Tempo: a complexidade de tempo é O(n), já que estamos calculando os números de Fibonacci de 2 até n em uma única iteração.

  • Espaço: a complexidade de espaço é O(1), já que estamos utilizando apenas algumas variáveis para armazenar os dois últimos valores de Fibonacci, independentemente do tamanho de n.

Vantagens

  1. Eficiência: como o algoritmo é iterativo, ele é muito mais eficiente do que a versão recursiva simples (sem memoização). A complexidade é linear, O(n), com uso de espaço constante.

  2. Simples de Implementar: a programação dinâmica é uma abordagem simples e direta para este problema específico de Fibonacci, sem a necessidade de um vetor adicional, como fizemos com a memoização.

Algumas desvantagens da programação dinâmica

  1. Alta complexidade de espaço: em muitos casos, a programação dinâmica pode exigir uma quantidade significativa de memória para armazenar as soluções parciais. Para problemas que envolvem um grande número de subproblemas, o armazenamento de todas as soluções intermediárias pode ser muito dispendioso em termos de memória.

    • Observe o exemplo:

      • O problema da mochila (knapsack problem), a programação dinâmica pode precisar de uma matriz de O(n×W), onde nn é o número de itens e W é a capacidade máxima da mochila. Isso pode ser inviável para valores grandes de n e W.
    • Soluções possíveis: técnicas como programação dinâmica com compressão de espaço podem ser usadas para reduzir o uso de memória em alguns casos, mas isso pode aumentar a complexidade de implementação.

  2. Sobrecarga computacional:

    • Custos computacionais adicionais: a implementação de programação dinâmica geralmente envolve a construção de uma matriz ou estrutura de dados para armazenar as soluções parciais. Esse processo pode adicionar sobrecarga de tempo, especialmente se o problema tiver uma grande quantidade de estados ou subproblemas.

    • Embora a complexidade de tempo geralmente seja melhorada para O(n) ou O(n2) em relação à solução de força bruta (que pode ser exponencial), em problemas com grande número de subproblemas, a tabela de soluções pode ser muito grande, o que implica uma quantidade significativa de tempo e memória.

Considerações das desvantagens da programação dinâmica

  1. Consumo elevado de memória para armazenar soluções parciais.

  2. Sobrecarga de tempo e espaço, especialmente em problemas grandes.

  3. Dificuldade de identificação da estrutura de subproblemas, que é necessária para aplicar a programação dinâmica com sucesso.

  4. Maior complexidade de implementação em comparação com soluções mais simples.

  5. Não é aplicável a todos os problemas; requer a presença de subestruturas ótimas e sobreposição de subproblemas.

Portanto, podemos concluir que a programação dinâmica é uma técnica muito eficiente quando aplicada a problemas onde as variáveis relacionadas aos subproblemas são bem conhecidas. Caso contrário é melhor buscar por abordagem alternativa.

Conclusão

A análise assintótica é uma ferramenta essencial para entender a eficiência dos algoritmos, permitindo que escolham-se as melhores soluções para problemas complexos em grandes escalas.

Apoio

apoio

About

Author