Асимптотическая сложность классов коллекции .NET - PullRequest
Новая
       27

Асимптотическая сложность классов коллекции .NET

27 голосов
/ 12 мая 2009

Есть ли какие-либо ресурсы об асимптотической сложности (big-O и остальные) методов классов коллекций .NET (Dictionary<K,V>, List<T> и т.д ...)?

Я знаю, что документация библиотеки C5 включает в себя некоторую информацию об этом ( пример ), но я также заинтересован в стандартных коллекциях .NET ... (и информация PowerCollections также была бы хороша).

Ответы [ 6 ]

26 голосов
/ 12 мая 2009

MSDN Список этих:

и т.д.. Например:

Универсальный SortedList (TKey, TValue) класс представляет собой двоичное дерево поиска с O (log n) поиск, где n - это количество элементов в словаре. В этом он похож на SortedDictionary (TKey, TValue) универсальный учебный класс. Два класса имеют похожие объектные модели, и обе имеют O (log n) поиск. Где два класса отличаются использованием памяти и скоростью вставка и удаление:

SortedList (TKey, TValue) использует меньше памяти, чем SortedDictionary (TKey, TValue).

SortedDictionary (TKey, TValue) имеет более быстрая вставка и удаление операции для несортированных данных, O (log n) в отличие от O (n) для SortedList (TKey, TValue).

Если список заполнен сразу из отсортированных данных, SortedList (TKey, TValue) быстрее чем SortedDictionary (TKey, TValue).

24 голосов
/ 12 мая 2009

На этой странице обобщены некоторые временные сложности для различных типов коллекций с Java, хотя они должны быть точно такими же для .NET.

Я взял таблицы с этой страницы и изменил / расширил их для .NET Framework. См. Также страницы MSDN для SortedDictionary и SortedList , которые подробно описывают временные сложности, необходимые для различных операций.

Поиск 

<b>Type of Search/Collection Types           Complexity  Comments</b>
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.

Поиск и вставка 

<b>Operation         Array/ArrayList  LinkedList  SortedDictionary  SortedList</b>
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.

Удаление должно иметь ту же сложность, что и вставка для связанной коллекции.

SortedList имеет несколько примечательных особенностей для вставки и извлечения.

Вставка (Добавить метод):

Этот метод является операцией O (n) для несортированные данные, где n - граф. это O (log n) операция, если новый элемент добавляется в конце список. Если вставка вызывает изменение размера, операция O (n).

Получение (свойство объекта):

Получение значения этого свойства является операцией O (log n), где n Граф. Установка свойства является O (log n) операция, если ключ уже в SortedList <(Of <(TKey, TValue>)>). Если ключ не находится в список, устанавливающий свойство O (n) операция для несортированных данных, или O (журнал n) если новый элемент добавлен в конец списка. Если вставка вызывает изменить размер, операция O (n).

Обратите внимание, что ArrayList эквивалентно List<T> с точки зрения сложности всех операций.

2 голосов
/ 18 августа 2015

На этой странице представлены краткие заметки о некоторых преимуществах и недостатках большинства коллекций .NET:

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

2 голосов
/ 15 июня 2011

В общем, я не знаю (другой только что опубликованный ответ, возможно, даст вам именно то, что вам нужно), но вы можете отразить этот и другие методы, конечно, используя ILSpy (немного неудобно с кодом FSharp, правда) и это в конечном итоге дает эту функцию как 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;
}

Хорошо, так что это не совсем «правильный» код в терминах C #, но наличие цикла while(true) подразумевает, что он не может быть, по крайней мере, O (1); Что касается того, что это на самом деле ... ну, моя голова слишком болит, чтобы узнать :)

0 голосов
/ 29 июня 2011

Документация говорит, что она построена на двоичном дереве, и не упоминает отслеживание максимального элемента. Если документация верна, это означает, что это должно быть O (log n). Раньше в документации по коллекциям была хотя бы одна ошибка (ссылающаяся на структуру данных на основе массива как двоичное дерево поиска), но она была исправлена.

0 голосов
/ 12 мая 2009

Нет такой вещи, как "сложность классов коллекции". Скорее разные операции над этими коллекциями имеют разные сложности. Например, добавление элемента в Dictionary<K, V> ...

... приближается к операции O (1) . Если емкость должна быть увеличена для размещения нового элемента, этот метод становится операцией O (n) , где n равно Count.

Принимая во внимание извлечение элемента из Dictionary<K, V> ...

... приближается к операции O (1).

...