Complejidad asintótica de las clases de colección.NET
collections big-o (6)
Esta página presenta notas breves sobre algunas ventajas y desventajas clave para la mayoría de las Colecciones .NET:
¿Hay recursos sobre la complejidad asintótica (big-O y el resto) de los métodos de las clases de colección .NET ( Dictionary<K,V> , List<T> etc ...)?
Sé que la documentación de la biblioteca C5 incluye cierta información al respecto ( example ), pero también me interesan las colecciones estándar de .NET ... (y la información de PowerCollections también estaría bien).
La documentación dice que está construido en un árbol binario y no menciona el seguimiento del elemento máximo. Si la documentación es correcta, eso significa que debería ser O (log n). Solía haber al menos un error en la documentación de las colecciones (refiriéndose a una estructura de datos respaldada por una matriz como un árbol de búsqueda binario), pero eso se ha corregido.
MSDN enumera estos:
-
Dictionary<,> -
List<> -
SortedList<,>(edición: 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 binario 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 ambas 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 extracción:
SortedList (TKey, TValue) usa 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 lugar de O (n) para SortedList (TKey, TValue).
Si la lista se rellena a la vez a partir de los datos ordenados, SortedList (TKey, TValue) es más rápido que SortedDictionary (TKey, TValue).
No hay tal cosa como "complejidad de clases de colección". Más bien, diferentes operaciones en estas colecciones tienen diferentes complejidades. Por ejemplo, agregando un elemento a un Dictionary<K, V> ...
... se acerca a una operación O (1) . Si se debe aumentar la capacidad para acomodar el nuevo elemento, este método se convierte en una operación O (n) , donde
nesCount.
Mientras se recupera un elemento de un Dictionary<K, V> ...
... se acerca a una operación O (1).
No lo sé en general (la otra respuesta que acabo de publicar tal vez te dé exactamente lo que estás buscando), pero puedes reflejar esto y otros métodos, por supuesto, usando ILSpy (un poco incómodo con el código FSharp, cierto) y esto finalmente da como resultado esta función como C #:
internal static a maximumElementAux<a>(SetTree<a> s, a n)
{
while (true)
{
SetTree<a> setTree = s;
if (setTree is SetTree<a>.SetOne)
{
break;
}
if (setTree == null)
{
return n;
}
SetTree<a>.SetNode setNode = (SetTree<a>.SetNode)s;
SetTree<a> arg_23_0 = setNode.item3;
n = setNode.item1;
s = arg_23_0;
}
return ((SetTree<a>.SetOne)s).item;
return n;
}
Bien, este no es exactamente el código ''correcto'' en términos de C #, pero la presencia del bucle while(true) implica que no puede ser O (1) al menos; en cuanto a lo que realmente es ... bueno, me duele demasiado la cabeza para descubrirlo :)
Esta página resume algunas de las complicaciones de tiempo para varios tipos de colección con Java, aunque deberían ser exactamente iguales para .NET.
Tomé las tablas de esa página y las modifiqué / expandí para el framework .NET. Vea también las páginas de MSDN para SortedDictionary<,> y SortedList , que detallan las complejidades de tiempo requeridas para varias operaciones.
buscando
Type of Search/Collection Types Complexity Comments Linear search Array/ArrayList/LinkedList O(N) Unsorted data. Binary search sorted Array/ArrayList/ O(log N) Requires sorted data. Search Hashtable/Dictionary<T> O(1) Uses hash function. Binary search SortedDictionary/SortedKey O(log N) Sorting is automated.
Recuperación e Inserción
Operation Array/ArrayList LinkedList SortedDictionary SortedList Access back O(1) O(1) O(log N) O(log N) Access front O(1) O(1) N.A. N.A. Access middle O(1) O(N) N.A. N.A. Insert at back O(1) O(1) O(log N) O(N) Insert at front O(N) O(1) N.A. N.A. Insert in middle O(N) O(1) N.A. N.A.
La eliminación debe tener la misma complejidad que la inserción para la colección asociada.
SortedList tiene algunas particularidades notables para la inserción y recuperación.
Inserción (Añadir método):
Este método es una operación O (n) para datos sin clasificar, 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 provoca un cambio de tamaño, la operación es O (n).
Recuperación (propiedad del artículo):
La recuperación del 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 la lista ordenada <(Of <(TKey, TValue>)>). Si la clave no está en la lista, establecer la propiedad es una operación O (n) para datos sin clasificar, o O (registro n) si el nuevo elemento se agrega al final de la lista. Si la inserción provoca un cambio de tamaño, la operación es O (n).
Tenga en cuenta que ArrayList es equivalente a la List<T> en términos de la complejidad de todas las operaciones.