Complejidad del tiempo
La complejidad temporal representa de forma asintótica el tiempo que algoritmo para encontrar una solución.
Operación elemental
La complejidad consiste en evaluar la eficacia del método M y en comparar este último con otro método M'. Esta comparación es independiente del entorno (máquina, sistema, compilador, lenguaje, etc.). La eficiencia depende del número de operaciones elementales. Estos dependen del tamaño de los datos y la naturaleza de los datos.
En el caso de una estructura de tipo secuencia, la evaluación es igual a la suma de los costos. Por ejemplo, si el algoritmo tiene un tratamiento T1(n) seguido de T2(n), entonces T(n)=T1(n)+T2(n).
En el caso de una sucursal, la evaluación es igual al máximo de las sucursales. Por ejemplo, el algoritmo ejecuta T1(n) sino T2(n), luego T(n)=max(T1(n), T2(n)).
En el caso de un bucle, la evaluación es igual a la suma de los costes de los pasajes sucesivos. Por ejemplo, si el algoritmo es un tiempo Ti(n) con la complejidad de Ti(n) dependiendo del número i de la iteración. Entonces la complejidad es T(n) = sum(i=1 to n) Ti(n).
Notación Landau
La notación de Landau caracteriza el comportamiento asintótico de una función, es decir, el comportamiento de f(n) cuando n tiende a infinito.
Ejemplos de
Peor, mejor y promedio
Considere un algoritmo para encontrar un elemento en una matriz en forma iterativa. El algoritmo se detiene cuando se ha encontrado el valor. El algoritmo se desglosa de la siguiente manera: asignación de 0 a i, siempre que i no haya atravesado la tabla, se incrementa i, si tab[i]=valor, se devuelve verdadero, si no, al final de la tabla se devuelve falso. Sea C la complejidad del cuerpo del bucle.
En el peor de los casos, el algoritmo atraviesa toda la matriz, es decir, T(n)=1+n*C=O(n). En el mejor de los casos, el elemento está al comienzo de la matriz, por lo que T(n)=1+C=O(1). Consideramos que, en promedio, existe una probabilidad de 50% de que el elemento no esté en la matriz y de 50% de que esté a la mitad de la matriz (esto, por supuesto, es absurdo, pero no analizaremos todas las posibilidades). En este caso, la complejidad promedio es T(n)=0.5*(1+n*C)+0.5*(1+n*C/2)=a*n+b con constantes a y b = O (no) . Notamos que el comportamiento asintótico en promedio es el mismo que en el peor de los casos.
Ejemplos de
Suponga que cada una de las siguientes expresiones da el tiempo de procesamiento T (n) empleado por un algoritmo para resolver un problema de tamaño n. Seleccione los términos dominantes con el mayor aumento en n y especifique la complejidad de Big-Oh más baja de cada algoritmo.
| Expresión | Dominante | O (.) |
| 5 + 0,001n3+ 0.025n | 0.001n3 | Nosotros3) |
| 500n + 100n1.5 + 50n registro10 no | 100n1.5 | Nosotros1.5) |
| 0.3n + 5n1.5 + 2,5 n1.75 | 2,5 n1.75 | Nosotros1.75) |
| no2 Iniciar sesión2 n + n (registro2 no)2 | no2 Iniciar sesión2 no | Nosotros2 log n) |
| n registro3 n + n log2 no | n registro3 n, n log2 no | O (n log n) |
| 3 registro8 n + log2 Iniciar sesión2 Iniciar sesión2 no | 3 registro8 no | O (log n) |
| 0. 100n + 0.01n2 | 0.01n2 | Nosotros2) |
| 0.01n + 100n2 | 100n2 | Nosotros2) |
| 2n + n0.5 + 0.5n1.25 | 0.5n1.25 | Nosotros1.25) |
| 0.01n log2 n + n (registro2 no)2 | n (registro2 no)2 | O (n (log n)2) |
| Registro de 100n3 n + n3 + 100n | no3 | Nosotros3) |
Las instrucciones siguientes muestran algunas características de la notación “Big-Oh” para las funciones f ≡ f (n) y g ≡ g (n). Determine si cada afirmación es VERDADERA o FALSA y corrija la fórmula en el último caso.
| Función | ¿Verdadero o falso? | Después de corregir |
| O (f + g) = O (f) + O (g) | FALSO | O (f + g) = max {O (f), O (g)} |
| O (f g) = O (f) O (g) | CIERTO | |
| si g = O (f) y h = O (f) entonces g = O (h) | FALSO | si g = O (f) yf = O (h) entonces g = O (h) |
| 5n + 8n 2 + 100n 3 = O (n 4) | CIERTO | |
| 5n + 8n 2 + 100n 3 = O (n 2 log n) | FALSO | Nosotros3 ) |
