CLASE IComplejidad de los Algoritmos

Patricia Espinoza

El análisis de algoritmos proporciona los métodos necesarios para poder comparar distintos algoritmos que resuelven un mismo problema.

El algoritmo se expresa en función del tamaño del problema, al determinar la complejidad estoy midiendo el algoritmo, es decir mientras mas grande más complejo.

¿Qué es la complejidad de un Algoritmo..?

Lo que se entiende por “ analizar un algoritmo“ es medir la cantidad de Tiempo y Espacio que requiere un algoritmo para su ejecución.

En otras palabras, se refiere a preguntarse si es que el algoritmo diseñado es factible de ejecutar en el computador que se dispone. Significa poder predecir el comportamiento del algoritmo antes de llevarlo a un programa .

Complejidad Temporal o Tiempo de ejecución: Tiempo de cómputo necesario para ejecutar algún programa.

Recurso Tiempo: • Aplicaciones informáticas que trabajan “en tiempo real” requieren que los cálculos se realicen en el menor tiempo posible.

• Aplicaciones que manejan un gran volumen de información si no se tratan adecuadamente pueden necesitar tiempos impracticables.

Complejidad Espacial: Memoria que utiliza un programa para su ejecución,

La eficiencia en memoria de un algoritmo indica la cantidad de espacio requerido para ejecutar el algoritmo; es decir, el espacio en memoria que ocupan todas las variables propias al algoritmo.

ESTRUCTURA DE DATOSInternos:Estáticos y Dinámicos

Externos: Bases de Datos, Archivos.

ESTRUCTURA DE DATOS

Las estructuras estáticas son aquellas en las que el tamaño ocupado en memoria, se define con anterioridad a la ejecución del programa que los usa, de forma que su dimensión no puede modificarse durante la misma (matriz), aunque no necesariamente tenga que utilizar toda la memoria reservada al inicio.

Los datos estructurados se pueden clasificar según la variabilidad de su tamaño durante la ejecución del programa en: estáticos y dinámicos

Las estructuras estáticas son aquellas en las que el tamaño ocupado en memoria, se define con anterioridad a la ejecución del programa que los usa, de forma que su dimensión no puede modificarse durante la misma.

Aunque no necesariamente tenga que utilizar toda la memoria reservada al inicio.

Estructura de Datos Dinámicas

No tienen las limitaciones o restricciones en el tamaño de memoria ocupada que son propias de las estructuras estáticas.

Se caracteriza por el hecho de que con un nombre se hace referencia a un grupo de casillas de memoria.  Es decir un dato estructurado tiene varios componentes.

  Lineales       a) Pila        b) Cola       c) Lista No lineales        a) Árboles       b) Grafos

Una medida que suele ser útil conocer es el tiempo de ejecución de un programa en función de N, lo que denota como 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.

TIEMPO DE EJECUCIÓN

El interés principal del análisis de algoritmos radica en saber cómo crece el tiempo de ejecución, cuando el tamaño de la entrada crece.

Esto es la eficiencia asintótica del algoritmo. Se denomina “asintótica” porque analizael comportamiento de las funciones en el límite, es decir, su tasa decrecimiento.

El tiempo que requiere un algoritmo para dar una respuesta, se divide generalmente en 3 casos ¡  Peor Caso: caso más extremo, donde se considera el tiempo máximo para solucionar un problema ¡  Caso promedio: caso en el cual, bajo ciertas restricciones, se realiza un análisis del algoritmo ¡  Mejor caso: caso ideal en el cual el algoritmo tomará el menor tiempo para dar una respuesta

Ante situaciones nuevas o problemas, el que no sabe buscar soluciones se sentirá confuso y angustiado y entonces no busca una estrategia y dará una primera solución para poner punto final a su agonía. El que sabe buscar soluciones, selecciona la estrategia que le parece más cercana a la requerida y hace una hábil adaptación que se ajusta a la nueva demanda.