NOTACION o GRANDE

Definicion:
Se utiliza para hacer referencia a la velocidad de crecimiento de los valores de una funcion, es decir su utilidad radica en encontrar un limite superior de tiempo de ejecucion de un algoritmo en el peor de los casos.

 

La definicion de esta notacion es la siguiente.-

g(n) O(F(n)) si y solo si existen las constantes C y n tales que g(n) <= C * F(n).

 

para todo C>=n se tiene que T(n)<=Cn el orden de la magnitud de una funcion es el orden del termino de la funcion mas grande en terminos de n.

Nota: el orden de magnitud de una función es el orden del termino de la función mas grande respecto de n.

 

caracterisitcas:

• El análisis de algoritmos estima el consumo de recursos de un algoritmo.
•  Esto nos permite comparar los costos relativos de dos o más algoritmos para resolver el mismo problema.
• El análisis de algoritmos también les da una herramienta a los diseñadores de algoritmos para estimar si una solución propuesta es probable que satisfaga las restricciones de recursos de un problema.
• El concepto de razón de crecimiento, es la razón a la cual el costo de un algoritmo crece conforme el tamaño de la entrada crece.
• Usualmente se mide el tiempo de ejecución de un algoritmo, y el almacenamiento primario y secundario que consume.
• Consideración principal para estimar el desempeño de un algoritmo, es el número de operaciones básicas requeridas por el algoritmo para procesar una entrada de cierto tamaño.