El otro día un alumno del curso de preparación del examen 70-536 en campusMVP me hizo la siguiente (interesante) pregunta:
"He revisando el tema de las coleciones y me han surgido las siguentes dudas: Al leer en el MSDN información sobre distintas colecciones a veces aparece la siguiente frase: 'La recuperación del valor de esta propiedad es una operación O(1); el establecimiento de la propiedad también es una operación O(1).' ¿exactamente a que se refiere con operación O(1)? El ejemplo que he puesto pertenece a ArrayList.Item (Propiedad) http://msdn.microsoft.com/es-es/library/system.collections.arraylist.item.aspx"
¿Y esto qué es?
Lo de 0(1) es una notación matemática usada en algoritmia que indica el comportamiento límite de una función. A este tipo de notación se le llama "notación asintótica", "notación Landau" o "notación Big O".
En la wikipedia hay un artículo muy completo sobre esta notación, pero básicamente lo que hay que saber para "andar por casa" es que lo que significa que un algoritmo 0(1) es que éste tarda lo mismo en ejecutarse para cualquiera de sus elementos. Bueno, en realidad lo exacto no sería decir que "tarda lo mismo", sino más bien que "en términos computacionales el esfuerzo necesario para procesarlo es el mismo", lo cual en muchos casos se traduce en el mismo tiempo.
Así por ejemplo en el caso de la pregunta, la extracción de un elemento de la lista especializada ArrayList a través de su indexador (propiedad item), lo que te indica la notación 0(1) de la documentación de MSDN es que se tarda lo mismo en obtener el primer elemento de la colección que el último o que otro cualquiera. Es decir, que da igual que la lista tenga 10 o 10.000 elementos: el tiempo que tardas en obtener una referencia a cualquiera de ellos es el mismo. ¡Lo cual es estupendo!
Sin embargo si coges otro tipo de lista (por ejemplo un SortedList) y ves alguno de sus métodos para manipular elementos (por ejemplo RemoveAt) verás que la documentación te dice que es una operación 0(n). En este caso, aunque no lo indica, 'n' se refiere al número total de elementos de la lista. Esto quiere decir que el esfuerzo algorítmico -que luego se traduce en tiempo- para eliminar un elemento de la lista es una proporción lineal directamente proporcional al número de elementos de la lista. Es decir, que cuanto más al final de la lista esté el elemento más cuesta obtenerlo.
Si nos encontraramos algún algoritmo que indicara que es, por ejemplo, 0(n^3), querría decir que el esfuerzo es exponencial (al cubo) al número de elementos.
Esto es muy importante a la hora de seleccioanr uno u otro algoritmo según la cantidad de elementos que deba procesar. En el caso de las listas que nos ocupa gracias a estas indicaciones sabemos que si vamos a manejar una colección con muchos elementos será mejor utilizar un ArrayList que una SortedList, ya que cualquier acceso a los elementos para su procesamiento nos costará mucho más en el segundo caso que en el primero.
Espero que a otras personas les pueda resultar útil.
💪🏻 ¿Este post te ha ayudado?, ¿has aprendido algo nuevo?
Pues NO te pido que me invites a un café... Te pido algo más fácil y mucho mejor
