Aritmetica de la notacion o

Aritmética de la notación O

Una vez definido el concepto de algoritmo pasaremos a su análisis aritmético. Entendemos por tamaño de entrada de un algoritmo al número de componentes sobre los que seva a ejecutar el algoritmo. Por ejemplo la dimensión de un vector a ordenar o el tamaño de las matrices a multiplicar.
La unidad de tiempo a la que deben hacer referencia las medidas de eficienciade un algoritmo no pueden ser expresadas en segundos o en otras unidad de tiempo concreta pues no existe una computadora estándar a la que puedan hacer referencia todas las medidas.
Denotaremos port(n) el tiempo de ejecución de un algoritmo para una entrada de tamaño n.
A la hora de medir el tiempo siempre lo haremos en función del número de operaciones elementales que realiza dicho algoritmoentendiendo por operaciones elementales (OE) aquellas que el compilar realiza el computador en tiempo delimitado por una constante. Así, consideremos OE las operaciones aritméticas básica, asignacionesa variables de tipo predefinido, los altos o llamadas a funciones y procedimientos y el retorno de estos , las operaciones lógicas y el acceso a estructuras indexadas básicas, como son los vectoresy matrices, cada una de ellas contabilizara como una operación elemental, resumiendo el tiempo de ejecución de un algoritmo va a ser una función que mida el numero de operaciones elementales querealiza el algoritmo para un tamaño de entrada dado.
Operaciones elementales
Las operaciones elementales son:
* Las operaciones aritméticas básicas: ( +, -, *, /)
* Asignación a variables
*Los saltos: llamadas a funciones, procedimientos, retornos, ciclos.
* Las comparaciones y operaciones lógicas: > < = and or not
* Acceso a vectores y matrices
Para analizar desde unpseudocódigo la complejidad, típicamente se aplica las reglas siguientes:
* Las OE toman tiempo O(1) si la complejidad de una sucesión de instrucciones I1, i2, I3 . . . Ik donde k no depende...