lab de algoritmos( Analisis de algoritmos)

Hare referencia al analisis de los algoritmos en que consiste un analisis de un algoritmo pues en el grado de complejidad del mismo como en el ejercicio pasado realizamos la tabla y grafica para determinar cual de las funciones era la peor opcion para desarrollar un algoritmo bueno pues eso se refiere a la complejidad de un algoritmo que es lo mismo al tiempo de respuesta del algoritmo no esta por demas mencionar que el analisis de algoritmos es parte importante de la teoria de la complejidad computacional que se enfoca en la complejidad inherente a la resoluciòn de un problema computable se basa en el tiempo y el espacio que con tiempo se refiere a el numero y tipo de pasos de un algoritmo para resolver un problema y el espacio dando un aproximado de memoria que se ocupa en la resolucion del problema.
los problemas que tienen una complejiad lineal son los que se resuelven en un tiempo que se relasiona linealmente con su tamaño
un ejemplo de complejidad lineal seria
con un vector cuando se extrae un elemeto de el, del indice que sea tomara un tiempo O(1) por que sin importar el lugar donde se encuentre solo se efectua una acciòn.
 ejemplo 2
O por decir en el momento que deseas buscar una palabra en un diccionario abres el diccionario en un punto sabes si la palabra se encuentra ally o tienes que retroceder paginas para encontrarla o avanzar paginas para encontrar dicha palabra y ally estaras usando un proceso recursivo que por consiguiente tiene una complejidad logaritmica O(logn) ya que se efectuan varias operaciones en forma recursiva y claro tardara mas que una con complejidad O(1)

tambien hay operaciones con mas complejidad y aqui esta una tabla con una jerarquia de mayor a menor eficiencia:

• (n): Complejidad lineal. aparece en la complejidad de bucles simples siempre y cuando la complejidad de las instrucciones interiores  sea constante
• O(n log n):se encuentra en el método de ordenación quicksort y se considera una buena complejidad. Si n se duplica, el tiempo de ejecución es ligeramente mayor del doble.
• O(n2): Complejidad cuadrática. Aparece en bucles o ciclos doblemente anidados. Si n se duplica, el tiempo de ejecución aumenta cuatro veces.
• O(n3): Complejidad cúbica. Suele darse en bucles con triple anidación. Si n se duplica, el tiempo de ejecución se multiplica por ocho. Para un valor grande de n empieza a crecer dramáticamente.
• O(na): Complejidad polinómica (a > 3). Si a crece, la complejidad del programa es bastante mala.
• O(2n): Complejidad exponencial. muy lentas y no son buenas en ejecucion de programas.Se dan en subprogramas recursivos que contengan dos o más llamadas internas. N

para entender mas esto se aplican las reglas siguientes:

• la asignacion de variables simples toman tiempo O(1)
• Escribir una salida simple toma tiempo O(1)
• Leer una entrada simple toma tiempo O(1)

•  Si las complejidades de una sucesion de instrucciones I1,I2,.....Ik donde k no depende del tamaño de la instancia, son respectivamente f1,f2,.....fk la complejidad total de la sucesiòn es:

                                                O(f1+f2+...+fk)=O(max{f1.....fk})

• La complejidad de una clausula de condiciòn es la suma del tiempo a evaluar la condiciòn y la complejidad de la alternativa ejecutada
• La complejidad de una repeticiòn es O(k(ft+f0)) donde k es el numero de veces que se repite ft es la complejidad de evaluar la condicion de terminar f0 la complejidad de la suceciòn de operaciones de las cuales consiste una repeticiòn
• La complejidad de tiempo de una llamada de subrutina es la suma del tiempo de calcular sus parametros el tiempo de asignacion de los parametros y el tiempo de ejecuciòn de las instrucciones
• Operaciones aritmèticas y asignaciones que procesan arreglos o conjuntos tienen complejidad lineal en el tamaño del arreglo o conjunto

Despues de analizar las reglas anteriores nos damos cuenta que entre mas grande o mas operaciones que se realizen mas tiempo tardara el algoritmo en responder.

bueno esto es todo por mi parte y aqui les dejo mis paginas de referencia:

http://es.wikipedia.org/wiki/An%C3%A1lisis_de_algoritmos
 Complejidad computacional de problemas y el analisis y diseño de algoritmos