Unidad VII Análisis de los algoritmos

7.1 Complejidad en el tiempo.
7.2 Complejidad en el espacio.
7.3 Eficiencia de los algoritmos.

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.

 Concepto de complejidad de algoritmos.

 La mayoría de los problemas que se plantean en la actualidad se pueden resolver con algoritmos que difieren en su eficiencia. Dicha diferencia puede ser irrelevante cuando el número de datos es pequeño pero cuando la cantidad de datos es mayor la diferencia crece. Ejemplo: Suma de 4 y 10 primero números naturales.

 

1+2+3+4  = 10

 

1+2+3+4+5+6+7+8+9+10 = 55

3                3

tiempo

9                3

4*(4+1)/2 = 10

 

10*(10+1)/2 = 55

 

La complejidad  de un algoritmo o complejidad computacional, estudia los recursos y esfuerzos requeridos durante el cálculo para resolver un problema los cuales se dividen en: tiempo de ejecución y espacio en memoria. El factor tiempo, por lo general es más importante que el factor espacio, pero existen algoritmos que ofrecen el peor de los casos en un menor tiempo que el mejor de los casos, lo cual no es la mejor de las soluciones.

 El factor tiempo de ejecución de un algoritmo depende de la cantidad de datos que se quieren procesar, una forma de apreciar esto es con las cuatro curvas que se presentan en las graficas de la figura 1.1.




 

Como se puede apreciar en las graficas, entre mayor se al número de datos mayor tiempo se aplica en las graficas a), b) y c), lo cual no ocurre con la grafica d), por lo tanto podemos deducir que una función que se acerque más al eje de las x es más constante y eficiente en le manejo de grandes cantidades de datos.

 Aritmética de la notación O.

La notación asintótica “O” (grande) se utiliza para hacer referencia a la velocidad de crecimiento de los valores de una función, es decir, su utilidad radica en encontrar un límite superior del tiempo de ejecución de un algoritmo buscando el peor caso.

 

La definición de esta notación es la siguiente:

 

f(n) y g(n) funciones que representan enteros no negativos a números reales. Se dice que f(n) es O(g(n)) si y solo si hay una constante real c>0 y un entero constante n0>=1 tal que f(n)<=cg(n) para todo entero n>= n0. Esta definición se ilustra en la figura 1.2.


 

 Nota: el orden de magnitud de una función es el orden del término de la función más grande respecto de n.

 

La notación asintótica “O” grande se utiliza para especificar una cota inferior para la velocidad de crecimiento de T(n), y significa que existe una constante c tal que T(n) es mayor o igual a c(g(n)) para un número infinito de valores n.

 

Regla para la notación O

 

Definición     (O)T(n) es O(f(n)) si existen las constantes positivas c  y n0 tales que n >= n0 se verifica T(n)<= cf(n).

 

Esta definición afirma que existe un punto inicial n0 tal que para todos los valores de n después de ese punto; el tiempo de ejecución T(n) esta acotado por algún múltiplo de f(n).

 

La expresión matemática de lo anterior es T(n) = O(f(n)) y el índice de crecimiento de T(n) es <= al crecimiento de f(n).

 

T(n) Tiempo de ejecución del algoritmo.

F(n) Tiempo al introducir los datos al algoritmo.

 

 Complejidad.

 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 cuanta que cada instrucción requiere una unidad de tiempo, dicho tiempo se puede calcular en función de n (el numero 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.

 public int Mayor()

{

            int may=arr[0];

            for(ind=0; ind<arr.length; ind++)

                        if(arr[ind]>may)

                                   may=arr[ind];

            return may;

}

 

Para este ejemplo se pueden encontrar dos formulas que determinen el tiempo de ejecución, la primera representa el peor de los casos y la segunda el mejor de los casos. Para se creación se sigue el programa:

 

-       La inicialización de la variable may=arr[0], corresponde a dos unidades de tiempo.

-       La inicialización del ciclo for agrega otra unidad de tiempo.

-       La condición del ciclo for se ejecuta desde 1 hasta el tamaño del arreglo lo cual agrega el número de unidades del tamaño del arreglo.

-       El cuerpo del ciclo for se ejecuta el tamaño del arreglo - 1 veces, para este caso el numero de operaciones del cuerpo del ciclo pueden ser 6 o 4 (condición del if dos, asignación a may dos e incremento y asignación dos) en el peor o mejor de los casos respectivamente. Por consiguiente el cuerpo del ciclo contribuye con 4(tamaño del arreglo - 1) o 6(tamaño del arreglo - 1) unidades de tiempo.

-       Y el retorno de may aporta una unidad de tiempo.

 

Con todo lo anterior se logra obtener las siguientes formulas (tamaño del arreglo o arr.length se cambian por n):

 

            T(n) = 2+1+n+6(n-1)+1 = 7n-2                  Peor de los casos.

 

            T(n) = 2+1+n+4(n-1)+1 = 5n                     Mejor de los casos.

 

Ejercicio. Determinar el tiempo de ejecución del método que se encarga de asignar de forma aleatoria los elementos a un arreglo de n elementos enteros.

 

Ejercicio. Determina el tiempo de ejecución del método que se encarga de contar los elementos pares de un arreglo de n elementos enteros y retorna el resultado.

 

Ejercicio. Determinar el tiempo de ejecución del método que se encarga de calcular el factorial de un número y retorna el resultado.

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.

 

 

 

 

 

 

 

 

 

 

 


Comments