Unidad VII ANÁLISIS DE ALGORITMOS.

Un algoritmo es una secuencia de pasos lógica para encontrar la solución de un problema.

Todo algoritmo debe contar con las siguientes características:

Preciso, definido y finito. Por Preciso, entenderemos que cada paso del algoritmo tiene una relación con el anterior y el siguiente; un algoritmo es Definido, cuando se ejecuta más de una vez con los mismos datos y el resultado es el mismo; y Finito, indica que el algoritmo cuenta con una serie de pasos definidos o que tiene un fin.

 Hablando de estructuras de datos podemos decir que los algoritmos según su función se dividen en:

ü  Algoritmos de ordenamiento y

ü  Algoritmos de búsqueda.

 Un algoritmo de ordenamiento, es el que pone los elementos de una lista o vector en una secuencia (ascendente o descendente) diferente a la entrada, es decir, el resultado de salida debe ser una permutación (reordenamiento) de la entrada que satisfaga la relación de orden requerida.

 Un algoritmo de búsqueda, es aquel que está diseñado para encontrar la solución de un problema boleano de existencia o no de un elemento en particular dentro de un conjunto finito de elementos (estructura de datos), es decir al finalizar el algoritmo este debe decir si el elemento en cuestión existe o no en ese conjunto, además, en caso de existir, el algoritmo podría proporcionar la localización del elemento dentro del conjunto.

TIEMPO DE EJECUCIÓN DE UN ALGORITMO.

 El tiempo de ejecución de un algoritmo, se refiere a la suma de los tiempos en los que el programa tarda en ejecutar una a una todas sus instrucciones, tomando en cuenta que cada instrucción requiere una unidad de tiempo, dicho tiempo se puede calcular en función de n (el número de datos), lo que se denomina T(n)

 Si hacemos un análisis de forma directa al programa para determinar el tiempo de ejecución del mismo, debemos definir el conjunto de operaciones primitivas, que son independientes del lenguaje de programación que se use. Algunas de las funciones primitivas son las siguientes:

ü  Asignación de un valor a una variable.

ü  Llamada a un método.

ü  Ejecución de una operación aritmética.

ü  Comparar dos números.

ü  Poner índices a un arreglo.

ü  Seguir una referencia de objeto.

ü  Retorno de un método.

En forma específica, una operación primitiva corresponde a una instrucción en el lenguaje de bajo nivel, cuyo tiempo de ejecución depende del ambiente de hardware y software, pero es constante. Ejemplo. Método que retorna el número mayor de un arreglo de n elementos.

 

COMPLEJIDAD EN ESPACIO.

La complejidad de espacio, se refiere a la memoria que utiliza un programa para su ejecución; es decir el espacio de memoria que ocupan todas las variables propias del programa. Dicha memoria se divide en Memoria estática y Memoria dinámica.

Para calcular la memoria estática, se suman la cantidad de memoria que ocupa cada una de las variables declaradas en el programa.

Tomando en cuenta los tipos de datos primitivos del lenguaje de programación java podemos determinar el espacio que requiere cada una de las variables de un programa, de acuerdo a lo siguiente:

Tipo de dato primitivo	Tamaño en bits	Tamaño en Bytes
byte char short int float long double	8 16 16 32 32 64 64	1 2 2 4 4 8 8

El cálculo de la memoria dinámica, no es tan simple ya que depende de cada ejecución del programa o algoritmo y el tipo de estructuras dinámicas que se estén utilizando.

SELECCIÓN DE UN ALGORITMO.

 Una de las características primordiales en la selección de un algoritmo es que este sea sencillo de entender, calcular, codificar y depurar, así mismo que utilice eficientemente los recursos de la computadora y se ejecute con la mayor rapidez posible con un eficaz uso de memoria dinámica y estática.

 También para seleccionar correctamente el mejor algoritmo es necesario realizar estas preguntas:

ü  ¿Qué grado de orden tendrá la información que vas a manejar?

 Si la información va a estar casi ordenada y no quieres complicarte, un algoritmo sencillo como el ordenamiento burbuja será suficiente. Si por el contrario los datos van a estar muy desordenados, un algoritmo poderoso como Quicksort puede ser el más indicado. Y si no puedes hacer una presunción sobre el grado de orden de la información, lo mejor será elegir un algoritmo que se comporte de manera similar en cualquiera de estos dos casos extremos.

ü  ¿Qué cantidad de datos vas a manipular?

 Si la cantidad es pequeña, no es necesario utilizar un algoritmo complejo, y es preferible uno de fácil implementación. Una cantidad muy grande puede hacer prohibitivo utilizar un algoritmo que requiera de mucha memoria adicional.

ü  ¿Qué tipo de datos quieres ordenar?

 Algunos algoritmos sólo funcionan con un tipo específico de datos (enteros, enteros positivos, etc.) y otros son generales, es decir, aplicables a cualquier tipo de dato.

ü  ¿Qué tamaño tienen los registros de tu lista?

 Algunos algoritmos realizan múltiples intercambios (burbuja, inserción). Si los registros son de gran tamaño estos intercambios son más lentos.