Estructura De Datos

1.1 Concepto Complejidad Algoritmos

La resolución práctica de un problema exige por una parte un algoritmo o método de resolución y por otra un programa o codificación de aquel en un ordenador real.

Ambos componentes tienen su importancia, pero la del algoritmo es absolutamente esencial, mientras que la codificación puede muchas veces pasar a nivel de anécdota.

A efectos prácticos o ingenieriles, nos deben preocupar los recursos físicos necesarios para que un programa se ejecute.

Aunque puede haber muchos parametros, los mas usuales son el tiempo de ejecución y la cantidad de memoria (espacio).

Ocurre con frecuencia que ambos parametros están fijados por otras razones y se plantea la pregunta inversa: ¿cual es el tamano del mayor problema que puedo resolver en T segundos y/o con M bytes de memoria?

En lo que sigue nos centramos casi siempre en el parametro tiempo de ejecución, si bien las ideas desarrolladas son fácilmente aplicables a otro tipo de recursos.

Para cada problema determinaremos un medida N de su tamaño (por número de datos) e intentaremos hallar respuestas en función de dicho N.

El concepto exacto que mide N depende de la naturaleza del problema.

Así, para un vector se suele utizar como N su longitud; para una matriz, el número de elementos que la componen; para un grafo, puede ser el número de nodos (a veces es mas importante considerar el número de arcos, dependiendo del tipo de problema a resolver), en un archivo se suele usar el número de registros, etc.

Es imposible dar una regla general, pues cada problema tiene su propia lógica de coste.

Tiempo de Ejecución

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 algun “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.

1.2 Aritmética de la notación O.

La notación O (también llamada O mayúscula), se utiliza para comparar la eficiencia de losalgoritmos.

Tipos de análisis de la Notacion O

Peor caso (usualmente)T(n) = Tiempo máximo necesario para un problema de tamaño n.Caso medio (a veces)T(n) = Tiempo esperado para un problema cualquiera de tamaño n.

Requiere establecer una distribución estadística

Mejor caso (engañoso)

 Análisis del peor caso

¿Cuál es el tiempo que necesitaría un algoritmo concreto?

Varía en función del ordenador que utilicemos

Varía en función del compilador que seleccionemos.

Puede variar en función de nuestra habilidad como programadores.

IDEA:Ignorar las constantes dependientes del contexto.SOLUCIÓN:Fijarse en el crecimiento de T(n) cuando n ->∞

NOTACION “O” 

O(g(n)) = { f(n) | Ec,n0 constantes positivas tales que f (n) = c g(n) A n = n0 }En la práctica, se ignoran las constantes y los términos de menor peso:3n3 + 90n2 – 5n + 6046 = O (n3)Eficiencia asintóticaCuando n es lo suficientemente grande…Un algoritmo O (1), es más eficiente que un algoritmo O (log n),Un algoritmo O (log n), es más eficiente que un algoritmo O(n),Un algoritmo O(n), es más eficiente que un algoritmo O(n log n),Un algoritmo O(n log n), es mas eficiente que un algoritmo O (n2),Un algoritmo O (n2), es más eficiente que un algoritmo O(n3),Un algoritmo O (n3), es más eficiente que un algoritmo O (2n).NOTA:En ocasiones, un algoritmo más ineficiente puede resultar másadecuado para resolver unproblema real ya que, en a práctica, hay que tener en cuenta otros aspectos además de laeficiencia.

Propiedades de la notación O 

c O(f(n)) = O(f(n))O (f(n)+g(n)) = max {O (f(n)), O (g(n))}O (f(n)+g(n)) = O (f(n)+g(n))O (f(n)) O (g(n)) = O (f(n) g(n))O(O (f(n))) = O (f(n))

1.3 Complejidad

El análisis de complejidad se basa en la comparación del tipo de ejecución de los algoritmosdesarrollados para resolver un problema.A partir del análisis de complejidad se han definido varias clases de problemas: los problemas quese resuelven en tiempo polinomial por una máquina determinista forman la clase P y los problemasque se resuelven en tiempo polinomial por una máquina no determinista forman la clase NP.En computación, al hablar de complejidad, no se está refiriendo a la dificultad que se tendría paradiseñar un programa, o a lo rebuscado de un algoritmo. La teoría de complejidad tiene que ver condos medidas de desempeño: tiempo y espacio.La complejidad computacional de un problema es una medida de los recursos computacionales(generalmente el tiempo) requeridos para resolver el problema.La complejidad temporal tiene que ver con el tiempo que tarda un programa para ejecutarse. Lacomplejidad espacial estudia la cantidad de espacio de almacenamiento que es necesario para unaoperación.

1.3.1 Tiempo de Ejecución de un Algorítmo

El tiempo de ejecución de un algoritmo, es prioritario cuando este esanalizado.

El tiempo de ejecución de un algoritmo o estructura de datos dependede varios factores relativos al hardware (procesador, reloj, memoria, disco,etc) y el software (sistema operativo, lenguaje, compilador, etc.).

Interesa hallar la dependencia del tiempo de ejecución en función deltamaño de la entrada.

Un método para estudiar el tiempo de ejecución es la experimentación,que tiene limitaciones:1.-Los experimentos se pueden hacer sobre un conjunto limitado deentradas de prueba.2.-Es necesario realizar los experimentos con el mismo hardware ysoftware.3.-Es necesario implementar y ejecutar el algoritmo.

Adicionalmente a la experimentación conviene disponer de un enfoque analítico que:Tome en consideración todas las posibles entradas.Permita evaluar la eficiencia de dos algoritmos de forma independiente del hardware y software.Se pueda realizar estudiando una representación de alto nivel del algoritmo sin necesidad deimplementarlo.

1.3.2 Complejidad en Espacio

Memoria que utiliza un programa para su ejecución, La eficiencia en memoria de un algoritmo indicala cantidad de espacio requerido para ejecutar el algoritmo; es decir, el espacio en memoria queocupan todas las variables propias al algoritmo. Para calcular la memoria estática de un algoritmo sesuma la memoria que ocupan las variables declaradas en el algoritmo. Para el caso de la memoriadinámica, el cálculo no es tan simple ya que, este depende de cada ejecución del algoritmo.

1.4 Selección de un Algorítmo

La selección del mejor algoritmo para el problema dado; en la práctica las cosas no son tan fáciles yen ocasiones no es tan obvio poder escoger un algoritmo entre un grupo, pues la cantidad deoperaciones no siempre es el único criterio a tener en cuenta. También debe considerarse, por ejemplo, el tamaño del algoritmo, la claridad con que está expresado, etc.- Finalidad.-Todo algoritmo tiene el objetivo o una finalidad de resolver un tipo de problema y seejecuta para obtener un resultado que es la solución de un caso particular de ese problema.-

Orden.-Los pasos del algoritmo tienen que ejecutarse en un orden preciso e indicado en elalgoritmo. Si este orden se altera, generalmente no se obtiene el resultado deseado.- Finitud.-El algoritmo tiene que ser finito en tres aspectos:

a).El algoritmo es una secuencia finita de pasos (no tiene sentido ningunoun algoritmo cuya descripción sea infinitamente larga)

b).La ejecución del algoritmo termina después de concluir un númerofinito de pasos Nótese que este aspecto es diferente al anterior, pues podría tenerse una cantidad pequeña de pasos en la definición que se ejecutararepetidamente un número infinito de veces. Por ejemplo: “dividir un númeroracional mayor que 0 por dos repetidamente hasta que el cociente sea cero”.

c).La ejecución de un paso cualquiera del algoritmo tiene que poderejecutarse en un tiempo finito.

2.1 Manejo de Memoria Estatica

La memoria estatica es la que se reserva al momento de compilacion antes de comenzar a ejecutarse el programa. Los objetos son creados en ese momento y destruidos al final del programa. Mantiene la misma de localizacion

...