Tema 1.2 - Eficiencia Algorítmica

Comparación de Algoritmos

La calidad del algoritmo depende de

🧠
Eficiencia
Medida de los recursos que emplea un algoritmo en su ejecución.
💽
Recursos Computacionales
  • Tiempo (ejecución).
  • Espacio (memoria).
  • Nº procesadores.
📚
Recursos No Computacionales
  • Dificultad de implementación.
  • Disponibilidad de bibliotecas.

Tiempo algorítmico

⏳
La comparación en tiempo depende de:
  • Datos de entrada.
  • Calidad del código generado por el compilador.
  • Rapidez del procesador.
  • Complejidad intrínseca del algoritmo.
🕰️
Estudios sobre el tiempo
  • Teórico (a priori): Función que acote el tiempo de ejecución para unos valores de los datos de entrada.
  • Real (a posteriori): Tiempo de ejecución para una determinada entrada y en un ordenador concreto.

Principio de Invarianza

📖
Definición
Dado un algoritmo y dos implementaciones I1I_1 e I2I_2, que tardan T1(n)T_1(n) y T2(n)T_2(n) respectivamente, existe una constante real positiva c∈R+c \in R^+ y un natural n0∈Nn_0 \in N tales que:
∀ n>=n0, T1(n)<=c ⋅ T2(n)\forall\ n >= n_0,\ T_1(n) <= c\ ·\ T_2(n)
El tiempo de ejecución de dos implementaciones distintas no va a diferir más que en una constante multiplicativa.

Estudio real y teórico de un algoritmo

🖥️
En el estudio real de un algoritmo se mide el tiempo de ejecución de este en una máquina
💡
En el estudio teórico de un algoritmo se trata de estimar el comportamiento del algoritmo independientemente de la máquina que lo vaya a ejecutar

Complejidad algorítmica

📖
La complejidad algorítmica ayuda a determinar la eficiencia de un algoritmo. Esta nos permite obtener medidas aproximadas, relativas al tamaño del problema. Este análisis es independiente de la máquina donde se ejecutará el problema
🧪
Tiempo empleado: T(n)T(n)
Dado un conjuto de datos de entrada nn, se dice que T(n)T(n) es el tiempo que se empleará para resolver el problema
⚠️ En este caso el tiempo no se mide en segundos sino en pasos o instrucciones
Ejemplo
Tomando como ejemplo un bucle tal que…
for i=0 to 10:
	suma += i
Entonces podemos plantear que el número de instrucciones que se ejecutarán será k⋅nk·n. Siendo nn el número de veces que se ejecutará el bucle, en este caso 1010. Y siendo kk una constante que representa el número de instrucciones que se ejecutan en cada iteración.

Medidas Asintóticas

📖
Las medidas asintóticas nos permiten describir la complejidad de un algoritmo a base de definir unas clases de equivalencia las cuales crecen de la misma forma, dependiendo de la entrada, que los algoritmos que estamos estudiado
📖
El concepto de asintótico se refiere a que el estudio de los algoritmos se realiza para estradas de datos suficientemente grandes

Notación O\text O (’o’ mayúscula)

📖
Esta notación busca expresar la cota superior. Esto quiere decir que esta notación representa todas aquellas funciónes que crecen en complejidad como mucho tan rápido como nuestro algoritmo
Esta notación representa: El peor de los casos
📶
El orden de complejidades es el siguiente…
O(1)<<O(log⁡n)<<O(n)<<O(n log⁡n)<<O(n2)<<O(n3)<<⋯<<O(2n)<<O(n!)\small{O(1) << O(\log n) << O(n) << O(n\ \log n) << O(n^2) << O(n^3) << \dots << O(2^n) << O(n!)}
💡 Siendo O(1)O(1) lo mejor y O(n!)O(n!) lo peor

Notación Ω\Omega (Omega)

📖
Esta notación busca expresar la cota inferiror. Esto quiere decir que esta notación representa todas aquellas funciónes que crecen en complejidad como mínimo tan rápido como nuestro algoritmo
Esta notación representa: El mejor de los casos

Notación Θ\Theta (Theta)

📖
Esta notación busca expresar el exacto de la función. Esto quiere decir que esta notación representa todas aquellas funciónes que crecen en complejidad tan rápido como nuestro algoritmo
Esta notación representa: El caso promedio

Cálculo de la Eficiencia

🔣
Sentencias simples (+,-,=,…)
Las instrucciones simples, como las lecturas, escrituras, asignación, …; Tienen una complejidad constante: O(1)O(1)
🔁
Bloques de sentencia (for/while)
Los bloques de sentencias, son aquellos que ejecutan una serie de sentencias simples. En este caso se aplica la regla del máximo, osea, se toma la complejidad mayor de todas las complejidades contenidas en el bloque de sentencias
Ejemplo: O(1)+O(1)+O(n)+O(n2)=O(n2)O(1) + O(1) + O(n) + O(n^2) = O(n^2)
🔀
Sentencias condicionales (if/else)
En el caso de las sentencias condicionales, se tomará la complejidad mayor de los dos bloques

Funciones

📖
La complejidad de una función equivale a la complejidad del código que ejecuta. Podemos entender una función como un bloque de código

Recursividad

📖
La complejidad de una función recursiva se puede medir usado uno de los siguiente métodos:
  • Método de sustitución
  • Árbol de recursividad
  • Expansión de recurrencias
  • Ecuación característica
🪓
Divide y Vencerás
T(n)=aT(nb)+cnk con a≥1,b≥2,k≥0,c>0T(n) = aT\bigg(\cfrac{n}{b}\bigg) + cn^k \text{ con } a \geq 1, b \geq 2, k \geq 0, c > 0
T(n)={O(nk)a<bkO(nklog⁡bn)a=bkO(nlog⁡ba)a>bkT(n) = \begin{cases} O(n^k) && a <b^k\\ O(n^k \log_b n) && a = b^k\\ O(n^{\log_b a}) && a > b^k \end{cases}
Siendo…
  • aa → Sub-problemas generados
  • bb → Divisor del problema
  • kk → Complejidad del método de combinación
© 2024 Notion Lovers.Made with ❤️ by Notion Lovers