analisis de algoritmos

ANÁLISIS DE LOS ALGORITMOS


7.1 complejidad en el tiempo.
7.2 complejidad en el espacio.
7.3 eficiencia de los algoritmos.

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, dichotiempo 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 valora 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 ysoftware, 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; Indmay)
                                   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 delos 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 número 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.
 
Complejidad en espacio.
La complejidad de espacio, se refiere a lamemoria 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 deprogramació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 eltipo 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....