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