Tiempo de ejecución: determinación del peor de los casos.

									
// ---------------------------------------------------------------------------------------------------------------------------------------------
// Desarrolle un algoritmo que permita validar si una lista de enteros se compone de una secuencia de elementos de la siguiente forma:
//
//							< P1, P2, P3, ..., Pn, 100, N1, N2, N3, ..., Nm, -100, ... >
//
// - Siendo Pi un entero positivo diferente a 100,
// - Siendo Ni un entero negativo diferente a -100, 
// - Siendo los puntos suspensivos la representación de que el formato anterior podría repetirse de igual manera.

// ---------------------------------------------------------------------------------------------------------------------------------------------

// Ejemplos de listas válidas:

// l1 = < >

// l2 = < 1, 100, -5, -100 >

// l3 = < 1, 2, 3, 100, -1, -2, -3, -100 >

// l4 = < 1, 2, 3, 100, -1, -2, -3, -100, 4, 4, 4, 5, 100, -20, -1, -6,-7, -100 >
								

									
// --------------------------------------------------------------------------------------------------------------------------------------------
// Algoritmo propuesto: 
// Entrada: Ingresa una lista de enteros "lista".
// Salida: Verdadero si cumple con el formato, falso en caso contrario.
// --------------------------------------------------------------------------------------------------------------------------------------------
// ALGORITMO	//	--> TIEMPO ESTIMADO
// --------------------------------------------------------------------------------------------------------------------------------------------
es_valida = verdadero;	//	--> C
elemento = 0; //	--> C

// (1) Consume cada <Spi Sni>
MIENTRAS( NO (es_vacia (lista)) y es_valida){ //	---> a * (T_Cuerpo_mientras)
	
	// (2) Consume la cadena P1, P2, ..., Pn, 100
	MIENTRAS (es_valida y NO (es_vacia (lista)) y elemento != 100){	//	--> (m+1) * C
		
		elemento = quitar_primero (lista);	//	--> C
		es_valida = elemento > 0;	//	--> C
		
	}
	
	// Chequea que se haya consumido efectivamente el valor 100 y queden elementos en la lista
	es_valida = es_valida y (elemento == 100) y NO (es_vacia (lista));	//	--> C
	
	// (3) Consume la cadena N1, N2, ..., Nm, -100
	MIENTRAS (es_valida y NO (es_vacia (lista)) y elemento != -100){ //	--> (l+1) * C
		
		elemento = quitar_primero (lista);	//	--> C
		es_valida = elemento < 0;			//	--> C
	}
	
	// Chequea que se haya consumido efectivamente el valor -100
	es_valida = es_valida y (elemento == -100);	//	--> C
}

RETORNAR es_valida;	//	--> C								

									-----------------------------------------------------------------------------------------------------------------------------------------------
(#) Antes de analizar puntualmente el algoritmo presentado:
1) ¿Cuál es el tiempo de ejecución esperado para una posible solución? --> Se deberán considerar todos los elementos de la lista.
2) ¿En el orden de qué función estará el tiempo de ejecución? --> Debería ser de O(n), siendo n la longitud de la lista de entrada.

-----------------------------------------------------------------------------------------------------------------------------------------------
(#) Analizar el algoritmo propiamente dicho: ¿cómo trabaja? ¿qué realiza? ¿cuáles son los datos de entrada?

-----------------------------------------------------------------------------------------------------------------------------------------------
(#) Vamos a calcular el tiempo de ejecución del algoritmo que valida el formato de la lista.
1) Identificar el o los datos de entrada ---> Único dato de entrada: lista de enteros.
2) Identificar el tamaño del o de los datos de entrada --> Tamaño de la lista: n. 
3) Teniendo en cuenta que n es el tamaño de la entrada, estimaremos T(n), siendo esta función la estimación del tiempo de ejecución del algoritmo que valida el formato de la lista.

-----------------------------------------------------------------------------------------------------------------------------------------------
(#) Respecto al tiempo de ejecución, analizar: ¿cuál será el escenario que representa el peor de los casos?
1) Asumamos que el peor caso se da cuando una cadena es inválida: 

+ Ejemplo 1: < 1, -1, 2, 3, 4, 5, 6, 100, -1, -2, -100, 1, -1, 2, 3, 4, 5, 6, 100, -1, -2, -100>
+ Ejemplo 1: Si la validación falla de forma temprana, no se llegan a analizar todos los enteros, por lo que no estamos en el peor caso respecto a la cantidad de operaciones a realizar. De hecho, la validación podría fallar un par de elementos antes de llegar al final de la cadena, y de nuevo, no se estarían consumiendo todos los elementos de la lista. Entonces, no podemos asumir como peor caso una cadena inválida, dado que el algoritmo se ejecutará parcialmente (informalmente, algún bucle repetitivo mientras no se se ejecutará hasta el final).

+ Ejemplo de cadena válida: con cualquier cadena válida de longitud n, queda claro que el algoritmo deberá validar los n enteros para asegurar que se cumple con el formato. Entonces, se asume como pero caso una cadena válida.

-----------------------------------------------------------------------------------------------------------------------------------------------
(#) Asumiendo que el peor caso se da cuando una cadena es válida, luego:
1) ¿Qué tipo de cadena válida considerar? ¿Cómo se puede especificar para el análisis? 
2) Considerar, sin pérdida de generalidad, una lista válida de longitud n con el siguiente formato:

						< P1, P2, P3, ..., Pm, 100, N1, N2, N3, ..., Nl, -100 >
						
2.1) Considerando esta lista, se puede inferir que:
+ El bucle MIENTRAS (*1) realizará a iteraciones, con a = 1.
+ El bucle MIENTRAS (*2) realizará (m+1) iteraciones, siendo m la cantidad de enteros positivos más uno considerando el valor 100.
+ El bucle MIENTRAS (*3) realizará (l+1) iteraciones, siendo l la cantidad de enteros negativos más uno considerando el valor -100.
+ Luego, el tamaño de la lista se relaciona con las longitudes m y l de la siguiente forma: n = (m+1)+(l+1) --> n = m + l + 2.

2.2) En el código fuente se puede expresar directamente en el código fuente los tiempos asumidos para cada uno de los bloques repetitivos así como para las instrucciones ejecutadas (ver Algoritmo.txt, columna derecha).

2.3) Se puede expresar el tiempo de ejecución (notado como Tiempo_de_subsecuencia(n)) para una lista de longitud n con el formato indicado en 2.1 de la siguiente forma:
+ Tiempo_de_subsecuencia(n) = 1 * ((m+1) * C + (l+1) * C + C)
+ Tiempo_de_subsecuencia(n) = C * ((m+1) + (l+1) + 1) 
+ Tiempo_de_subsecuencia(n) = C * (n + 1), dado que n = (m+1) + (l+1)
+ Tiempo_de_subsecuencia(n) es O(n).

3) Aún cuando el tiempo de ejecución estimado en 2.3) siguiendo el formato especificado en 2) no tiene pérdida de generalidad, es de interés que el tiempo estimado en 2.3) puede generalizarse a una lista de enteros de longitud n, que no sólo considere una secuencia de enteros positivos, separados por 100, seguidos de una secuencia de enteros negativos, separados por -100, sino considerar la lista de la siguiente forma:

3.1) Considerando la lista con formato especificado en el punto 2):

							< P1, P2, P3, ..., Pm, 100, N1, N2, N3, ..., Nl, -100> 
							
se notará esta subsecuencia de la siguiente manera:
													
													< Sp, Sn >
													
de manera tal que una lista de enteros aún más general que la especificada en el punto 2) se puede notar como:
											
											< Sp1, Sn1, ..., Spa, Sna > 
										
siendo Spi y Sni las subsecuencias de elementos positivos y negativos respectivamente, teniendo un total de a subsecuencias < Sp, Sn >

Ejemplo 1: 		< 1, 2, 3, 100, -1, -2, -3, -100, 1, 2, 3, 100, -1, -2, -3, -100 >, n = 16
               < ++++++++++++, ----------------, ++++++++++++, ---------------- >
                      Sp1       	  Sn1            Sp2             Sn2          , a = 2

3.2) A partir de lo notado en el inciso 2.2), se puede expresar el tiempo de ejecución (notado como T(n)) para una lista de longitud n con el formato indicado en 3.1) de la siguiente forma:

T(n) = Suma desde 1 hasta a ( Tiempo_de_subsecuencia(x) ), x es el tamaño de la subsecuencia S = <Spi, Sni>.

Teniendo en cuenta el Tiempo_de_subsecuncia(x) determinado en 2.3), luego:

T(n) = Suma desde 1 hasta a ( C * (x + 1))

Los diferentes valores de x pueden ser acotados de forma general como x = C * n/a, siendo C una constante que aproxima cada una de las cantidades de <Sp, Sn>.

T(n) = Suma desde 1 hasta a ( C * (x + 1)), asumiendo x acotado por n/a, luego:
T(n) = (a-1+1) * ( C * ( n/a + 1 ) ),
T(n) = a * ( C * n/a + C )
T(n) = a * C * n/a + a * C
T(n) = C * n + a * C, teniendo en cuenta que a << n
T(n) = C * n + n * C
T(n) = 2n * C
T(n) es O(n)