Complejidad asintótica de las clases de colección .NET

¿Hay algún recurso sobre la complejidad asintótica (big-O y el rest) de los métodos de las clases de colección .NET ( Dictionary , List etc …)?

Sé que la documentación de la biblioteca C5 incluye cierta información al respecto ( ejemplo ), pero también me interesan las colecciones .NET estándar … (y la información de PowerCollections también sería agradable).

MSDN enumera estos:

  • Dictionary<,>
  • List<>
  • SortedList<,> (editar: enlace incorrecto; aquí está la versión genérica )
  • SortedDictionary<,>

etc. Por ejemplo:

La clase genérica SortedList (TKey, TValue) es un árbol de búsqueda binaria con recuperación O (log n), donde n es el número de elementos en el diccionario. En esto, es similar a la clase genérica SortedDictionary (TKey, TValue). Las dos clases tienen modelos de objetos similares, y ambos tienen recuperación O (log n). Donde las dos clases difieren es en el uso de la memoria y la velocidad de inserción y eliminación:

SortedList (TKey, TValue) utiliza menos memoria que SortedDictionary (TKey, TValue).

SortedDictionary (TKey, TValue) tiene operaciones de inserción y eliminación más rápidas para datos sin clasificar, O (log n) en oposición a O (n) para SortedList (TKey, TValue).

Si la lista se completa de una sola vez a partir de datos ordenados, SortedList (TKey, TValue) es más rápido que SortedDictionary (TKey, TValue).

Esta página resume algunas de las complejidades del tiempo para varios tipos de colecciones con Java, aunque deberían ser exactamente las mismas para .NET.

Tomé las tablas de esa página y las modifiqué / expandí para .NET Framework. Consulte también las páginas de MSDN para SortedDictionary y SortedList , que detallan las complejidades de tiempo requeridas para varias operaciones.


buscando

 Tipo de búsqueda / Colección Complejidad Complejidad Comentarios
 Búsqueda lineal Array / ArrayList / LinkedList O (N) Datos no ordenados.
 Búsqueda binaria ordenada Array / ArrayList / O (log N) Requiere datos ordenados.
 Buscar Hashtable / Dictionary  O (1) Utiliza la función hash.
 Búsqueda binaria SortedDictionary / SortedKey O (log N) La ordenación está automatizada.

Recuperación e inserción

 Operation Array / ArrayList LinkedList SortedDictionary SortedList
 Acceso atrás O (1) O (1) O (log N) O (log N)
 Acceso frontal O (1) O (1) NANA
 Acceso medio O (1) O (N) NANA
 Insertar en la parte posterior O (1) O (1) O (log N) O (N)
 Insertar al frente O (N) O (1) NANA
 Insertar en medio O (N) O (1) NANA

La eliminación debe tener la misma complejidad que la inserción para la colección asociada.

SortedList tiene algunas peculiaridades notables para la inserción y la recuperación.

Inserción (método de Agregar):

Este método es una operación O (n) para datos no ordenados, donde n es Count. Es una operación O (log n) si el nuevo elemento se agrega al final de la lista. Si la inserción causa un cambio de tamaño, la operación es O (n).

Recuperación (propiedad del artículo):

Recuperar el valor de esta propiedad es una operación O (log n), donde n es Count. La configuración de la propiedad es una operación O (log n) si la clave ya está en SortedList <(Of <(TKey, TValue>)>). Si la clave no está en la lista, establecer la propiedad es una operación O (n) para datos no ordenados, o O (log n) si el nuevo elemento se agrega al final de la lista. Si la inserción causa un cambio de tamaño, la operación es O (n).

Tenga en cuenta que ArrayList es equivalente a List en términos de la complejidad de todas las operaciones.


No lo sé en general (la otra respuesta que acabo de publicar tal vez te dé exactamente lo que buscas), pero puedes reflejar este y otros métodos, por supuesto, usando ILSpy (un poco incómodo con el código FSharp, cierto) y esto finalmente cede esta función como C #:

 internal static a maximumElementAux(SetTree s, an) { while (true) { SetTree setTree = s; if (setTree is SetTree.SetOne) { break; } if (setTree == null) { return n; } SetTree.SetNode setNode = (SetTree.SetNode)s; SetTree arg_23_0 = setNode.item3; n = setNode.item1; s = arg_23_0; } return ((SetTree.SetOne)s).item; return n; } 

Bueno, este no es exactamente el código “correcto” en términos de C #, pero la presencia del ciclo while(true) implica que no puede ser al menos O (1); en cuanto a lo que realmente es … bueno, me duele la cabeza demasiado para saberlo 🙂

Esta página presenta notas breves sobre algunos pros y contras clave para la mayoría de las Colecciones .NET:

http://geekswithblogs.net/BlackRabbitCoder/archive/2011/06/16/c.net-fundamentals-choosing-the-right-collection-class.aspx

No existe la “complejidad de las clases de cobranza”. Por el contrario, las diferentes operaciones en estas colecciones tienen diferentes complejidades. Por ejemplo, agregar un elemento a un Dictionary

… se acerca a una operación O (1) . Si la capacidad se debe boost para acomodar el nuevo elemento, este método se convierte en una operación O (n) , donde n es Count .

Mientras que recuperamos un elemento de un Dictionary

… se acerca a una operación O (1).

La documentación dice que está construida sobre un árbol binario y no menciona el seguimiento del elemento máximo. Si la documentación es correcta, eso significa que debe ser O (log n). Solía ​​haber al menos un error en la documentación de las colecciones (en referencia a una estructura de datos respaldada por una matriz como un árbol de búsqueda binaria), pero eso se ha corregido.