Complejidad del algoritmo
Enviado por melissap11 • 18 de Octubre de 2015 • Ensayos • 387 Palabras (2 Páginas) • 121 Visitas
LA COMPLEJIDAD DEL ALGORITMO
Se sabe que un algoritmo son unos pasos específicos dados para que resolver un problema o una situación.
Eficiencia y complejidad:
El diseño de los pasos dados debe ser específico, no complejo para facilitar la solución que proporcionara, ya que cada paso representa costos en tiempo y espacio, donde tiempo es lo que tarda en ejecutarse y espacio es la memoria ocupada
El tiempo depende de: los datos de entrada que le suministremos, la calidad del código generado por el compilador para crear el programa objeto, la naturaleza y rapidez de las instrucciones máquina del procesador concreto que ejecute el programa.
Hay dos estudios posibles sobre el tiempo:
1. Uno que proporciona una medida teórica (a priori), que consiste en obtener una función que acote (por arriba o por abajo) el tiempo de ejecución del algoritmo para unos valores de entrada dados.
2. Y otro que ofrece una medida real (a posteriori), consistente en medir el tiempo de ejecución del algoritmo para unos valores de entrada dados y en un ordenador concreto.
La primera medida representa estimación del comportamiento del algoritmo y la segunda representa las medidas reales del comportamiento del algoritmo, estas medidas son funciones temporales de los datos de entrada.
El tamaño de la entrada será el número de componentes sobre los que se ejecutará el algoritmo
T(n) será el tiempo de ejecución de un algoritmo, ya que no se puede utilizar una medida especifica de tiempo, se debe encontrar la manera de reducir la diferencia entre distintas implementaciones de un mismo algoritmo.
Esa diferencia es que acota el siguiente principio:
Principio de Invarianza:
Dado un algoritmo y dos implementaciones suyas I1 e I2, que tardan T1(n) y T2 (n). Segundos respectivamente, el Principio de Invarianza afirma que existe una constante real c > 0 y un número natural n0 tales que para todo n = n se verifica que T1(n) = cT2 (n).
Se entiende que el tiempo de implementaciones distintas de un algoritmo no va a cambiar más que una constante multiplicativa.
Con esto podemos definir sin problemas que un algoritmo tarda un tiempo del orden de T(n) si existen una constante real c > 0 y una implementación I del algoritmo que tarda menos que cT(n), para todo n tamaño de la entrada.
Es importante tener en cuenta que el comportamiento de un algoritmo puede variar para diferentes entradas
...