Как мне получить элемент с наименьшим ключом в коллекции за O (1) или O (log n) время?

ProgramBox

Как мне получить элемент с наименьшим ключом в коллекции за O (1) или O (log n) время?

Post author:admin
Запись опубликована:28 апреля, 2023
Post category:Вопросы по программированию

#c# #.net #data-structures #big-o

#c# #.net #структуры данных #big-o

Вопрос:

Я знаю, что могу использовать Dictionary и извлекать произвольный элемент за O (1) время.

Я знаю, что могу получить следующий по величине (или наименьший) элемент в SortedDictionary за O (1) время. Но что, если бы я захотел удалить первое значение (на основе TKey ‘s IComparable ) в SortedDictionary ?

Могу ли я использовать .First() метод для извлечения наименьшего ключа? И в чем его сложность? Будет ли он выполняться за O (1), O (log n) или O (n) время?

Является SortedDictionary правильной структурой данных для этого?

Примечание: Вариант использования — это что-то вроде очереди приоритетов для бедных людей или упорядоченной очереди. Для этого не допускается использование открытого исходного кода (должен быть написан с нуля или уже в .NET 3.5 framework).

1. Роберт, в отсортированном словаре обычно требуется log2n, чтобы получить минимальный элемент, это не O (1). Кучи предлагают O (1) доступ к min (или max).

2. @best: Я не говорил, что min это O (1). Прочитайте вопрос еще раз: следующий элемент — O (1)

3. следующий по старшинству / низшему значению (в подмножестве), предшественник / преемник элемента также не являются O (1).

Ответ №1:

SortedList и SortedDictionary реализованы внутренне как бинарные деревья поиска и в идеале могут обеспечить вам производительность O (log n) в течение минуты (требуется пройтись по дереву, но не перечислять весь список). Однако использование LINQ для выполнения этого минимального значения, вероятно, приведет к перечислению всего списка.

Я бы рассмотрел список пропусков как лучшую альтернативную структуру данных.

1. Делает . У NET есть собственная реализация списка пропусков?

2. @Robert, к сожалению, нет — вам пришлось бы реализовать это самостоятельно (или использовать реализацию с открытым исходным кодом, но вы сказали, что это не вариант.) Однако базовый алгоритм не особенно сложен в реализации, а статья MSDN, на которую я ссылался, знакомит вас с ядром.

3. LINQ будет использовать GetEnumerator() для извлечения первого элемента (O (log n)), а не Min() .

4. @Marcelo, будь . First() (он же: GetEnumerator) вернет минимальное значение, зависящее от порядка сортировки SortedList<T>. Таким образом, он может удовлетворять или не удовлетворять требованию. Вопрос OP был немного нечетким.

5. Min требует перечисления всего списка, потому что он не может знать, что он отсортирован. У LINQ действительно есть . Метод First().

Ответ №2:

Сортированный справочник.Указано, что для GetEnumerator требуется O (log n) время, поэтому First() должен последовать его примеру.

1. @hempp: Разве это не то, что SortedDictionary делает?

2. @Robert: Он сортирует с помощью IComparable — то, как реализован IComparable, определяет порядок сортировки. Поскольку в данном случае структура данных принадлежит вам, это было бы прекрасно.

Ответ №3:

Если у вас есть SortedDictionary or SortedList , вы можете использовать .First() (или dict.Keys[0] для SortedList ) В противном случае, вы могли бы сделать:

 dict[dict.Keys.Min()]

на что потребуется общее время O (N) (поскольку Min () должна перебирать всю коллекцию)

.First() вероятно, у меня будет O (1) время для SortedList и O (log n) для SortedDictionary.

Вставка и удаление будут занимать O (log N) времени для SortedDictionary и могут составлять до O (N) для SortedList. Обратите внимание, что если вы используете словарь для резервного копирования вашей «очереди приоритетов», у вас не может быть двух элементов с одинаковым приоритетом.

Я не думаю, что у какого-либо класса есть специальная реализация для Last, поэтому, если вам нужен ключ с наибольшим значением, вам, вероятно, следует использовать SortedList, поскольку вы можете сделать dict.Keys[dict.Count-1] . Если вам нужен только самый высокий (а не самый низкий), вы могли бы использовать средство сравнения, чтобы отсортировать его в этом порядке и использовать первым.

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

2. Тогда вам следует использовать SortedDictionary (или SortedList ). Просто учитывайте также затраты на вставку и удаление.

Ответ №4:

Поскольку вы упомянули только получение значений, а не их установку, вы могли бы использовать простой список, отсортировать его заранее, а затем получить доступ к любому значению по порядку в O (1).

Ответ №5:

Почему бы вам не сохранить отдельный отсортированный список ключей, чтобы вы всегда могли получить элемент с наименьшим ключом, просто выполнив dict[keyList[0]] .

Ответ №6:

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