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:
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.
-
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;
-
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).
-
-
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
-
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.
-
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
-
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.
-
-
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
-
Consumo elevado de memória para armazenar soluções parciais.
-
Sobrecarga de tempo e espaço, especialmente em problemas grandes.
-
Dificuldade de identificação da estrutura de subproblemas, que é necessária para aplicar a programação dinâmica com sucesso.
-
Maior complexidade de implementação em comparação com soluções mais simples.
-
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
About
Author
- Name: Frederico Sales
- link: https://assintotica.xyz
- e-mail: frederico@fredericosales.eng.br
- slug: analise-assintotica
- date: 2024-11-19