Análisis del algoritmo
El análisis de la eficiencia de un algoritmo puede realizarse en dos etapas diferentes, antes de la implementación y después de la implementación, como
Análisis a priori – Se define como análisis teórico de un algoritmo. La eficiencia del 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.
Un análisis posterior – Se define como el análisis empírico de un algoritmo. El algoritmo elegido se implementa utilizando un lenguaje de programación. A continuación, el algoritmo elegido se ejecuta en la máquina del ordenador objetivo. En este análisis, se recogen estadísticas reales como el tiempo de ejecución y el espacio necesario.
El análisis del algoritmo se ocupa del tiempo de ejecución de varias operaciones. El tiempo de ejecución de una operación puede definirse como el número de instrucciones de ordenador ejecutadas por operación.
Complejidad del algoritmo
Supongamos que X se trata como un algoritmo y N se trata como el tamaño de los datos de entrada, el tiempo y el espacio implementados por el algoritmo X son los dos factores principales que determinan la eficiencia de X.
Factor Tiempo – El tiempo se calcula o se mide contando el número de operaciones clave como las comparaciones en el algoritmo de ordenación.
Factor Espacio – El espacio se calcula o se mide contando el espacio máximo de memoria requerido por el algoritmo.
La complejidad de un algoritmo f(N) proporciona el tiempo de ejecución y/o el espacio de almacenamiento que necesita el algoritmo con respecto a N como tamaño de los datos de entrada.
Complejidad espacial
La complejidad espacial de un algoritmo representa la cantidad de espacio de memoria que necesita el algoritmo en su ciclo de vida.
El espacio que necesita un algoritmo es igual a la suma de los dos componentes siguientes
Una parte fija que es un espacio requerido para almacenar ciertos datos y variables (es decir, variables y constantes simples, tamaño del programa, etc.), que no dependen del tamaño del problema.
Una parte variable es un espacio requerido por las variables, cuyo tamaño depende totalmente del tamaño del problema. Por ejemplo, el espacio de la pila de recursión, la asignación de memoria dinámica, etc.
La complejidad espacial S(p) de cualquier algoritmo p es S(p) = A + Sp(I) Donde A se trata como la parte fija y S(I) se trata como la parte variable del algoritmo que depende de la característica de instancia I. A continuación se muestra un ejemplo sencillo que intenta explicar el concepto
Algoritmo
SUM(P, Q)Step 1 - STARTStep 2 - R ← P + Q + 10Step 3 - Stop
Aquí tenemos tres variables P, Q y R y una constante. Por lo tanto S(p) = 1+3. Ahora el espacio depende de los tipos de datos de los tipos de constantes y variables dadas y se multiplicará en consecuencia.
Complejidad temporal
La complejidad temporal de un algoritmo es la representación de la cantidad de tiempo que requiere el algoritmo para ejecutarse hasta su finalización. Los requisitos de tiempo pueden denotarse o definirse como una función numérica t(N), donde t(N) puede medirse como el número de pasos, siempre que cada paso lleve un tiempo constante.
Por ejemplo, en el caso de la suma de dos enteros de n bits, se dan N pasos. En consecuencia, el tiempo total de cálculo es t(N) = c*n, donde c es el tiempo consumido para la suma de dos bits. En este caso, observamos que t(N) crece linealmente a medida que aumenta el tamaño de la entrada.
