Я реализую очередь приоритетов и хочу перебирать список, чтобы вставить его в нужное место. В документации указано, что С# List<T>.Item Свойство - O (1):
List<T>.Item Свойство
например.
int retrivedValue = myIntList[5];
Как это возможно, так как add также является O (1)? Это нравится есть печенье и все еще есть. Обычные списки в моей голове имеют O (n) для доступа к элементу.
List<T> - это список в представлении, как говорит документация, он представляет типизированный список объектов, к которым можно получить доступ по индексу. Его элементы могут быть доступны по индексу напрямую и не требуют поэтапного обхода, эрго, сложность времени для доступа к элементу - это O (1). Он реализован внутри как динамический массив, который удваивает его размер, когда он заполняется (благодаря комментариям!).
Возможно, вы сбиваете с толку LinkedList<T>, который реализован как связанный список...
Стандартный тип Список поддерживается внутренним массивом с производительностью доступа O (1).
Список не использует связанный список.
List<T> поддерживается массивом.
Операция Add - это O (1), амортизированная по всем добавкам, что означает, что большинство операций - O (1), но некоторые из них O (N). Всякий раз, когда массив поддержки заполняется, он копируется в новый массив с двойным размером.
В качестве примера того, как это работает, предположим, что базовый массив начинается с 4 элементов. Первые 4 дополнения - O (1), но пятый должен будет скопировать существующие 4 элемента и добавить пятый, сделав его O (5). Добавление элементов 6, 7 и 8 равно O (1), а добавление элемента 9 будет O (9). Тогда элементы 10-16 также будут O (1).
К тому моменту, когда вы добавили 16 элементов в массив, вы выполнили операции O (28), в результате чего добавление N элементов займет почти O (2N) операций. Таким образом, добавление одного элемента в среднем равно O (2) = O (1).
У вас есть только O(n), если вам нужно выполнить итерацию по списку для извлечения элемента.
В этом примере вы обращаетесь к внутреннему массиву по индексу, поэтому не нужно итерации.
Несмотря на привлекательную сложность поиска по спискам на основе индекса элемента, мне интересно, может ли ваши потребности лучше обслуживаться с помощью SkipList, как описано в Обширное исследование структур данных Используя С# 2.0, ссылаясь на здесь, поскольку приоритет заказа не уникален.
Если массивная поддержка списка удваивается по размеру каждый раз, и n разрешается расти без ограничений, то количество раз, когда массив будет перераспределен, будет O (logn), и в каждой точке будет размер 2 ^ к; k = 1,2,3...
List<T>.Item versus List<T>.ContainsДоступ к элементам в списке - это O (1), если индекс известен, но для поддержания правильного порядка, основанного на приоритете, вам нужно либо использовать какой-то внешний механизм заказа, либо использовать .Contains, но этот второй метод не O (1).
Идея заключается в том, что SkipList является связанным списком со случайно вставленными указателями быстрой перемотки вперед для преодоления списка ссылок O (n) сложности поиска. Каждый node имеет следующие K указатели высоты K и K. Не вдаваясь в подробности, высоты распределяются, а функция next() выбирает соответствующий указатель таким образом, чтобы выполнить поиск O (logn). Однако node для удаления из очереди всегда будет находиться на одном конце связанного списка.
Память конечна и практически говоря, приоритетная очередь не будет расти вечно. Можно утверждать, что очередь растет до определенного размера, а затем никогда не перераспределяется. Но тогда это сокращается? Если список становится фрагментированным, операция сжатия становится еще более дорогостоящей, чем операция увеличения. Если поддерживается сокращение, тогда стоимость будет выплачиваться каждый раз, когда Списка становится слишком маленькой, а затем возрастающая стоимость будет выплачена, когда список станет слишком большим. Если он не поддерживается, то память, связанная с наибольшим размером очереди, будет выделена. Это приоритетная очередь, на самом деле кажется возможным, что очередь может увеличиваться по мере того, как в нее поступает работа, а затем сжимается (логически) до 0. Там могут быть редкие обстоятельства, что он будет расти очень большой, если потребительская сторона отстает.
Список внутренне использует массив, поэтому индексирование является прямой операцией. Кроме того, добавление в конце происходит быстро (если не требуется realoc). Вставка и удаление - это O (n), хотя все элементы массива необходимо перемещать. На практике это тоже не так плохо, потому что перемещение реализовано как одноблочное перемещение правой части массива.
Возможно, вам стоит взглянуть на this, чтобы понять и использовать наиболее подходящую структуру данных.
Ниже приведена сводная таблица:
