Algoritmo paralelo: análisis
El análisis de un algoritmo nos ayuda a determinar si el algoritmo es útil o no. Generalmente, un algoritmo se analiza en función de su tiempo de ejecución.(Time Complexity) y la cantidad de espacio (Space Complexity) Requiere.
Dado que tenemos sofisticados dispositivos de memoria disponibles a un costo razonable, el espacio de almacenamiento ya no es un problema. Por lo tanto, no se le da tanta importancia a la complejidad del espacio.
Los algoritmos paralelos están diseñados para mejorar la velocidad de cálculo de una computadora. Para analizar un algoritmo paralelo, normalmente consideramos los siguientes parámetros:
- Complejidad del tiempo (tiempo de ejecución),
- Número total de procesadores utilizados y
- Coste total.
Complejidad del tiempo
La razón principal detrás del desarrollo de algoritmos paralelos fue reducir el tiempo de cálculo de un algoritmo. Por lo tanto, evaluar el tiempo de ejecución de un algoritmo es extremadamente importante para analizar su eficiencia.
El tiempo de ejecución se mide sobre la base del tiempo que tarda el algoritmo en resolver un problema. El tiempo total de ejecución se calcula desde el momento en que el algoritmo comienza a ejecutarse hasta el momento en que se detiene. Si todos los procesadores no inician o finalizan la ejecución al mismo tiempo, entonces el tiempo total de ejecución del algoritmo es el momento en que el primer procesador inició su ejecución hasta el momento en que el último procesador detiene su ejecución.
La complejidad temporal de un algoritmo se puede clasificar en tres categorías:
Worst-case complexity - Cuando la cantidad de tiempo requerida por un algoritmo para una entrada dada es maximum.
Average-case complexity - Cuando la cantidad de tiempo requerida por un algoritmo para una entrada dada es average.
Best-case complexity - Cuando la cantidad de tiempo requerida por un algoritmo para una entrada dada es minimum.
Análisis asintótico
La complejidad o eficiencia de un algoritmo es el número de pasos ejecutados por el algoritmo para obtener el resultado deseado. El análisis asintótico se realiza para calcular la complejidad de un algoritmo en su análisis teórico. En el análisis asintótico, se utiliza una gran longitud de entrada para calcular la función de complejidad del algoritmo.
Note - Asymptotices una condición en la que una línea tiende a encontrarse con una curva, pero no se cruzan. Aquí la línea y la curva son asintóticas entre sí.
La notación asintótica es la forma más sencilla de describir el tiempo de ejecución más rápido y más lento posible para un algoritmo que utiliza límites altos y límites bajos de velocidad. Para ello, utilizamos las siguientes notaciones:
- Notación Big O
- Notación omega
- Notación theta
Notación Big O
En matemáticas, la notación Big O se usa para representar las características asintóticas de las funciones. Representa el comportamiento de una función para grandes entradas en un método simple y preciso. Es un método para representar el límite superior del tiempo de ejecución de un algoritmo. Representa la mayor cantidad de tiempo que podría tardar el algoritmo en completar su ejecución. La función -
f (n) = O (g (n))
si existen constantes positivas c y n0 tal que f(n) ≤ c * g(n) para todos n dónde n ≥ n0.
Notación omega
La notación Omega es un método para representar el límite inferior del tiempo de ejecución de un algoritmo. La función -
f (n) = Ω (g (n))
si existen constantes positivas c y n0 tal que f(n) ≥ c * g(n) para todos n dónde n ≥ n0.
Notación theta
La notación theta es un método para representar tanto el límite inferior como el límite superior del tiempo de ejecución de un algoritmo. La función -
f (n) = θ (g (n))
si existen constantes positivas c1, c2, y n0 tal que c1 * g (n) ≤ f (n) ≤ c2 * g (n) para todos n dónde n ≥ n0.
Aceleración de un algoritmo
El rendimiento de un algoritmo paralelo se determina calculando su speedup. La aceleración se define como la relación entre el tiempo de ejecución del peor caso del algoritmo secuencial más rápido conocido para un problema particular y el tiempo de ejecución del peor caso del algoritmo paralelo.
Número de procesadores utilizados
El número de procesadores utilizados es un factor importante en el análisis de la eficiencia de un algoritmo paralelo. Se calcula el costo de compra, mantenimiento y funcionamiento de las computadoras. Cuanto mayor sea el número de procesadores que utiliza un algoritmo para resolver un problema, más costoso se vuelve el resultado obtenido.
Coste total
El costo total de un algoritmo paralelo es el producto de la complejidad del tiempo y el número de procesadores usados en ese algoritmo en particular.
Costo total = Complejidad de tiempo × Número de procesadores utilizados
Por lo tanto, los efficiency de un algoritmo paralelo es -