Discusión:Paginación

¿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)

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) 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 --Alexrdp 13:47 7 jun 2011 (UTC)