Discusión:Paginación - Historial de revisiones

Alexrdp en 13:47 7 jun 2011

2011-06-07T13:47:13Z

Ajaest en 11:53 7 jun 2011

2011-06-07T11:53:26Z

Ajaest en 11:51 7 jun 2011

2011-06-07T11:51:49Z

Ajaest: Pregunta sobre administración usando Mapa de Bits vs Listas

2011-06-07T11:51:25Z

Pregunta sobre administración usando Mapa de Bits vs Listas

Página nueva

¿Los mapas de bits no son de O(n) frente a las listas que son de O(1)? Lo digo porque:
*Para encontrar un espacio libre en el mapa de bits hay que recorrer toda la lista hasta encontrar una página libre, en cuyo caso hemos recorrido n elementos
*Para encontrar una página libre en la lista solo hay que hacer un pull sobre el FIFO de páginas libres, por lo tanto orden constante O(1)

← Revisión anterior		Revisión del 13:47 7 jun 2011
Línea 5:		Línea 5:
	Si lo pregunto y no lo corrijo directamente es porque en los apuntes que tomé en clase también tengo que los mapas de bits son de O(1)		Si lo pregunto y no lo corrijo directamente es porque en los apuntes que tomé en clase también tengo que los mapas de bits son de O(1)
	[[Usuario:Ajaest\|ajaest]] 11:51 7 jun 2011 (UTC)		[[Usuario:Ajaest\|ajaest]] 11:51 7 jun 2011 (UTC)
		+
		+
		+	Ambas son de orden constante: El número de elementos de un mapa de bits es siempre el mismo. Sería O(n) en el caso de que el número de bits fuese variable.
		+	Por ejemplo, cuando se recorre un array en el que se sabe que el tamaño es 10, ese bucle se considera de orden constante. Por el contrario, en una lista enlazada, como no se sabe de antemano cuantos elementos se van a recorrer, el algoritmo resultante es de orden lineal --[[Usuario:Alexrdp\|Alexrdp]] 13:47 7 jun 2011 (UTC)

← Revisión anterior		Revisión del 11:53 7 jun 2011
Línea 3:		Línea 3:
	*Para encontrar una página libre en la lista solo hay que hacer un pull sobre el FIFO de páginas libres, por lo tanto orden constante O(1)		*Para encontrar una página libre en la lista solo hay que hacer un pull sobre el FIFO de páginas libres, por lo tanto orden constante O(1)

		+	Si lo pregunto y no lo corrijo directamente es porque en los apuntes que tomé en clase también tengo que los mapas de bits son de O(1)
	[[Usuario:Ajaest\|ajaest]] 11:51 7 jun 2011 (UTC)		[[Usuario:Ajaest\|ajaest]] 11:51 7 jun 2011 (UTC)

← Revisión anterior		Revisión del 11:51 7 jun 2011
Línea 2:		Línea 2:
	*Para encontrar un espacio libre en el mapa de bits hay que recorrer toda la lista hasta encontrar una página libre, en cuyo caso hemos recorrido n elementos		*Para encontrar un espacio libre en el mapa de bits hay que recorrer toda la lista hasta encontrar una página libre, en cuyo caso hemos recorrido n elementos
	*Para encontrar una página libre en la lista solo hay que hacer un pull sobre el FIFO de páginas libres, por lo tanto orden constante O(1)		*Para encontrar una página libre en la lista solo hay que hacer un pull sobre el FIFO de páginas libres, por lo tanto orden constante O(1)
		+
		+	[[Usuario:Ajaest\|ajaest]] 11:51 7 jun 2011 (UTC)