Se pone más lindo y algunos typos

diff --git a/doc/InformeTP3.lyx b/doc/InformeTP3.lyx
index 297889401ee1cb98527a413c4ee312345fe8909c..44480ff8534caa970e9ed20e48cca47b7bf5fe23 100644 (file)
--- 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.
 
 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
  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
 \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 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
 
                 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 
 \layout LyX-Code
 

+
+\size small 

 Dato            | | | | | | | | | | | | | | | | | | | | | | | | | |
 \layout LyX-Code
 
 Dato            | | | | | | | | | | | | | | | | | | | | | | | | | |
 \layout LyX-Code
 

+
+\size small 

                 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
 \layout LyX-Code
 
                 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
 \layout LyX-Code
 

+
+\size small 

                  ^ ^                                             ^
 \layout LyX-Code
 
                  ^ ^                                             ^
 \layout LyX-Code
 

+
+\size small 

 Desplazamientos  | |                                             |
 \layout LyX-Code
 
 Desplazamientos  | |                                             |
 \layout LyX-Code
 

+
+\size small 

      +-+         | |                                             |
 \layout LyX-Code
 
      +-+         | |                                             |
 \layout LyX-Code
 

+
+\size small 

      | |---------+ |                                             |
 \layout LyX-Code
 
      | |---------+ |                                             |
 \layout LyX-Code
 

+
+\size small 

      +-+           |                                             |
 \layout LyX-Code
 
      +-+           |                                             |
 \layout LyX-Code
 

+
+\size small 

      | |-----------+                                             |
 \layout LyX-Code
 
      | |-----------+                                             |
 \layout LyX-Code
 

+
+\size small 

      +-+                                                         |
 \layout LyX-Code
 
      +-+                                                         |
 \layout LyX-Code
 

+
+\size small 

      
 \backslash 
 /
      
 \backslash 
 /


@@ -503,12 +548,18 @@ Desplazamientos  | |                                             |
                                                          |
 \layout LyX-Code
 
                                                          |
 \layout LyX-Code
 

+
+\size small 

      +-+                                                         |
 \layout LyX-Code
 
      +-+                                                         |
 \layout LyX-Code
 

+
+\size small 

      | |---------------------------------------------------------+
 \layout LyX-Code
 
      | |---------------------------------------------------------+
 \layout LyX-Code
 

+
+\size small 

      +-+
 \layout Standard
 
      +-+
 \layout Standard
 


@@ -522,12 +573,24 @@ La posici
  (pos_inicial+n-1)%n)
 \layout Standard
 
  (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
 
 \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
 
 \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
 \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.
  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
 
  Los resultados se dan a continuación, para dos configuraciones de PC distintas:
 \layout Standard
 

+

 \begin_inset Float table
 placement H
 wide false
 \begin_inset Float table
 placement H
 wide false