Otra consideración a tener en cuenta a la hora de tratar con la complejidad es que si estamos contando el tiempo que tarda un algoritmo en resolver un problema ¿En qué ordenador lo ejecutamos? Parece obvio que el mismo algoritmo ejecutado en un ordenador el doble de rápido que otro tardará la mitad en encontrar la solución. ¿Cuál debería ser entonces la unidad de medida de la complejidad? Ninguna unidad de tiempo nos vale: ni segundos ni milisegundos, porque el resultado variaría de un ordenador a otro.
Además el mismo algoritmo tardará más o menos en solucionar un problema de una talla u otra. Es decir, no puede tardarse lo mismo en ordenar un array de 100 valores que uno de 100000.
Nos podemos permitir esa simplificación porque lo que realmente queremos saber es cómo crece el número de instrucciones necesarias para resolver el problema con respecto a la talla del problema. Eso es realmente la complejidad.
Por ejemplo, observa ésta función (da igual cuál sea su propósito)
función ejemplo (n: entero): entero
empieza
variables: a, j, k enteros
para j desde 1 hasta n hacer
a=a-1
a=a*2
fin para
devolver a
termina
En este algoritmo hay un par de bucles para que se ejecuten uno después del otro.
Observemos el primer bucle.
Se ejecuta n veces, y en su interior hay una instrucción.
Eso quiere decir que la línea 5 se ejecuta n veces.
Después se ejecuta el segundo bucle, que contiene en su interior dos instrucciones (las de las líneas 8 y 9).
Como ese segundo bucle se ejecuta también n veces y tiene dos instrucciones, se realizan 2n instrucciones.
Finalmente hay una instrucción en la línea 11 que se ejecuta una sola vez.
El número de instrucciones que se ejecutan en total es n + 2n + 1 es decir, 3n + 1
Todavía no hemos llegado al fondo de la cuestión, pero vamos encaminados. Podemos decir que la complejidad de ese algoritmo es 3n + 1, porque ese es el número de instrucciones que hay que realizar para solucionar el problema cuando la talla del problema es n.
La idea que subyace es que podemos saber cómo se comporta el algoritmo conforme la talla del problema va creciendo. En este caso, si se representa 3n + 1 con respecto a n nos daremos cuenta de que esta función es una recta. Para este algoritmo podemos suponer que cuando lo traslademos a un lenguaje de programación concreto sobre un ordenador concreto, si para un n = 100 tarda 7 unidades de tiempo en solucionarlo, con unas pocas operaciones podemos deducir cuántas unidades de tiempo tarda para un n = 1000. Por supuesto, no es un valor exacto, pero lo que nos importa es saber de qué manera aumenta el tiempo con respecto a la talla del problema.
TIEMPO DE EJECUCIÓN DE UN ALGORITMO
Una medida que suele ser útil conocer es el tiempo de ejecución de un programa en función de N, lo que denominaremos T(N). Esta función se puede medir físicamente (ejecutando el programa, reloj en mano), o calcularse sobre el código contando instrucciones a ejecutar y multiplicando por el tiempo requerido por cada instrucción. Así, un trozo sencillo de programa como
S1; for (int i= 0; i < N; i++) S2; requiere T(N)= t1 + t2*N
siendo t1 el tiempo que lleve ejecutar la serie S1 de sentencias, y t2 el que lleve la serie S2.
Prácticamente todos los programas reales incluyen alguna sentencia condicional, haciendo que las sentencias efectivamente ejecutadas dependan de los datos concretos que se le presenten. Esto hace que mas que un valor T(N) debamos hablar de un rango de valores Tmin(N) <= T(N) <= Tmax(N) los extremos son habitualmente conocidos como caso peor y caso mejor. Entre ambos se hallara algún caso promedio o más frecuente. Cualquier fórmula T(N) incluye referencias al parámetro N y a una serie de constantes Ti que dependen de factores externos al algoritmo como pueden ser la calidad del código generado por el compilador y la velocidad de ejecución de instrucciones del ordenador que lo ejecuta. Dado que es fácil cambiar de compilador y que la potencia de los ordenadores crece a un ritmo vertiginoso (en la actualidad, se duplica anualmente), intentaremos analizar los algoritmos con algun nivel de independencia de estos factores; es decir, buscaremos estimaciones generales ampliamente válidas.
COMPLEJIDAD EN ESPACIO
• Es la memoria que utiliza un programa para su ejecución. Lo que implica que la eficiencia en memoria de un algoritmo lo indica la cantidad de espacio requerido para ejecutarlo, es decir, el espacio memoria que ocupan todas las variables propias del algoritmo.
• Es la memoria que utiliza un programa para su ejecución; es decir, el espacio de memoria que ocupan todas las variables propias del algoritmo.
Esta se divide en Memoria Estática y Memoria Dinámica.
• Memoria estática. Para calcularla se suma de memoria que ocupan las variables declaradas en el algoritmo.
• Memoria dinámica. Su cálculo no es tan simple ya que depende de cada ejecución del algoritmo
Ejemplo1: algoritmo de búsqueda en arboles.Función búsqueda_arboles.
Devuelve una solución o fallo.
Inicializa un árbol de búsqueda con estado inicial.
Bucle hacer
- Si no hay candidatos para expandir.
- Entonces devolver fallo.
- En otro caso escoger nodo para expandir.
- Si el nodo es el objetivo.
- Entonces devolver solución.
- En otro caso expandir nodo.
M = profundidad máxima del árbol (puede ser infinita)
D = profundidad de la mejor solución (menor costo)
B = factor de ramificación (numero máximo de sucesiones) = 10
Depth Nodes Time Memory
0 1 1milisecond 100 bytes
2 111 .1 second 11 Kb
4 11111 11 second 1 Mb
6 1000000 18 minutos 111 Mb
Ejemplo2:
Complejidad espacial:
public int getAverage ( int arr[] ) {
int sum = 0;
for (int i = 0; i < arr.length; i++) {
sum += arr[i];
}
return sum / arr.length;
}
En el ejemplo anterior tenemos una función que nos permite obtener el promedio de un arreglo de números.
Como no podemos saber el número de elementos que tiene este arreglo decimos que tiene n elementos int, además tenemos un elemento int (sum)
Utilizando la notación O podemos representar eso de la siguiente manera: O(n+1)
Ahora analicemos el siguiente método:
Public void initMatrix (int mat [ ] [ ] ) {
for ( int i = 0; i < mat.length; i++ ) {
for ( int j = 0; j < mat[i].length; j++) {
mat [ i ][ j ] = 0;
}
}
}