commit bab6eca0bb628b981f82ad361f81d86e082816fd
parent dce0a43e6dd580a5f17fccf44e73b37c7b6dc7dc
Author: Martin Kloeckner <mjkloeckner@gmail.com>
Date: Tue, 15 Jul 2025 11:16:33 -0300
use `\mathcal{O}` instead of `\Omicron`
or `\mathcal{O}(n)` instead of `\Omicron(n)`
Diffstat:
3 files changed, 71 insertions(+), 71 deletions(-)
diff --git a/guias/complejidad_algoritmica/complejidad_algoritmica.md b/guias/complejidad_algoritmica/complejidad_algoritmica.md
@@ -7,7 +7,7 @@ Martin Klöckner - [mklockner@fi.uba.ar](mailto:mklockner@fi.uba.ar)
> $n/2$ con un costo constante en cada paso adicional, obtener la complejidad
> sabiendo que el costo real $T(n)$ es:
> \vspace{-0.65em}
-> $$T(n) = 2T\left(\frac{n}{2}\right) + \Omicron(1)$$
+> $$T(n) = 2T\left(\frac{n}{2}\right) + \mathcal{O}(1)$$
Como la función de costo real $T(n)$ depende de la misma función $T(n)$ pero con
una entrada menor $n/2$ se trata de un algoritmo recursivo o iterativo. Por el
@@ -15,7 +15,7 @@ método de expansion, el orden se calcula siguiendo los procedimientos a
continuación. De la expresión de $T(n)$:
$$\begin{align}
-T(n) = 2T\left(\frac{n}{2}\right) + \Omicron(1)
+T(n) = 2T\left(\frac{n}{2}\right) + \mathcal{O}(1)
\end{align}$$
De la ecuación anterior se puede obtener $T\left(\frac{n}{2}\right)$
@@ -23,35 +23,35 @@ reemplazando $n$ con $n/2$:
$$\begin{align}
T\left(\frac{n}{2}\right) = 2T\left(\frac{n}{4}\right) +
-\Omicron(1)
+\mathcal{O}(1)
\end{align}$$
Por lo tanto reemplazando $(2)$ en $(1)$ resulta:
$$\begin{align}
-T(n) &= 2\cdotp \left[2T\left(\frac{n}{4}\right) + \Omicron(1)\right] + \Omicron(1) \nonumber\\
- &= 4T\left(\frac{n}{4}\right) + 2\Omicron(1) + \Omicron(1) \nonumber\\
- &= 4T\left(\frac{n}{4}\right) + 3\Omicron(1)
+T(n) &= 2\cdotp \left[2T\left(\frac{n}{4}\right) + \mathcal{O}(1)\right] + \mathcal{O}(1) \nonumber\\
+ &= 4T\left(\frac{n}{4}\right) + 2\mathcal{O}(1) + \mathcal{O}(1) \nonumber\\
+ &= 4T\left(\frac{n}{4}\right) + 3\mathcal{O}(1)
\end{align}$$
Pero de $(1)$ también se puede obtener $T\left(\frac{n}{4}\right)$:
$$\begin{align}
-T\left(\frac{n}{4}\right) = 2T\left(\frac{n}{8}\right) + \Omicron(1)
+T\left(\frac{n}{4}\right) = 2T\left(\frac{n}{8}\right) + \mathcal{O}(1)
\end{align}$$
Y reemplazando $(4)$ en la ecuación $(3)$:
$$\begin{align}
-T(n) &= 4\cdotp \left[2T\left(\frac{n}{8}\right) + \Omicron(1)\right] + 2\Omicron(1) + \Omicron(1) \nonumber\\
- &= 8T\left(\frac{n}{8}\right) + 4\Omicron(1) + 2\Omicron(1) + \Omicron(1)\nonumber\\
- &= 8T\left(\frac{n}{8}\right) + 7\Omicron(1)
+T(n) &= 4\cdotp \left[2T\left(\frac{n}{8}\right) + \mathcal{O}(1)\right] + 2\mathcal{O}(1) + \mathcal{O}(1) \nonumber\\
+ &= 8T\left(\frac{n}{8}\right) + 4\mathcal{O}(1) + 2\mathcal{O}(1) + \mathcal{O}(1)\nonumber\\
+ &= 8T\left(\frac{n}{8}\right) + 7\mathcal{O}(1)
\end{align}$$
Se puede ver que luego de realizar $k$ veces el mismo procedimiento resulta:
$$\begin{align}
-T(n) = 2^{k}\cdotp T\left(\frac{n}{2^k}\right) + (2^{k}-1)\cdotp \Omicron(1)
+T(n) = 2^{k}\cdotp T\left(\frac{n}{2^k}\right) + (2^{k}-1)\cdotp \mathcal{O}(1)
\end{align}$$
Pero las iteraciones se terminan cuando el numero de entradas es $1$, entonces
@@ -63,16 +63,16 @@ $$\begin{align}
Con $(7)$ en $(6)$ resulta
-$$T(n) = n\cdotp T(1) + (n - 1)\cdotp \Omicron(1)$$
+$$T(n) = n\cdotp T(1) + (n - 1)\cdotp \mathcal{O}(1)$$
-De la expresión anterior, suponiendo $T(1) = \Omicron(1)$ y aproximando, resulta
+De la expresión anterior, suponiendo $T(1) = \mathcal{O}(1)$ y aproximando, resulta
$$\begin{align*}
-T(n) &= n\cdotp \Omicron(1) + (n - 1)\cdotp \Omicron(1) \\
- &= \Omicron(n) + \Omicron(n) \Rightarrow \boxed{T(n) = \Omicron(n)}
+T(n) &= n\cdotp \mathcal{O}(1) + (n - 1)\cdotp \mathcal{O}(1) \\
+ &= \mathcal{O}(n) + \mathcal{O}(n) \Rightarrow \boxed{T(n) = \mathcal{O}(n)}
\end{align*}$$
-Es decir la complejidad resulta $\Omicron(n)$. El mismo problema se podría haber
+Es decir la complejidad resulta $\mathcal{O}(n)$. El mismo problema se podría haber
resuelto utilizando el teorema maestro para la reducción por division, el cual
en primer lugar dice que dado un algoritmo con función de costo real $T(n)$ de
la siguiente forma:
@@ -88,14 +88,14 @@ resulta:
$$T(n) =
\begin{cases}
-\hspace{0.75em} \Omicron(n^k) & \text{si } a < b^{k} \\
-\hspace{0.75em} \Omicron(n^{k}\cdotp log(n)) & \text{si } a = b^{k} \\
-\hspace{0.75em} \Omicron(n^{log_{b}(a)}) & \text{si } a > b^{k}
+\hspace{0.75em} \mathcal{O}(n^k) & \text{si } a < b^{k} \\
+\hspace{0.75em} \mathcal{O}(n^{k}\cdotp log(n)) & \text{si } a = b^{k} \\
+\hspace{0.75em} \mathcal{O}(n^{log_{b}(a)}) & \text{si } a > b^{k}
\end{cases}$$
En este caso se tiene que $T(n)$ es
-$$T(n) = 2T\left(\frac{n}{2}\right) + \Omicron(1)$$
+$$T(n) = 2T\left(\frac{n}{2}\right) + \mathcal{O}(1)$$
Y es de la forma
@@ -104,7 +104,7 @@ $$a\cdotp T\left(\frac{n}{b}\right) + c\cdotp n^{k}$$
Con $a=2$, $b=2$, $c=1$ y $k=0$. Por lo tanto, la solución de la ecuación de
recurrencia, o la complejidad sale directamente, siendo esta:
-$$T(n) = \Omicron(n^{log_{b}(a)}) = \Omicron(n^{log_{2}(2)}) \Rightarrow \boxed{T(n) = \Omicron(n)}$$
+$$T(n) = \mathcal{O}(n^{log_{b}(a)}) = \mathcal{O}(n^{log_{2}(2)}) \Rightarrow \boxed{T(n) = \mathcal{O}(n)}$$
Resultando de igual forma que para la complejidad hallada mediante el método de
expansión.
@@ -112,46 +112,46 @@ expansión.
> 2. Un algoritmo busca un valor en un array ordenado reduciendo el problema a
> la mitad en cada paso, con un costo constante para la comparación
> \vspace{-0.65em}
-> $$T(n) = T\left(\frac{n}{2}\right) + \Omicron(1)$$
+> $$T(n) = T\left(\frac{n}{2}\right) + \mathcal{O}(1)$$
Para obtener la complejidad algorítmica, utilizo el método de expansión:
$$\begin{align}
-T(n) = T\left(\frac{n}{2}\right) + \Omicron(1)
+T(n) = T\left(\frac{n}{2}\right) + \mathcal{O}(1)
\end{align}$$
Pero $T\left(\frac{n}{2}\right)$ resulta de reemplazar $n$ por $\frac{n}{2}$ en
$T(n)$, entonces:
$$\begin{align}
-T\left(\frac{n}{2}\right) = T\left(\frac{n}{4}\right) + \Omicron(1)
+T\left(\frac{n}{2}\right) = T\left(\frac{n}{4}\right) + \mathcal{O}(1)
\end{align}$$
Reemplazando $(9)$ en $(8)$ resulta
$$\begin{align}
-T(n) &= T\left(\frac{n}{4}\right) + \Omicron(1) + \Omicron(1) \nonumber\\
- &= T\left(\frac{n}{4}\right) + 2\Omicron(1)
+T(n) &= T\left(\frac{n}{4}\right) + \mathcal{O}(1) + \mathcal{O}(1) \nonumber\\
+ &= T\left(\frac{n}{4}\right) + 2\mathcal{O}(1)
\end{align}$$
Realizando una iteración mas reemplazando $n = \frac{n}{4}$ en $(8)$ resulta
$$\begin{align}
-T\left(\frac{n}{4}\right) = T\left(\frac{n}{8}\right) + \Omicron(1)
+T\left(\frac{n}{4}\right) = T\left(\frac{n}{8}\right) + \mathcal{O}(1)
\end{align}$$
Y con $(11)$ en $(10)$:
$$\begin{align}
-T(n) &= T\left(\frac{n}{8}\right) + \Omicron(1) + \Omicron(1) + \Omicron(1) \nonumber\\
- &= T\left(\frac{n}{8}\right) + 3\Omicron(1)
+T(n) &= T\left(\frac{n}{8}\right) + \mathcal{O}(1) + \mathcal{O}(1) + \mathcal{O}(1) \nonumber\\
+ &= T\left(\frac{n}{8}\right) + 3\mathcal{O}(1)
\end{align}$$
Se puede ver que luego de $k$ veces (o iteraciones) de repetir el procedimiento
resulta
$$\begin{align}
-T(n) &= T\left(\frac{n}{2^k}\right) + k\cdotp \Omicron(1)
+T(n) &= T\left(\frac{n}{2^k}\right) + k\cdotp \mathcal{O}(1)
\end{align}$$
Pero las iteraciones se terminan cuando se llega al caso base, esto es, cuando
@@ -164,18 +164,18 @@ $$\begin{align}
Reemplazando $(14)$ en $(13)$
$$\begin{align}
-T(n) &= T(1) + log_{2}(n)\cdotp \Omicron(1)
+T(n) &= T(1) + log_{2}(n)\cdotp \mathcal{O}(1)
\end{align}$$
-Suponiendo $T(1) = \Omicron(1)$ resulta que
+Suponiendo $T(1) = \mathcal{O}(1)$ resulta que
$$\begin{align}
-T(n) &= \Omicron(1) + log_{2}(n)\cdotp \Omicron(1)
+T(n) &= \mathcal{O}(1) + log_{2}(n)\cdotp \mathcal{O}(1)
\end{align}$$
Por lo tanto la complejidad algorítmica resulta:
-$$\boxed{T(n) = \Omicron(log(n))}$$
+$$\boxed{T(n) = \mathcal{O}(log(n))}$$
De manera análoga utilizando el teorema maestro, la expresión de $T(n)$ es de la
forma
@@ -185,14 +185,14 @@ $$a\cdotp T\left(\frac{n}{b}\right) + c\cdotp n^{k}$$
Con $a = 1$, $b = 2$, $c=1$ y $k=0$, por lo tanto aplicando el teorema maestro
para la reducción por division resulta que la complejidad es:
-$$T(n) = \Omicron(n^{k}\cdotp log(n)) = \Omicron(n^{0}\cdotp log(n))$$
+$$T(n) = \mathcal{O}(n^{k}\cdotp log(n)) = \mathcal{O}(n^{0}\cdotp log(n))$$
-$$\Rightarrow\boxed{T(n) = \Omicron(log(n))}$$
+$$\Rightarrow\boxed{T(n) = \mathcal{O}(log(n))}$$
> 3. Un algoritmo suma los elementos de una lista de $n$ números dividiendo la
> lista en dos partes de igual tamaño.
> \vspace{-0.25em}
-> $$T(n) = 2T\left(\frac{n}{2}\right) + \Omicron(n)$$
+> $$T(n) = 2T\left(\frac{n}{2}\right) + \mathcal{O}(n)$$
En este caso aplico el teorema maestro en caso de poder aplicarse primero y
luego comparo con el método de expansión. Se puede ver que $T(n)$ es de la forma
@@ -202,55 +202,55 @@ $$a\cdotp T\left(\frac{n}{b}\right) + c\cdotp n^{k}$$
Con $a=2$, $b=2$, $c=1$ y $k=1$, por lo tanto se puede aplicar el teorema
maestro y la complejidad algorítmica resulta;
-$$T(n) = \Omicron(n^{k}\cdotp log(n)) = \Omicron(n^{1}\cdotp log(n))$$
+$$T(n) = \mathcal{O}(n^{k}\cdotp log(n)) = \mathcal{O}(n^{1}\cdotp log(n))$$
-$$\Rightarrow\boxed{T(n) = \Omicron(n\cdotp log(n))}$$
+$$\Rightarrow\boxed{T(n) = \mathcal{O}(n\cdotp log(n))}$$
De manera análoga, utilizando el método de expansion:
$$\begin{align}
-T(n) = 2T\left(\frac{n}{2}\right) + \Omicron(n)
+T(n) = 2T\left(\frac{n}{2}\right) + \mathcal{O}(n)
\end{align}$$
Pero $T\left(\frac{n}{2}\right)$ resulta de reemplazar $n =
\frac{n}{2}$ en $(17)$, de lo cual resulta
$$\begin{align}
-T\left(\frac{n}{2}\right) = 2T\left(\frac{n}{4}\right) + \Omicron\left(\frac{n}{2}\right)
+T\left(\frac{n}{2}\right) = 2T\left(\frac{n}{4}\right) + \mathcal{O}\left(\frac{n}{2}\right)
\end{align}$$
Entonces de $(18)$ en $(17)$
$$\begin{align}
-T(n) &= 2\cdotp \left[2 T\left(\frac{n}{4}\right) + \Omicron\left(\frac{n}{2}\right)\right] + \Omicron(n) \nonumber \\
- &= 4\cdotp T\left(\frac{n}{4}\right) + 2\cdotp \Omicron\left(\frac{n}{2}\right) + \Omicron(n)
+T(n) &= 2\cdotp \left[2 T\left(\frac{n}{4}\right) + \mathcal{O}\left(\frac{n}{2}\right)\right] + \mathcal{O}(n) \nonumber \\
+ &= 4\cdotp T\left(\frac{n}{4}\right) + 2\cdotp \mathcal{O}\left(\frac{n}{2}\right) + \mathcal{O}(n)
\end{align}$$
Realizando una iteración más $T\left(\frac{n}{4}\right)$ resulta de reemplazar $n =
\frac{n}{4}$ en $(17)$, de lo cual resulta
$$\begin{align}
-T\left(\frac{n}{4}\right) = 2T\left(\frac{n}{8}\right) + \Omicron\left(\frac{n}{4}\right)
+T\left(\frac{n}{4}\right) = 2T\left(\frac{n}{8}\right) + \mathcal{O}\left(\frac{n}{4}\right)
\end{align}$$
Y de $(20)$ en $(19)$
$$\begin{align}
T(n) &= 4\cdotp \left[ 2T\left(\frac{n}{8}\right) +
- \Omicron\left(\frac{n}{4}\right) \right] + 2\cdotp
- \Omicron\left(\frac{n}{2}\right) + \Omicron(n) \nonumber \\
+ \mathcal{O}\left(\frac{n}{4}\right) \right] + 2\cdotp
+ \mathcal{O}\left(\frac{n}{2}\right) + \mathcal{O}(n) \nonumber \\
&= 8\cdotp T\left(\frac{n}{8}\right) +
- 4\cdotp \Omicron\left(\frac{n}{4}\right) +
- 2\cdotp \Omicron\left(\frac{n}{2}\right) + \Omicron(n)
+ 4\cdotp \mathcal{O}\left(\frac{n}{4}\right) +
+ 2\cdotp \mathcal{O}\left(\frac{n}{2}\right) + \mathcal{O}(n)
\end{align}$$
Es decir, luego de $k$ iteraciones se llega a:
$$\begin{align}
T(n) &= 2^{k}\cdotp T\left(\frac{n}{2^{k}}\right) +
- \sum^{k-1}_{i=0} 2^{i} \cdotp \Omicron\left(\frac{n}{2^{i}}\right) \nonumber \\
+ \sum^{k-1}_{i=0} 2^{i} \cdotp \mathcal{O}\left(\frac{n}{2^{i}}\right) \nonumber \\
&= 2^{k}\cdotp T\left(\frac{n}{2^{k}}\right) +
- \sum^{k-1}_{i=0} \Omicron(n)
+ \sum^{k-1}_{i=0} \mathcal{O}(n)
\end{align}$$
Pero cuando se llega al caso base se cumple:
@@ -262,14 +262,14 @@ $$\begin{align}
De $(23)$ en $(22)$:
$$\begin{align*}
-T(n) &= n\cdotp T(1) + \sum^{log_{2}(n-1)}_{i=0} \Omicron(n) \\
- &= n\cdotp T(1) + log_{2}(n-1) \cdotp \Omicron(n) \\
- &= \Omicron(n) + \Omicron(n\cdotp log(n))
+T(n) &= n\cdotp T(1) + \sum^{log_{2}(n-1)}_{i=0} \mathcal{O}(n) \\
+ &= n\cdotp T(1) + log_{2}(n-1) \cdotp \mathcal{O}(n) \\
+ &= \mathcal{O}(n) + \mathcal{O}(n\cdotp log(n))
\end{align*}$$
El termino dominante de la expresión anterior es $n\cdotp log(n)$ entonces:
-$$\Rightarrow\boxed{T(n) = \Omicron(n\cdotp log(n))}$$
+$$\Rightarrow\boxed{T(n) = \mathcal{O}(n\cdotp log(n))}$$
La expresión anterior coincide con la complejidad algorítmica hallada mediante
el método de aplicar el teorema maestro, pero se es evidente que el método de
diff --git a/guias/complejidad_algoritmica/complejidad_algoritmica.pdf b/guias/complejidad_algoritmica/complejidad_algoritmica.pdf
Binary files differ.
diff --git a/notas/complejidad_algoritmica/complejidad_algoritmica.md b/notas/complejidad_algoritmica/complejidad_algoritmica.md
@@ -134,7 +134,7 @@ La cota que mejor aproxima (Theta $\Theta$) hace referencia a una funcion que
acota tanto inferiormente como superiormente al tiempo real $T(n)$ de un
algoritmo dado para un $n$ suficientemente grande.
-### Cota superior $\Omicron$
+### Cota superior $\mathcal{O}$
La cota superior hace referencia a una función que acota el crecimiento del
número de operaciones elementales o tiempo de ejecución de un algoritmo en el
@@ -152,38 +152,38 @@ diferencia.
El orden expresa el comportamiento dominante de un algoritmo para un número de
entradas $n$ suficientemente grande, en la practica se suele tomar como si fuera
la cota superior, aunque por definición no lo es. Por definición se dice que
-$T(n)$ es de orden $g(n)$ (o pertenece a) $\Omicron(g(n))$ si y solo si existen
+$T(n)$ es de orden $g(n)$ (o pertenece a) $\mathcal{O}(g(n))$ si y solo si existen
constantes positivas $c$ y $n_{0}$, tales que se verifica para todo $n > n_{0}$
lo siguiente
$$0 \leq T(n) \leq c*g(n)\hspace{1em} \forall n \geq n_{0}$$
En general en los casos en donde $T(n)$ se expresa como un polinomio, el orden
-$\Omicron$ del algoritmo, es el termino de mayor grado de $T(n)$
+$\mathcal{O}$ del algoritmo, es el termino de mayor grado de $T(n)$
Los ordenes mas comunes entre diferentes algoritmos se pueden ordenar en forma
creciente en cuanto a complejidad algorítmica, esto permite comparar la
eficiencia entre los algoritmos:
-$$ \Omicron(1) \subset \Omicron(log(n)) \subset \Omicron(n) \subset
-\Omicron(n*log(n)) \subset \Omicron(n^2) \subset \Omicron(n^3) \subset ...
-\subset \Omicron(2^n) \subset \Omicron(n!)$$
+$$ \mathcal{O}(1) \subset \mathcal{O}(log(n)) \subset \mathcal{O}(n) \subset
+\mathcal{O}(n*log(n)) \subset \mathcal{O}(n^2) \subset \mathcal{O}(n^3) \subset ...
+\subset \mathcal{O}(2^n) \subset \mathcal{O}(n!)$$
#### Propiedades del orden
-1. $f$ es $\Omicron(f)$ entonces $f$ esta acotada por su orden
-2. $\Omicron(f)$ es $\Omicron(g) \Rightarrow \Omicron(f)$ esta incluido en
- $\Omicron(g)$ y viceversa
-3. $\Omicron(f) = \Omicron(g)$ $\Leftrightarrow$ $f$ es $\Omicron(g)$ y $g$ es
- $\Omicron(f)$
-4. Si $f$ es $\Omicron(g)$ y $g$ es $\Omicron(h)$ $\Rightarrow$ $f$ es $\Omicron(h)$
-5. Si $f$ es $\Omicron(g)$ y $f$ es $\Omicron(h)$ $\Rightarrow$ $f$ es $\Omicron(min(g, h))$
-6. [Regla de la suma] Si $f_{1}$ es $\Omicron(g)$ y $f_{2}$ es $\Omicron(h)$
- $\Rightarrow$ $f_{1} + f_{2}$ es $\Omicron(max(g, h))$
-7. [Regla del producto] Si $f_{1}$ es $\Omicron(g)$ y $f_{2}$ es $\Omicron(h)$
- $\Rightarrow$ $f_{1} * f_{2}$ es $\Omicron(g*h)$
+1. $f$ es $\mathcal{O}(f)$ entonces $f$ esta acotada por su orden
+2. $\mathcal{O}(f)$ es $\mathcal{O}(g) \Rightarrow \mathcal{O}(f)$ esta incluido en
+ $\mathcal{O}(g)$ y viceversa
+3. $\mathcal{O}(f) = \mathcal{O}(g)$ $\Leftrightarrow$ $f$ es $\mathcal{O}(g)$ y $g$ es
+ $\mathcal{O}(f)$
+4. Si $f$ es $\mathcal{O}(g)$ y $g$ es $\mathcal{O}(h)$ $\Rightarrow$ $f$ es $\mathcal{O}(h)$
+5. Si $f$ es $\mathcal{O}(g)$ y $f$ es $\mathcal{O}(h)$ $\Rightarrow$ $f$ es $\mathcal{O}(min(g, h))$
+6. [Regla de la suma] Si $f_{1}$ es $\mathcal{O}(g)$ y $f_{2}$ es $\mathcal{O}(h)$
+ $\Rightarrow$ $f_{1} + f_{2}$ es $\mathcal{O}(max(g, h))$
+7. [Regla del producto] Si $f_{1}$ es $\mathcal{O}(g)$ y $f_{2}$ es $\mathcal{O}(h)$
+ $\Rightarrow$ $f_{1} * f_{2}$ es $\mathcal{O}(g*h)$
## Complejidad algorítmica de algoritmos recursivos
