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

StackOverflow https://stackoverflow.com/questions/851949

Pregunta

¿Hay algún recurso 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 información al respecto (ejemplo), pero también estoy interesado en las colecciones .NET estándar...(y la información de PowerCollections también sería buena).

¿Fue útil?

Solución

Listas de MSDN siguientes:

etc. Por ejemplo:

  

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

     

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

     

SortedDictionary (TKey, TValue) tiene   la inserción y remoción más rápida   operaciones de datos no ordenados, O (log n)   en contraposición a O (n) para   SortedList (TKey, TValue).

     

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

Otros consejos

Esta página resume algunos de los comlplexities tiempo para diversas tipos de colección con Java, aunque deben ser exactamente el mismo para .NET.

Me he tomado las tablas de esa página y alterado / ellas ampliado para la plataforma .NET. Consulta las páginas de MSDN para SortedDictionary y SortedList , que detalle las complejidades tiempo requerido para diversas operaciones.

Buscar 

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 y de 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.

Supresión debe tener la misma complejidad que la inserción para la recogida asociada.

SortedList tiene algunas peculiaridades 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. Está   un O (log n) la operación si el nuevo   elemento se añade al final de la   lista. Si la inserción provoca un cambio de tamaño,   la operación es O (n).

Recuperación (propiedad Item):

  

Recuperar el valor de esta propiedad   es una operación O (log n), donde n es   Contar. Al establecer la propiedad es una   O (log n) la operación si la clave es   ya en la SortedList <(Of <(TKey,   TValue>)>). Si la clave no está en el   lista, el establecimiento de la propiedad es un O (n)   operación para los datos sin clasificar, o O (log   n) si se añade el nuevo elemento en la   final de la lista. Si la inserción provoca una   cambiar el tamaño, la operación es O (n).

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

No sé en general (la otra respuesta acaba de publicar tal vez le da exactamente lo que está buscando) - pero se puede reflejar esto y otros métodos, por supuesto, utilizando ILSpy (un poco incómodo con el código de FSharp, true) y esto finalmente da 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;
}

Bueno por lo que esto no es exactamente código 'adecuado' en términos de C # - pero la presencia de la while(true) bucle implica que no puede ser O (1) al menos; En cuanto a lo que realmente es ... bueno, mi cabeza duele demasiado para averiguar:)

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

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

No hay tal cosa como la "complejidad de las clases de colección". Por el contrario, las diferentes operaciones en estas colecciones tienen diferentes complejidades. Por ejemplo, la adición de un elemento a un Dictionary<K, V> ...

  

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

Mientras que la recuperación de un elemento de una <=> ...

  

... se acerca a un (1) Operación S.

La documentación dice que está construido sobre 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 se ha corregido.

Licenciado bajo: CC-BY-SA con atribución
No afiliado a StackOverflow
scroll top