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

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

Вопрос

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

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

Это было полезно?

Решение

MSDN перечисляет это:

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

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

SordedList (TKEY, TVALUE) использует меньше памяти, чем SortedDictionary (TKEY, TVALUE).

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

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

Другие советы

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

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

Идет поиск

Тип поиска/сбора Типы Сложность Комментарии
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.

Извлечение и вставка

Операция 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.

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

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

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

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

Получение (свойство элемента):

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

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

В общем, я не знаю (другой только что опубликованный ответ, возможно, дает вам именно то, что вам нужно) - но вы, конечно, можете отразить этот и другие методы, используя ILSpy (немного неудобно с кодом FSharp, правда), и это в конечном итоге дает эта функция как С#:

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);а что это такое на самом деле...ну, у меня слишком сильно болит голова, чтобы узнать :)

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

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

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

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

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

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

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

Лицензировано под: CC-BY-SA с атрибуция
Не связан с StackOverflow
scroll top