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.
Muchas gracias por la información. Es algo a tener siempre en cuenta!
Una con mu mala lesche:
¿Podría existir un algoritmo de eficiencia ln(O(x)), en donde x pudiera ser cualquier expresión típica del algoritmo, léase n, log n, etc?
Creo que hay dos respuestas, la que tiene truco y es trivial y la que no lo es…
En realidad, la notación asintótica se mide por dos cotas: O y Θ (omicron y theta del alfabeto griego, respectivamente), que simbolizan el «peor» y «mejor» caso de un algoritmo, en función de los elementos que pertenecen a la entrada del problema, pero no dependientes del tamaño. Es decir, para cada tamaño (n) de un problema existe un mejor y peor caso. También existen dos medidas diferentes de la complejidad de un problema, temporal (la más usual, y la empleada en el caso que comentas de acceso a colecciones) y espacial. Por supuesto, ambas medidas no tiene porque estar relacionadas, de hecho, una forma obvia de optimizar la complejidad temporal de un algoritmo, digamos, de ordenacion de un vector, seria maximizar su complejidad espacial, etc.
En cuanto a la pregunta de Rafael, la unidad de medida de la complejidad algoritmica es el «paso» (ya que toda magnitud debe ir asociada a una unidad de medida, por supuesto). Un paso se define como el conjunto de instrucciones de un algoritmo que pueden ser realizadas de forma correlativa, independientemente de la instancia concreta (input) de nuestro algoritmo. Por ejemplo, un bucle «for» que contenga 500 instrucciones y se ejecute N veces, tendra una complejidad de N, ya que aunque realmente este suponga 500*N instrucciones, la naturaleza asintotica del problema nos hace equiparar N = 500*N…
Desde ese punto de vista, únicamente las expresiones que sean determinantes del número de iteraciones en los bucles de nuestro algoritmo serán influyentes en el «orden» (log n, n, n^2… n^n, n!) de complejidad de nuestro algoritmo.
Creo que esta es la respuesta trivial, ¿cual es la otra? : )
Saludos,
M.
Esto me recuerda la complejidad ciclomática de McCabe y -todavía más antigua- las técnicas de métrica de código de Halstead, que creo que merecería la pena de una revisión a la vista de lo que ha cambiado el software de hoy.
Saludos
¡Pero qué frikis sois los tres! 😉
jaja, gracias!
Por cierto, el coste de acceso a un elemento «i» del vector es lineal ya que se computa como: GOTO Dir_Base_Vector + i*sizeof(tipo_elemento);
En lo unico que afecta el tamaño del vector es en la cota máxima del valor «i». : )
Saludos