Complexidade assintótica de classs de coleção .NET

Existem resources sobre a complexidade assintótica (big-O e o resto) de methods de classs de coleção .NET ( Dictionary , List etc …)?

Eu sei que a documentação da biblioteca C5 inclui algumas informações sobre ela ( exemplo ), mas também estou interessado em collections .NET padrão … (e as informações da PowerCollections também seriam boas).

MSDN lista estes:

  • Dictionary<,>
  • List<>
  • SortedList<,> (editar: link errado; aqui está a versão genérica )
  • SortedDictionary<,>

etc. Por exemplo:

A class genérica SortedList (TKey, TValue) é uma tree de pesquisa binária com recuperação O (log n), em que n é o número de elementos no dictionary. Neste, é semelhante à class genérica SortedDictionary (TKey, TValue). As duas classs têm modelos de objects semelhantes e ambas possuem recuperação O (log n). Onde as duas classs diferem é no uso de memory e velocidade de inserção e remoção:

SortedList (TKey, TValue) usa menos memory que SortedDictionary (TKey, TValue).

SortedDictionary (TKey, TValue) tem operações de inserção e remoção mais rápidas para dados não classificados, O (log n) em oposição a O (n) para SortedList (TKey, TValue).

Se a lista for preenchida de uma só vez a partir de dados classificados, SortedList (TKey, TValue) será mais rápido que SortedDictionary (TKey, TValue).

Esta página resume algumas das complexidades de tempo para vários tipos de coleção com Java, embora elas devam ser exatamente as mesmas para o .NET.

Eu peguei as tabelas dessa página e as alterei / expandi para o .NET framework. Veja também as páginas MSDN para SortedDictionary e SortedList , que detalham as complexidades de tempo necessárias para várias operações.


Procurando

 Tipo de pesquisa / tipos de coleção Comentários da complexidade
 Pesquisa linear Array / ArrayList / LinkedList O (N) Dados não sorteados.
 Pesquisa binária classificada Array / ArrayList / O (log N) Requer dados classificados.
 Busca Hashtable / Dictionary  O (1) Usa a function hash.
 Pesquisa binária SortedDictionary / SortedKey O (log N) A sorting é automática.

Recuperação e Inserção

 Operação Array / ArrayList LinkedList SortedDictionary SortedList
 Acesso de volta O (1) O (1) O (log N) O (log N)
 Acesso frente O (1) O (1) NANA
 Acesso médio O (1) O (N) NANA
 Insira na parte traseira O (1) O (1) O (log N) O (N)
 Inserir na frente O (N) O (1) NANA
 Inserir no meio O (N) O (1) NANA

A exclusão deve ter a mesma complexidade da inserção para a coleção associada.

SortedList tem algumas peculiaridades notáveis ​​para inserção e recuperação.

Inserção (método Add):

Este método é uma operação O (n) para dados não classificados, onde n é Count. É uma operação O (log n) se o novo elemento for adicionado no final da lista. Se a inserção causar um redimensionamento, a operação será O (n).

Recuperação (propriedade do item):

A recuperação do valor dessa propriedade é uma operação O (log n), em que n é Count. Definir a propriedade é uma operação O (log n) se a chave já estiver na SortedList <(Of <(TKey, TValue>)>). Se a chave não estiver na lista, a configuração da propriedade é uma operação O (n) para dados não classificados ou O (log n) se o novo elemento for adicionado no final da lista. Se a inserção causar um redimensionamento, a operação será O (n).

Observe que ArrayList é equivalente a List em termos da complexidade de todas as operações.


Eu não sei em geral (a outra resposta postada talvez lhe dê exatamente o que você está procurando) – mas você pode refletir este e outros methods usando ILSpy (um pouco estranho com o código FSharp, true) e isso eventualmente gera esta function 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; } 

Ok, então este não é exatamente o código ‘correto’ em termos C # – mas a presença do laço while(true) implica que ele não pode ser O (1) pelo menos; quanto ao que realmente é … bem, minha cabeça dói demais para descobrir 🙂

Esta página apresenta notas breves sobre alguns prós e contras importantes para a maioria das Coleções do .NET:

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

Não existe tal coisa como “complexidade de classs de coleção”. Em vez disso, operações diferentes nessas collections têm complexidades diferentes. Por exemplo, adicionar um elemento a um Dictionary

… se aproxima de uma operação O (1) . Se a capacidade precisar ser aumentada para acomodar o novo elemento, esse método se tornará uma operação O (n) , em que n é Count .

Considerando que recuperar um elemento de um Dictionary

… se aproxima de uma operação O (1).

A documentação diz que é construída em uma tree binária e não menciona o rastreamento do elemento máximo. Se a documentação estiver correta, isso significa que deve ser O (log n). Costumava haver pelo menos um erro na documentação das collections (referindo-se a uma estrutura de dados com suporte a matriz como uma tree de pesquisa binária), mas isso foi corrigido.