DAA - Metodología de análisis

Para medir el consumo de recursos de un algoritmo, se utilizan diferentes estrategias como se discutió en este capítulo.

Análisis asintótico

El comportamiento asintótico de una función f(n) se refiere al crecimiento de f(n) como n se hace grande.

Normalmente ignoramos pequeños valores de n, ya que generalmente estamos interesados ​​en estimar qué tan lento será el programa en grandes insumos.

Una buena regla general es que cuanto más lenta sea la tasa de crecimiento asintótico, mejor será el algoritmo. Aunque no siempre es cierto.

Por ejemplo, un algoritmo lineal $ f (n) = d * n + k $ siempre es asintóticamente mejor que uno cuadrático, $ f (n) = cn ^ 2 + q $.

Resolver ecuaciones de recurrencia

Una recurrencia es una ecuación o desigualdad que describe una función en términos de su valor en entradas más pequeñas. Las recurrencias se utilizan generalmente en el paradigma de divide y vencerás.

Dejenos considerar T(n) ser el tiempo de ejecución de un problema de tamaño n.

Si el tamaño del problema es lo suficientemente pequeño, diga n < c dónde c es una constante, la solución sencilla toma un tiempo constante, que se escribe como θ(1). Si la división del problema produce varios subproblemas con tamaño $ \ frac {n} {b} $.

Para resolver el problema, el tiempo requerido es a.T(n/b). Si consideramos que el tiempo necesario para la división esD(n) y el tiempo necesario para combinar los resultados de los subproblemas es C(n), la relación de recurrencia se puede representar como -

$$ T (n) = \ begin {cases} \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \: \ theta (1) & if \: n \ leqslant c \\ a T (\ frac {n} {b}) + D (n) + C (n) y de lo contrario \ end { casos} $$

Una relación de recurrencia se puede resolver usando los siguientes métodos:

• Substitution Method - En este método, adivinamos un límite y mediante inducción matemática probamos que nuestra suposición era correcta.

• Recursion Tree Method - En este método, se forma un árbol de recurrencia donde cada nodo representa el costo.

• Master’s Theorem - Esta es otra técnica importante para encontrar la complejidad de una relación de recurrencia.

Análisis amortizado

El análisis amortizado se usa generalmente para ciertos algoritmos donde se realiza una secuencia de operaciones similares.

• El análisis amortizado proporciona un límite al costo real de toda la secuencia, en lugar de limitar el costo de la secuencia de operaciones por separado.

• El análisis amortizado difiere del análisis de casos promedio; la probabilidad no está involucrada en el análisis amortizado. El análisis amortizado garantiza el rendimiento medio de cada operación en el peor de los casos.

No es solo una herramienta de análisis, es una forma de pensar el diseño, ya que diseño y análisis están íntimamente relacionados.

Método agregado

El método agregado ofrece una visión global de un problema. En este método, sin las operaciones toman el peor de los casos T(n)en total. Entonces el costo amortizado de cada operación esT(n)/n. Aunque diferentes operaciones pueden llevar un tiempo diferente, en este método se descuidan los costos variables.

Método contable

En este método, se asignan diferentes cargos a diferentes operaciones de acuerdo con su costo real. Si el costo amortizado de una operación excede su costo real, la diferencia se asigna al objeto como crédito. Este crédito ayuda a pagar operaciones posteriores cuyo costo amortizado sea menor que el costo real.

Si el costo real y el costo amortizado de i^th operación son $ c_ {i} $ y $ \ hat {c_ {l}} $, entonces

$$ \ 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 el trabajo prepago como energía potencial, en lugar de considerar el trabajo prepago como crédito. Esta energía se puede liberar para pagar operaciones futuras.

Si realizamos n operaciones que comienzan con una estructura de datos inicial D₀. Dejenos considerar,c_i como el costo real y D_i como estructura de datos de i^thoperación. La función potencial Ф se asigna a un número real Ф (D_i), el potencial asociado de D_i. El costo amortizado $ \ hat {c_ {l}} $ se puede definir por

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

Por lo tanto, el costo total amortizado es

$$ \ 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}) $ PS

Tabla dinámica

Si el espacio asignado para la mesa no es suficiente, debemos copiar la tabla en una tabla de mayor tamaño. De manera similar, si se borra una gran cantidad de miembros de la tabla, es una buena idea reasignar la tabla con un tamaño más pequeño.

Usando el análisis amortizado, podemos mostrar que el costo amortizado de inserción y eliminación es constante y el espacio no utilizado en una tabla dinámica nunca excede una fracción constante del espacio total.

En el siguiente capítulo de este tutorial, analizaremos brevemente las notaciones asintóticas.