Python - Análisis de algoritmos

Análisis de algoritmos

La eficiencia de un algoritmo se puede analizar en dos etapas diferentes, antes de la implementación y después de la implementación. Son los siguientes:

• A Priori Analysis- Este es un análisis teórico de un algoritmo. La eficiencia de un algoritmo se mide asumiendo que todos los demás factores, por ejemplo, la velocidad del procesador, son constantes y no tienen ningún efecto en la implementación.

• A Posterior Analysis- Este es un análisis empírico de un algoritmo. El algoritmo seleccionado se implementa mediante lenguaje de programación. Esto luego se ejecuta en la computadora de destino. En este análisis, se recopilan estadísticas reales como el tiempo de ejecución y el espacio requerido.

Complejidad del algoritmo

Suponer X es un algoritmo y n es el tamaño de los datos de entrada, el tiempo y el espacio utilizados por el algoritmo X son los dos factores principales que deciden la eficiencia de X.

• Time Factor - El tiempo se mide contando el número de operaciones clave, como comparaciones, en el algoritmo de clasificación.

• Space Factor - El espacio se mide contando el espacio de memoria máximo requerido por el algoritmo.

La complejidad de un algoritmo f(n) da el tiempo de ejecución y / o el espacio de almacenamiento requerido por el algoritmo en términos de n como el tamaño de los datos de entrada.

Complejidad espacial

La complejidad espacial de un algoritmo representa la cantidad de espacio de memoria que requiere el algoritmo en su ciclo de vida. El espacio requerido por un algoritmo es igual a la suma de los siguientes dos componentes:

• Una parte fija que es un espacio requerido para almacenar ciertos datos y variables, que son independientes del tamaño del problema. Por ejemplo, variables simples y constantes utilizadas, tamaño del programa, etc.

• Una parte variable es un espacio requerido por variables, cuyo tamaño depende del tamaño del problema. Por ejemplo, asignación de memoria dinámica, espacio de pila de recursividad, etc.

La complejidad espacial S (P) de cualquier algoritmo P es S (P) = C + SP (I), donde C es la parte fija y S (I) es la parte variable del algoritmo, que depende de la característica de la instancia I. es un ejemplo simple que intenta explicar el concepto -

Algorithm: SUM(A, B)
Step 1 -  START
Step 2 -  C ← A + B + 10
Step 3 -  Stop

Aquí tenemos tres variables A, B y C y una constante. Por lo tanto, S (P) = 1 + 3. Ahora, el espacio depende de los tipos de datos de las variables dadas y los tipos de constantes y se multiplicará en consecuencia.

Complejidad del tiempo

La complejidad temporal de un algoritmo representa la cantidad de tiempo que necesita el algoritmo para ejecutarse hasta su finalización. Los requisitos de tiempo se pueden definir como una función numérica T (n), donde T (n) se puede medir como el número de pasos, siempre que cada paso consuma un tiempo constante.

Por ejemplo, la suma de dos enteros de n bits toma npasos. En consecuencia, el tiempo computacional total es T (n) = c ∗ n, donde c es el tiempo necesario para la suma de dos bits. Aquí, observamos que T (n) crece linealmente a medida que aumenta el tamaño de entrada.