Análisis de Operaciones Elementales y Complejidad

Apuntes

[Diapositiva 1] Análisis de Algoritmos Al medir el tiempo, siempre lo haremos con base en el número de operaciones elementales (OE) realizadas por el algoritmo. ¿Qué se considera una operación elemental? Operaciones aritméticas básicas Asignaciones a variables Llamadas a funciones y procedimientos Retorno o salida de datos Comparaciones lógicas (==, !=, <, >, <=, >=, ||, &&) Acceso a estructuras indexadas básicas , como vectores y matrices. 1 OE. Operaciones aritméticas compuestas (+=, -=, *=, /=, ++, --): 2 OE . Declaración de variables sin inicialización : no se cuenta. 0 OE . “\n” para salto de línea : no se cuenta. 0 OE . Parámetro de formateo (“%d”, “% d%d%d ”) en Scanf y Printf : cuentan solo 1 OE . Si la variable es inicializada : se cuenta 1 OE . Matrices y vectores con operación compuesta : se deben desglosar y llevar a su forma más básica. Jala University Course Algorithm 1 [Diapositiva 2] Jala University Course Algorithm 1 Análisis de Algoritmos Ej01.: int a, b, c; 0 OE Ej02.: int a = 4, b, c = 9; 2 OE Ej03.: a[i] = 4; 2 OE Ej04.: a[i][j] = 3; 3 OE Ej05.: a[i][j] += b[f]; a[i][j] = a[i][j] + b[f]; 7 OE Ej06.: printf ("%d\n", i)...