I1M2015: Análisis de la complejidad de los algoritmos
En la segunda parte de la clase hoy de Informática de 1º del Grado en Matemáticas se ha explicado el tema de análisis de la complejidad de los algoritmos.
Se empezó explicando la notación de Landau y los órdenes de complejidad. A continuación se presentaron varios ejemplos de definiciones de distintos órdenes. En cada ejemplo, se especificó el problema, se definió la función, se hizo una tabla sobre la variación de los tiempos y su correspondiente gráfica, se extrajeron las ecuaciones en recurrencia, se resolvieron con Wolfram Alpha y se demostró por inducción el orden de la definición.
Como resumen, en la siguiente tabla se muestra los ejemplos presentados
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
| Ejemplo | Ecuaciones | Orden | |-------------|--------------------|------------| | suma | T(1) = k | O(n) | | | T(n+1) = T(n)+k' | | |-------------|--------------------|------------| | suma2 | T(1) = k | O(1) | |-------------|--------------------|------------| | sumaDeSumas | T(1) = k | O(n²) | | | T(n+1) = T(n)+n | | |-------------|--------------------|------------| | potencia | T(1) = k | O(log(n)) | | | T(n) = T(n/2)+k' | | |-------------|--------------------|------------| | raiz | T(0) = k | O(2ⁿ) | | | T(n+1) = 2T(n)+k' | | |-------------|--------------------|------------| | ordenación | T(1) = k | O(nlog(n)) | | por mezcla | T(n) = 2T(n/2)+n | | |