Tiempos de ejecución (Big-Oh)
Caso de un algoritmo iterativo
Álgebra aplicada al análisis de algoritmos.
Ejercicio perteneciente a una práctica de la materia Algoritmos y Estructuras de Datos de la Facultad de Informática - Universidad Nacional de la Plata , primer cuatrimestre de 2019.
Pasos:
Buscar las líneas de código cuyo tiempo de ejecución es constante . Estas son en general las asignaciones, operaciones lógicas y matemáticas, etc.
Buscar los bucles (for y en algunos casos while y otros), ellos se corresponden a sumatorias. ¡ Tener cuidado con el valor de incremento de la variable !
Armar con las partes anteriores la función T(n)
Procesar algebraicamente T(n) para obtener O(n)
Ejemplo:
Código (Java):
1 public static void uno ( int n) { 2 int i, j, k ; 3 int [ ] [ ] a, b, c; 4 a = new int [ n] [ n] ; 5 b = new int [ n] [ n] ; 6 c = new int [ n] [ n] ; 7 for ( i= 1 ; i<= n- 1 ; i++ ) { 8 for ( j= i+ 1 ; j<= n; j++ ) { 9 for ( k= 1 ; k<= j; k++ ) { 10 c[ i] [ j] = c[ i] [ j] + a[ i] [ j] * b[ i] [ j] ; 11 } 12 } 13 } 14 }
Líneas 1 a 6
: \quad : \quad : Tiempo constante: se juntan en k 1 k_1 k 1
Líneas 7, 8 y 9
:
Los for(i=a; i<=b; i++) se convierten en sumas ∑ a b \sum_a^b ∑ a b
Línea 10
:
Tiempo constante k 2 k_2 k 2
Uniendo la partes se tiene la función de tiempo T ( n ) T(n) T ( n )
T ( n ) = ∑ i n k 1 ⏟ 1..6 + ∑ i = 1 n − 1 ⏟ 7 ( ∑ j = i + 1 n ⏟ 8 ( ∑ k = 1 j ⏟ 9 ∑ i n k 2 ⏟ 10 ) ) T(n) = \underbrace{\vphantom{\sum_{i}^{n}} k_1}_{1..6} + \underbrace{\sum_{i=1}^{n-1}}_{7} \Biggl(\underbrace{\sum_{j=i+1}^{n}}_{8} \Biggl( \underbrace{\sum_{k=1}^{j}}_{9} \underbrace{\vphantom{\sum_{i}^{n}}k_2}_{10}\Biggr)\Biggr)
T ( n ) = 1 . . 6 i ∑ n k 1 + 7 i = 1 ∑ n − 1 ( 8 j = i + 1 ∑ n ( 9 k = 1 ∑ j 1 0 i ∑ n k 2 ) )
Nota : Los paréntesis no se necesitan en la ecuación anterior, los agregué solo para que se vea mejor el alcance de cada sumatoria.
Comienzo a trabajar desde la sumatoria más interna hacia afuera
Suma de una constante
∑ k = 1 j k 2 = j ∗ k 2 \sum\limits_{k=1}^{j} k_2 = j * k_2
k = 1 ∑ j k 2 = j ∗ k 2
T ( n ) = k 1 + ∑ i = 1 n − 1 ( ∑ j = i + 1 n ( j ∗ k 2 ) ) T(n) = k_1 + \sum_{i=1}^{n-1} \left(\sum_{j=i+1}^{n}\left( j * k_2\right)\right)
T ( n ) = k 1 + i = 1 ∑ n − 1 ( j = i + 1 ∑ n ( j ∗ k 2 ) )
Suma de constante por variable :
∑ j = i + 1 n ( j ∗ k 2 ) = k 2 ∗ ∑ j = i + 1 n j \sum\limits_{j=i+1}^{n}(j* k_2) = k_2 * \sum\limits_{j=i+1}^{n}j
j = i + 1 ∑ n ( j ∗ k 2 ) = k 2 ∗ j = i + 1 ∑ n j
T ( n ) = k 1 + ∑ i = 1 n − 1 ( k 2 ∗ ∑ j = i + 1 n ( j ) ) T(n) = k_1 + \sum_{i=1}^{n-1} \left(k_2 *\sum_{j=i+1}^{n}\left( j\right)\right)
T ( n ) = k 1 + i = 1 ∑ n − 1 ( k 2 ∗ j = i + 1 ∑ n ( j ) )
Cambio los límites de la suma :
∑ j = i + 1 n j = ∑ j = 1 n j − ∑ j = 1 i j \sum\limits_{j=i+1}^{n}j = \sum\limits_{j=1}^{n}j - \sum\limits_{j=1}^{i}j
j = i + 1 ∑ n j = j = 1 ∑ n j − j = 1 ∑ i j
T ( n ) = k 1 + ∑ i = 1 n − 1 ( k 2 ∗ ( ∑ j = 1 n j − ∑ j = 1 i j ) ) T(n) = k_1 + \sum_{i=1}^{n-1} \left(k_2 *\left(\sum\limits_{j=1}^{n}j - \sum\limits_{j=1}^{i}j\right)\right)
T ( n ) = k 1 + i = 1 ∑ n − 1 ( k 2 ∗ ( j = 1 ∑ n j − j = 1 ∑ i j ) )
Suma de la variable indice :
∑ j = 1 n j = n ∗ ( n + 1 ) 2 ; ∑ j = 1 i j = i ∗ ( i + 1 ) 2 \sum\limits_{j=1}^{n}j = \frac{n*(n+1)}{2} \qquad; \qquad \sum\limits_{j=1}^{i}j= \frac{i*(i+1)}{2}
j = 1 ∑ n j = 2 n ∗ ( n + 1 ) ; j = 1 ∑ i j = 2 i ∗ ( i + 1 )
T ( n ) = k 1 + ∑ i = 1 n − 1 ( k 2 ∗ ( n ∗ ( n + 1 ) 2 − i ∗ ( i + 1 ) 2 ) ) T(n) = k_1 + \sum_{i=1}^{n-1} \left(k_2 *\left(\frac{n*(n+1)}{2}-\frac{i*(i+1)}{2}\right)\right)
T ( n ) = k 1 + i = 1 ∑ n − 1 ( k 2 ∗ ( 2 n ∗ ( n + 1 ) − 2 i ∗ ( i + 1 ) ) )
Sacando la constante k 2 2 \frac{k_2}{2} 2 k 2
T ( n ) = k 1 + k 2 2 ∗ ∑ i = 1 n − 1 ( n 2 + n − i 2 − i ) T(n) = k_1 + \frac{k_2}{2} * \sum_{i=1}^{n-1} \left( n^2 + n -i^2-i\right)
T ( n ) = k 1 + 2 k 2 ∗ i = 1 ∑ n − 1 ( n 2 + n − i 2 − i )
Distribuyendo la sumatoria :
T ( n ) = k 1 + k 2 2 ∗ ( ∑ i = 1 n − 1 ( n 2 + n ) − ∑ i = 1 n − 1 i 2 − ∑ i = 1 n − 1 i ) T(n) = k_1 + \frac{k_2}{2} * \left(\sum_{i=1}^{n-1} (n^2 + n) - \sum_{i=1}^{n-1} i^2 - \sum_{i=1}^{n-1} i\right)
T ( n ) = k 1 + 2 k 2 ∗ ( i = 1 ∑ n − 1 ( n 2 + n ) − i = 1 ∑ n − 1 i 2 − i = 1 ∑ n − 1 i )
Aplicando :
∑ i = 1 n c t e = n ∗ c t e → ∑ i = 1 n − 1 ( n 2 + n ) = ( n − 1 ) ∗ ( n 2 + n ) \sum\limits_{i=1}^{n} cte = n *cte \quad \rightarrow \quad \sum\limits_{i=1}^{n-1}(n^2 + n) = (n-1)*(n^2 + n)
i = 1 ∑ n c t e = n ∗ c t e → i = 1 ∑ n − 1 ( n 2 + n ) = ( n − 1 ) ∗ ( n 2 + n )
∑ i = 1 n i = n ∗ ( n + 1 ) 2 → ∑ i = 1 n − 1 i = ( n − 1 ) ∗ [ ( n − 1 ) + 1 ] 2 = ( n − 1 ) ∗ n 2 \sum\limits_{i=1}^{n} i = \frac{n*(n+1)}{2} \quad \rightarrow \quad \sum\limits_{i=1}^{n-1} i = \frac{(n-1)*[(n-1)+1]}{2} = \frac{(n-1)*n}{2}
i = 1 ∑ n i = 2 n ∗ ( n + 1 ) → i = 1 ∑ n − 1 i = 2 ( n − 1 ) ∗ [ ( n − 1 ) + 1 ] = 2 ( n − 1 ) ∗ n
∑ i = 1 n i 2 = n ∗ ( n + 1 ) ∗ ( 2 n + 1 ) 6 → ∑ i = 1 n − 1 i 2 = ( n − 1 ) ∗ [ ( n − 1 ) + 1 ] ∗ [ 2 ( n − 1 ) + 1 ] 6 = ( n − 1 ) ∗ n ∗ ( 2 n − 1 ) 6 \sum\limits_{i=1}^{n} i^2 = \frac{n*(n+1)*(2n+1)}{6} \quad \rightarrow \quad \sum\limits_{i=1}^{n-1} i^2 = \frac{(n-1)*[(n-1)+1]*[2(n-1)+1]}{6} = \frac{(n-1)*n*(2n-1)}{6}
i = 1 ∑ n i 2 = 6 n ∗ ( n + 1 ) ∗ ( 2 n + 1 ) → i = 1 ∑ n − 1 i 2 = 6 ( n − 1 ) ∗ [ ( n − 1 ) + 1 ] ∗ [ 2 ( n − 1 ) + 1 ] = 6 ( n − 1 ) ∗ n ∗ ( 2 n − 1 )
T ( n ) = k 1 + k 2 2 ∗ ( ( n − 1 ) ∗ ( n 2 + n ) − ( n − 1 ) ∗ n ∗ ( 2 n − 1 ) 6 − ( n − 1 ) ∗ n 2 ) T(n) = k_1 + \frac{k_2}{2} * \left( (n-1)*(n^2 + n) -\frac{(n-1)*n*(2n-1)}{6} - \frac{(n-1)*n}{2}\right)
T ( n ) = k 1 + 2 k 2 ∗ ( ( n − 1 ) ∗ ( n 2 + n ) − 6 ( n − 1 ) ∗ n ∗ ( 2 n − 1 ) − 2 ( n − 1 ) ∗ n )
Haciendo denominador común y distribuyendo :
T ( n ) = k 1 + k 2 2 ∗ ( 6 ( n 3 + n 2 − n 2 − n ) − ( 2 n 3 − n 2 − 2 n 2 + n ) − 3 ( n 2 − n ) 6 ) T(n) = k_1 + \frac{k_2}{2} * \left( \frac {6( n^3 + n^2 - n^2 - n) - ( 2n^3 - n^2 - 2n^2 + n) - 3(n^2 - n)}{6} \right)
T ( n ) = k 1 + 2 k 2 ∗ ( 6 6 ( n 3 + n 2 − n 2 − n ) − ( 2 n 3 − n 2 − 2 n 2 + n ) − 3 ( n 2 − n ) )
Operando algebraicamente :
T ( n ) = k 2 3 ∗ n 3 − k 2 3 ∗ n + k 1 T(n) = \frac{k_2}{3} * n^3 - \frac{k_2}{3} * n + k_1
T ( n ) = 3 k 2 ∗ n 3 − 3 k 2 ∗ n + k 1
Recordando la definición de Big-Oh :
Decimos que
T ( n ) = O ( f ( n ) ) T(n) = O(f(n))
T ( n ) = O ( f ( n ) )
si existen constantes c c c n 0 n_0 n 0
T ( n ) ≥ c ∗ f ( n ) ∀ ( c ) > 0 ∧ n ≥ n 0 T(n)\ge c * f(n) \quad \forall (c) \gt 0\; \wedge\; n \ge n_0
T ( n ) ≥ c ∗ f ( n ) ∀ ( c ) > 0 ∧ n ≥ n 0
Aplicando esto al T ( n ) T(n) T ( n )
Analizo cada término por separado
k 2 3 ∗ n 3 ≤ c 2 ∗ n 3 ∀ c 2 ≥ k 2 3 ∧ n 0 ≥ 1 \frac{k_2}{3} * n^3 \le c_2 * n^3 \quad\quad \forall c_2 \ge \frac{k_2}{3} \wedge n_0 \ge 1
3 k 2 ∗ n 3 ≤ c 2 ∗ n 3 ∀ c 2 ≥ 3 k 2 ∧ n 0 ≥ 1
− k 2 3 ∗ n ≤ c 2 ∗ n 3 ∀ c 2 ≥ 0 ∧ n 0 ≥ 0 -\frac{k_2}{3} * n \le c_2 * n^3 \quad\quad \forall c_2 \ge 0 \wedge n_0 \ge 0
− 3 k 2 ∗ n ≤ c 2 ∗ n 3 ∀ c 2 ≥ 0 ∧ n 0 ≥ 0
por lo anterior los términos negativos se pueden eliminar de T(n)
k 1 ≤ c 1 ∗ n 3 ∀ c 1 ≥ 0 ∧ n 0 ≥ 1 k_1 \le c_1 * n^3 \quad\quad \forall c_1 \ge 0 \wedge n_0 \ge 1
k 1 ≤ c 1 ∗ n 3 ∀ c 1 ≥ 0 ∧ n 0 ≥ 1
Sumando miembro a miembro (descartando el término negativo)
k 2 3 ∗ n 3 + k 1 ≤ c 2 ∗ n 3 + c 1 ∗ n 3 \frac{k_2}{3} * n^3 + k_1 \le c_2 * n^3 + c_1 * n^3
3 k 2 ∗ n 3 + k 1 ≤ c 2 ∗ n 3 + c 1 ∗ n 3
Sacando factor común n 3 n^3 n 3
k 2 3 ∗ n 3 + k 1 ≤ ( c 2 + c 1 ) ∗ n 3 \frac{k_2}{3} * n^3 + k_1 \le ( c_2 + c_1 ) * n^3
3 k 2 ∗ n 3 + k 1 ≤ ( c 2 + c 1 ) ∗ n 3
Tomando ( n 0 = 1 (n_0 = 1 ( n 0 = 1 c = ( c 1 + c 2 ) c = (c_1 + c_2) c = ( c 1 + c 2 ) c 1 = k 1 c_1 = k_1 c 1 = k 1 c 2 = k 2 3 c_2 = \frac{k_2}{3} c 2 = 3 k 2
Llegamos finalmente a que:
k 2 3 ∗ n 3 + k 1 ≤ c ∗ n 3 \frac{k_2}{3} * n^3 + k_1 \le c * n^3
3 k 2 ∗ n 3 + k 1 ≤ c ∗ n 3
T ( n ) ≤ c ∗ n 3 c o n c = k 1 + k 2 3 ∧ n 0 = 1 T(n) \le c * n^3 \qquad con \quad c = k_1 + \frac{k_2}{3} \quad \wedge \quad n_0 = 1
T ( n ) ≤ c ∗ n 3 c o n c = k 1 + 3 k 2 ∧ n 0 = 1
T ( n ) ≤ O ( n 3 ) T(n) \le O ( n^3 )
T ( n ) ≤ O ( n 3 )
