guias/complejidad_algoritmica/guia_complejidad_algoritmica.md (9381B)
1 # Guía complejidad algorítmica 2 3 Algoritmos y Estructuras de Datos (CB100) - FIUBA 4 Martin Klöckner - [mklockner@fi.uba.ar](mailto:mklockner@fi.uba.ar) 5 6 > 1. Un algoritmo divide un problema de tamaño $n$ en dos subproblemas de tamaño 7 > $n/2$ con un costo constante en cada paso adicional, obtener la complejidad 8 > sabiendo que el costo real $T(n)$ es: 9 > \vspace{-0.65em} 10 > $$T(n) = 2T\left(\frac{n}{2}\right) + \mathcal{O}(1)$$ 11 12 Como la función de costo real $T(n)$ depende de la misma función $T(n)$ pero con 13 una entrada menor $n/2$ se trata de un algoritmo recursivo o iterativo. Por el 14 método de expansion, el orden se calcula siguiendo los procedimientos a 15 continuación. De la expresión de $T(n)$: 16 17 $$\begin{align} 18 T(n) = 2T\left(\frac{n}{2}\right) + \mathcal{O}(1) 19 \end{align}$$ 20 21 De la ecuación anterior se puede obtener $T\left(\frac{n}{2}\right)$ 22 reemplazando $n$ con $n/2$: 23 24 $$\begin{align} 25 T\left(\frac{n}{2}\right) = 2T\left(\frac{n}{4}\right) + 26 \mathcal{O}(1) 27 \end{align}$$ 28 29 Por lo tanto reemplazando $(2)$ en $(1)$ resulta: 30 31 $$\begin{align} 32 T(n) &= 2\cdotp \left[2T\left(\frac{n}{4}\right) + \mathcal{O}(1)\right] + \mathcal{O}(1) \nonumber\\ 33 &= 4T\left(\frac{n}{4}\right) + 2\mathcal{O}(1) + \mathcal{O}(1) \nonumber\\ 34 &= 4T\left(\frac{n}{4}\right) + 3\mathcal{O}(1) 35 \end{align}$$ 36 37 Pero de $(1)$ también se puede obtener $T\left(\frac{n}{4}\right)$: 38 39 $$\begin{align} 40 T\left(\frac{n}{4}\right) = 2T\left(\frac{n}{8}\right) + \mathcal{O}(1) 41 \end{align}$$ 42 43 Y reemplazando $(4)$ en la ecuación $(3)$: 44 45 $$\begin{align} 46 T(n) &= 4\cdotp \left[2T\left(\frac{n}{8}\right) + \mathcal{O}(1)\right] + 2\mathcal{O}(1) + \mathcal{O}(1) \nonumber\\ 47 &= 8T\left(\frac{n}{8}\right) + 4\mathcal{O}(1) + 2\mathcal{O}(1) + \mathcal{O}(1)\nonumber\\ 48 &= 8T\left(\frac{n}{8}\right) + 7\mathcal{O}(1) 49 \end{align}$$ 50 51 Se puede ver que luego de realizar $k$ veces el mismo procedimiento resulta: 52 53 $$\begin{align} 54 T(n) = 2^{k}\cdotp T\left(\frac{n}{2^k}\right) + (2^{k}-1)\cdotp \mathcal{O}(1) 55 \end{align}$$ 56 57 Pero las iteraciones se terminan cuando el numero de entradas es $1$, entonces 58 en $(6)$: 59 60 $$\begin{align} 61 \frac{n}{2^k} = 1 \Rightarrow n = 2^k \Rightarrow \boxed{log_{2}(n) = k} 62 \end{align}$$ 63 64 Con $(7)$ en $(6)$ resulta 65 66 $$T(n) = n\cdotp T(1) + (n - 1)\cdotp \mathcal{O}(1)$$ 67 68 De la expresión anterior, suponiendo $T(1) = \mathcal{O}(1)$ y aproximando, resulta 69 70 $$\begin{align*} 71 T(n) &= n\cdotp \mathcal{O}(1) + (n - 1)\cdotp \mathcal{O}(1) \\ 72 &= \mathcal{O}(n) + \mathcal{O}(n) \Rightarrow \boxed{T(n) = \mathcal{O}(n)} 73 \end{align*}$$ 74 75 Es decir la complejidad resulta $\mathcal{O}(n)$. El mismo problema se podría haber 76 resuelto utilizando el teorema maestro para la reducción por division, el cual 77 en primer lugar dice que dado un algoritmo con función de costo real $T(n)$ de 78 la siguiente forma: 79 80 $$T(n) = 81 \begin{cases} 82 \hspace{0.75em} c\cdotp n^{k} & \text{si } 1\leq n < b \\ 83 \hspace{0.75em} a\cdotp T\left(\frac{n}{b}\right) + c\cdotp n^{k} & \text{si } n \geq b 84 \end{cases}$$ 85 86 La complejidad algorítmica, o la solución de la ecuación de recurrencia $T(n)$ 87 resulta: 88 89 $$T(n) = 90 \begin{cases} 91 \hspace{0.75em} \mathcal{O}(n^k) & \text{si } a < b^{k} \\ 92 \hspace{0.75em} \mathcal{O}(n^{k}\cdotp log(n)) & \text{si } a = b^{k} \\ 93 \hspace{0.75em} \mathcal{O}(n^{log_{b}(a)}) & \text{si } a > b^{k} 94 \end{cases}$$ 95 96 En este caso se tiene que $T(n)$ es 97 98 $$T(n) = 2T\left(\frac{n}{2}\right) + \mathcal{O}(1)$$ 99 100 Y es de la forma 101 102 $$a\cdotp T\left(\frac{n}{b}\right) + c\cdotp n^{k}$$ 103 104 Con $a=2$, $b=2$, $c=1$ y $k=0$. Por lo tanto, la solución de la ecuación de 105 recurrencia, o la complejidad sale directamente, siendo esta: 106 107 $$T(n) = \mathcal{O}(n^{log_{b}(a)}) = \mathcal{O}(n^{log_{2}(2)}) \Rightarrow \boxed{T(n) = \mathcal{O}(n)}$$ 108 109 Resultando de igual forma que para la complejidad hallada mediante el método de 110 expansión. 111 112 > 2. Un algoritmo busca un valor en un array ordenado reduciendo el problema a 113 > la mitad en cada paso, con un costo constante para la comparación 114 > \vspace{-0.65em} 115 > $$T(n) = T\left(\frac{n}{2}\right) + \mathcal{O}(1)$$ 116 117 Para obtener la complejidad algorítmica, utilizo el método de expansión: 118 119 $$\begin{align} 120 T(n) = T\left(\frac{n}{2}\right) + \mathcal{O}(1) 121 \end{align}$$ 122 123 Pero $T\left(\frac{n}{2}\right)$ resulta de reemplazar $n$ por $\frac{n}{2}$ en 124 $T(n)$, entonces: 125 126 $$\begin{align} 127 T\left(\frac{n}{2}\right) = T\left(\frac{n}{4}\right) + \mathcal{O}(1) 128 \end{align}$$ 129 130 Reemplazando $(9)$ en $(8)$ resulta 131 132 $$\begin{align} 133 T(n) &= T\left(\frac{n}{4}\right) + \mathcal{O}(1) + \mathcal{O}(1) \nonumber\\ 134 &= T\left(\frac{n}{4}\right) + 2\mathcal{O}(1) 135 \end{align}$$ 136 137 Realizando una iteración mas reemplazando $n = \frac{n}{4}$ en $(8)$ resulta 138 139 $$\begin{align} 140 T\left(\frac{n}{4}\right) = T\left(\frac{n}{8}\right) + \mathcal{O}(1) 141 \end{align}$$ 142 143 Y con $(11)$ en $(10)$: 144 145 $$\begin{align} 146 T(n) &= T\left(\frac{n}{8}\right) + \mathcal{O}(1) + \mathcal{O}(1) + \mathcal{O}(1) \nonumber\\ 147 &= T\left(\frac{n}{8}\right) + 3\mathcal{O}(1) 148 \end{align}$$ 149 150 Se puede ver que luego de $k$ veces (o iteraciones) de repetir el procedimiento 151 resulta 152 153 $$\begin{align} 154 T(n) &= T\left(\frac{n}{2^k}\right) + k\cdotp \mathcal{O}(1) 155 \end{align}$$ 156 157 Pero las iteraciones se terminan cuando se llega al caso base, esto es, cuando 158 $\frac{n}{2^k} = 1$ entonces: 159 160 $$\begin{align} 161 \frac{n}{2^k} &= 1 \Rightarrow 2^k = n \Rightarrow \boxed{k = log_{2}(n)} 162 \end{align}$$ 163 164 Reemplazando $(14)$ en $(13)$ 165 166 $$\begin{align} 167 T(n) &= T(1) + log_{2}(n)\cdotp \mathcal{O}(1) 168 \end{align}$$ 169 170 Suponiendo $T(1) = \mathcal{O}(1)$ resulta que 171 172 $$\begin{align} 173 T(n) &= \mathcal{O}(1) + log_{2}(n)\cdotp \mathcal{O}(1) 174 \end{align}$$ 175 176 Por lo tanto la complejidad algorítmica resulta: 177 178 $$\boxed{T(n) = \mathcal{O}(log(n))}$$ 179 180 De manera análoga utilizando el teorema maestro, la expresión de $T(n)$ es de la 181 forma 182 183 $$a\cdotp T\left(\frac{n}{b}\right) + c\cdotp n^{k}$$ 184 185 Con $a = 1$, $b = 2$, $c=1$ y $k=0$, por lo tanto aplicando el teorema maestro 186 para la reducción por division resulta que la complejidad es: 187 188 $$T(n) = \mathcal{O}(n^{k}\cdotp log(n)) = \mathcal{O}(n^{0}\cdotp log(n))$$ 189 190 $$\Rightarrow\boxed{T(n) = \mathcal{O}(log(n))}$$ 191 192 > 3. Un algoritmo suma los elementos de una lista de $n$ números dividiendo la 193 > lista en dos partes de igual tamaño. 194 > \vspace{-0.25em} 195 > $$T(n) = 2T\left(\frac{n}{2}\right) + \mathcal{O}(n)$$ 196 197 En este caso aplico el teorema maestro en caso de poder aplicarse primero y 198 luego comparo con el método de expansión. Se puede ver que $T(n)$ es de la forma 199 200 $$a\cdotp T\left(\frac{n}{b}\right) + c\cdotp n^{k}$$ 201 202 Con $a=2$, $b=2$, $c=1$ y $k=1$, por lo tanto se puede aplicar el teorema 203 maestro y la complejidad algorítmica resulta; 204 205 $$T(n) = \mathcal{O}(n^{k}\cdotp log(n)) = \mathcal{O}(n^{1}\cdotp log(n))$$ 206 207 $$\Rightarrow\boxed{T(n) = \mathcal{O}(n\cdotp log(n))}$$ 208 209 De manera análoga, utilizando el método de expansion: 210 211 $$\begin{align} 212 T(n) = 2T\left(\frac{n}{2}\right) + \mathcal{O}(n) 213 \end{align}$$ 214 215 Pero $T\left(\frac{n}{2}\right)$ resulta de reemplazar $n = 216 \frac{n}{2}$ en $(17)$, de lo cual resulta 217 218 $$\begin{align} 219 T\left(\frac{n}{2}\right) = 2T\left(\frac{n}{4}\right) + \mathcal{O}\left(\frac{n}{2}\right) 220 \end{align}$$ 221 222 Entonces de $(18)$ en $(17)$ 223 224 $$\begin{align} 225 T(n) &= 2\cdotp \left[2 T\left(\frac{n}{4}\right) + \mathcal{O}\left(\frac{n}{2}\right)\right] + \mathcal{O}(n) \nonumber \\ 226 &= 4\cdotp T\left(\frac{n}{4}\right) + 2\cdotp \mathcal{O}\left(\frac{n}{2}\right) + \mathcal{O}(n) 227 \end{align}$$ 228 229 Realizando una iteración más $T\left(\frac{n}{4}\right)$ resulta de reemplazar $n = 230 \frac{n}{4}$ en $(17)$, de lo cual resulta 231 232 $$\begin{align} 233 T\left(\frac{n}{4}\right) = 2T\left(\frac{n}{8}\right) + \mathcal{O}\left(\frac{n}{4}\right) 234 \end{align}$$ 235 236 Y de $(20)$ en $(19)$ 237 238 $$\begin{align} 239 T(n) &= 4\cdotp \left[ 2T\left(\frac{n}{8}\right) + 240 \mathcal{O}\left(\frac{n}{4}\right) \right] + 2\cdotp 241 \mathcal{O}\left(\frac{n}{2}\right) + \mathcal{O}(n) \nonumber \\ 242 &= 8\cdotp T\left(\frac{n}{8}\right) + 243 4\cdotp \mathcal{O}\left(\frac{n}{4}\right) + 244 2\cdotp \mathcal{O}\left(\frac{n}{2}\right) + \mathcal{O}(n) 245 \end{align}$$ 246 247 Es decir, luego de $k$ iteraciones se llega a: 248 249 $$\begin{align} 250 T(n) &= 2^{k}\cdotp T\left(\frac{n}{2^{k}}\right) + 251 \sum^{k-1}_{i=0} 2^{i} \cdotp \mathcal{O}\left(\frac{n}{2^{i}}\right) \nonumber \\ 252 &= 2^{k}\cdotp T\left(\frac{n}{2^{k}}\right) + 253 \sum^{k-1}_{i=0} \mathcal{O}(n) 254 \end{align}$$ 255 256 Pero cuando se llega al caso base se cumple: 257 258 $$\begin{align} 259 \frac{n}{2^{k}} = 1 \Rightarrow 2^{k} = n \Rightarrow\boxed{k = log_{2}(n)} 260 \end{align}$$ 261 262 De $(23)$ en $(22)$: 263 264 $$\begin{align*} 265 T(n) &= n\cdotp T(1) + \sum^{log_{2}(n-1)}_{i=0} \mathcal{O}(n) \\ 266 &= n\cdotp T(1) + log_{2}(n-1) \cdotp \mathcal{O}(n) \\ 267 &= \mathcal{O}(n) + \mathcal{O}(n\cdotp log(n)) 268 \end{align*}$$ 269 270 El termino dominante de la expresión anterior es $n\cdotp log(n)$ entonces: 271 272 $$\Rightarrow\boxed{T(n) = \mathcal{O}(n\cdotp log(n))}$$ 273 274 La expresión anterior coincide con la complejidad algorítmica hallada mediante 275 el método de aplicar el teorema maestro, pero se es evidente que el método de 276 expansion en algunos casos se puede volver mucho mas tedioso en comparación a 277 aplicar el teorema.