DAA - Metodologia de Análise

Para medir o consumo de recursos de um algoritmo, diferentes estratégias são usadas conforme discutido neste capítulo.

Análise Assintótica

O comportamento assintótico de uma função f(n) refere-se ao crescimento de f(n) Como n fica grande.

Normalmente ignoramos pequenos valores de n, uma vez que geralmente estamos interessados ​​em estimar o quão lento o programa será com grandes entradas.

Uma boa regra prática é que quanto mais lenta a taxa de crescimento assintótico, melhor será o algoritmo. Embora nem sempre seja verdade.

Por exemplo, um algoritmo linear $ f (n) = d * n + k $ é sempre assintoticamente melhor do que um quadrático, $ f (n) = cn ^ 2 + q $.

Resolvendo Equações de Recorrência

Uma recorrência é uma equação ou desigualdade que descreve uma função em termos de seu valor em entradas menores. As recorrências são geralmente usadas no paradigma de dividir e conquistar.

Vamos considerar T(n) ser o tempo de execução em um problema de tamanho n.

Se o tamanho do problema for pequeno o suficiente, diga n < c Onde c é uma constante, a solução simples leva um tempo constante, que é escrito como θ(1). Se a divisão do problema resultar em uma série de subproblemas de tamanho $ \ frac {n} {b} $.

Para resolver o problema, o tempo necessário é a.T(n/b). Se considerarmos que o tempo necessário para a divisão éD(n) e o tempo necessário para combinar os resultados dos subproblemas é C(n), a relação de recorrência pode ser representada como -

$$ T (n) = \ begin {cases} \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \ theta (1) & if \: n \ leqslant c \\ a T (\ frac {n} {b}) + D (n) + C (n) & caso contrário \ end { casos} $$

Uma relação de recorrência pode ser resolvida usando os seguintes métodos -

• Substitution Method - Neste método, adivinhamos um limite e, usando a indução matemática, provamos que nossa suposição estava correta.

• Recursion Tree Method - Neste método, uma árvore de recorrência é formada onde cada nó representa o custo.

• Master’s Theorem - Esta é outra técnica importante para encontrar a complexidade de uma relação de recorrência.

Análise Amortizada

A análise amortizada é geralmente usada para certos algoritmos em que uma sequência de operações semelhantes é executada.

• A análise amortizada fornece um limite sobre o custo real de toda a sequência, em vez de limitar o custo da sequência de operações separadamente.

• A análise amortizada difere da análise de caso médio; probabilidade não está envolvida na análise amortizada. A análise amortizada garante o desempenho médio de cada operação no pior caso.

Não é apenas uma ferramenta de análise, é uma forma de pensar o design, uma vez que design e análise estão intimamente relacionados.

Método Agregado

O método agregado fornece uma visão global de um problema. Neste método, sen as operações levam o tempo do pior caso T(n)no total. Então, o custo amortizado de cada operação éT(n)/n. Embora operações diferentes possam levar um tempo diferente, neste método os custos variáveis ​​são negligenciados.

Método de Contabilidade

Neste método, diferentes encargos são atribuídos a diferentes operações de acordo com seu custo real. Se o custo amortizado de uma operação exceder seu custo real, a diferença é atribuída ao objeto como crédito. Este crédito ajuda a pagar por operações posteriores cujo custo amortizado seja inferior ao custo real.

Se o custo real e o custo amortizado de i^th operação são $ c_ {i} $ e $ \ hat {c_ {l}} $, então

$$ \ displaystyle \ sum \ limits_ {i = 1} ^ n \ hat {c_ {l}} \ geqslant \ displaystyle \ sum \ limits_ {i = 1} ^ n c_ {i} $$

Método Potencial

Este método representa o trabalho pré-pago como energia potencial, ao invés de considerar o trabalho pré-pago como crédito. Essa energia pode ser liberada para pagar por operações futuras.

Se realizarmos n operações começando com uma estrutura de dados inicial D₀. Vamos considerar,c_i como o custo real e D_i como estrutura de dados de i^thOperação. A função potencial Ф mapeia para um número real Ф (D_i), o potencial associado de D_i. O custo amortizado $ \ hat {c_ {l}} $ pode ser definido por

$$ \ hat {c_ {l}} = c_ {i} + \ Phi (D_ {i}) - \ Phi (D_ {i-1}) $$

Portanto, o custo amortizado total é

$$ \ displaystyle \ sum \ limits_ {i = 1} ^ n \ hat {c_ {l}} = \ displaystyle \ sum \ limits_ {i = 1} ^ n (c_ {i} + \ Phi (D_ {i} ) - \ Phi (D_ {i-1})) = \ displaystyle \ sum \ limits_ {i = 1} ^ n c_ {i} + \ Phi (D_ {n}) - \ Phi (D_ {0}) $ $

Mesa Dinâmica

Se o espaço alocado para a mesa não for suficiente, devemos copiar a mesa para uma mesa maior. Da mesma forma, se um grande número de membros for apagado da tabela, é uma boa ideia realocar a tabela com um tamanho menor.

Usando a análise amortizada, podemos mostrar que o custo amortizado de inserção e exclusão é constante e o espaço não utilizado em uma tabela dinâmica nunca excede uma fração constante do espaço total.

No próximo capítulo deste tutorial, discutiremos brevemente as Notações Assintóticas.