From e23ac6d55a1cc9a9a98f15c405438d0cb11dac4c Mon Sep 17 00:00:00 2001
From: Ricardo Markiewicz <gazer.arg@gmail.com>
Date: Mon, 28 Jun 2004 06:45:45 +0000
Subject: [PATCH] =?utf8?q?=20Se=20pone=20m=C3=A1s=20lindo=20y=20algunos=20?=
 =?utf8?q?typos?=
MIME-Version: 1.0
Content-Type: text/plain; charset=utf8
Content-Transfer-Encoding: 8bit

---
 doc/InformeTP3.lyx | 92 ++++++++++++++++++++++++++++++++++++++++------
 1 file changed, 80 insertions(+), 12 deletions(-)

diff --git a/doc/InformeTP3.lyx b/doc/InformeTP3.lyx
index 2978894..44480ff 100644
--- a/doc/InformeTP3.lyx
+++ b/doc/InformeTP3.lyx
@@ -429,8 +429,15 @@ desde ahora lo llamaremos BS, para minimizar la notaci
 
 En una implementación simple, el BS debe crear una matriz y crear todos
  los desplazamientos sobre ella.
- Esto hace que se necesito O(n^2) en memoria, donde n es la longitud del
- vector sobre el cual se quiere operar.
+ Esto hace que se necesito 
+\begin_inset Formula $O(n^{2})$
+\end_inset 
+
+ en memoria, donde 
+\begin_inset Formula $n$
+\end_inset 
+
+ es la longitud del vector sobre el cual se quiere operar.
  Claramente es un problema, ya que para una página pequeña, digamos 1kb,
  se necesita una matriz de 1Mb.
 \layout Standard
@@ -455,47 +462,85 @@ Se ha optado por utilizar el qsort de la libc por ser ANSI-C y tener una
 \layout Standard
 
 Como última opción se estudió el Radix Sort, ya que justamente nuestro dato
- a ordenar es de longitud fija n y se cuenta con un conjunto de L=255 elementos
- posibles a aparecer en el dato.
- El orden de éste método sería O(n*L), pero para que realmente el Radix
- Sort sea efectivo, se requiere que L < log2(n) = 15, por lo que no convenía
- tampoco.
+ a ordenar es de longitud fija 
+\begin_inset Formula $n$
+\end_inset 
+
+ y se cuenta con un conjunto de 
+\begin_inset Formula $L=255$
+\end_inset 
+
+ elementos posibles a aparecer en el dato.
+ El orden de éste método sería 
+\begin_inset Formula $O(n*L)$
+\end_inset 
+
+, pero para que realmente el Radix Sort sea efectivo, se requiere que 
+\begin_inset Formula $255=L<log_{2}(n)=15$
+\end_inset 
+
+, por lo que fue descartado.
 \layout Standard
 
 Para solucionar el problema del consumo de memoria se plateó un esquema
  como el que se indica a continuación :
 \layout LyX-Code
 
+               
+\layout LyX-Code
+
+
+\size small 
                 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 
 \layout LyX-Code
 
+
+\size small 
 Dato            | | | | | | | | | | | | | | | | | | | | | | | | | |
 \layout LyX-Code
 
+
+\size small 
                 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
 \layout LyX-Code
 
+
+\size small 
                  ^ ^                                             ^
 \layout LyX-Code
 
+
+\size small 
 Desplazamientos  | |                                             |
 \layout LyX-Code
 
+
+\size small 
      +-+         | |                                             |
 \layout LyX-Code
 
+
+\size small 
      | |---------+ |                                             |
 \layout LyX-Code
 
+
+\size small 
      +-+           |                                             |
 \layout LyX-Code
 
+
+\size small 
      | |-----------+                                             |
 \layout LyX-Code
 
+
+\size small 
      +-+                                                         |
 \layout LyX-Code
 
+
+\size small 
      
 \backslash 
 /
@@ -503,12 +548,18 @@ Desplazamientos  | |                                             |
                                                          |
 \layout LyX-Code
 
+
+\size small 
      +-+                                                         |
 \layout LyX-Code
 
+
+\size small 
      | |---------------------------------------------------------+
 \layout LyX-Code
 
+
+\size small 
      +-+
 \layout Standard
 
@@ -522,12 +573,24 @@ La posici
  (pos_inicial+n-1)%n)
 \layout Standard
 
-La ganancia de este método es que se utilizan 2*n bytes de memoria solamente,
- es decir, que se bajo a O(n) el orden en memoria del algoritmo.
+La ganancia de este método es que se utilizan 
+\begin_inset Formula $2*n$
+\end_inset 
+
+ bytes de memoria solamente, es decir, que se bajó a O(n) el orden en memoria
+ del algoritmo.
 \layout Standard
 
-Luego de inicializar el vector Desplazamiento (esta parte es O(n) en tiempo)
- se ordena el vector utilizando el qsort, que es del orden de O(n*log(n))
+Luego de inicializar el vector Desplazamiento (esta parte es 
+\begin_inset Formula $O(n)$
+\end_inset 
+
+ en tiempo) se ordena el vector utilizando el qsort, que es del orden de
+ 
+\begin_inset Formula $O(n*log_{2}(n))$
+\end_inset 
+
+
 \begin_inset Foot
 collapsed true
 
@@ -544,7 +607,11 @@ En realidad es del orden de O(1.44*n*log2(n)), para el caso promedio.
 \layout Standard
 
 Se debe aclara que los órdenes estimados más arriba se basan en la suposición
- de que el orden de una comparación en O(1).
+ de que el orden de una comparación en 
+\begin_inset Formula $O(1)$
+\end_inset 
+
+.
  En el caso de tener que comprimir archivos donde los desplazamientos queden
  iguales o solo cambien sobre el final, los órdenes se ven muy afectados.
  Sin embargo, para el caso promedio no se comporta tan mal.
@@ -1023,6 +1090,7 @@ Se prueba el set de Calgary utilizando nuestro compresor, y enfrentandolo
  Los resultados se dan a continuación, para dos configuraciones de PC distintas:
 \layout Standard
 
+
 \begin_inset Float table
 placement H
 wide false
-- 
2.43.0