Что случилось с O (1)?

Question

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

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

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

Несмотря на то, что я заметил это раньше, в вопросе Pandincus только что обнаружился пример: «Собственная коллекция», используемая для получения элементов за O (1) времени в C # .NET? ».

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

Для коллекций, в которых используется какой-либо поиск для определения местоположения подходящей ячейки для индекса другого типа (или для разреженного массива с целочисленным индексом), жизнь не так проста. В частности, если есть конфликты и возможна перегрузка, доступ не является точно O (1). И если коллекция является гибкой, необходимо распознать и амортизировать стоимость расширения базовой структуры (например, дерева или хеш-таблицы) для , что облегчает перегрузку (например, высокий уровень столкновений или дисбаланс дерева).

Я бы никогда не подумал говорить об этих гибких и динамических структурах как о (1). Тем не менее, я вижу, что они предложены как O (1) решения без какой-либо идентификации условий, которые должны поддерживаться для фактического обеспечения доступа O (1) (а также, что эта константа пренебрежимо мала).

ВОПРОС: Вся эта подготовка действительно для вопроса. Что такое случайность вокруг O (1) и почему она так слепо принята? Признается ли, что даже O (1) может быть нежелательно большим, хотя и почти постоянным? Или O (1) просто присвоение понятия сложности вычислений для неформального использования? Я озадачен.

ОБНОВЛЕНИЕ: Ответы и комментарии указывают на то, где я случайно не определился с О (1), и я это исправил. Я все еще ищу хорошие ответы, и некоторые потоки комментариев в некоторых случаях более интересны, чем их ответы.

Answer 1

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

Answer 2

Реализации хеш-таблиц на практике используются не "точно" O (1), если вы протестируете одну из них, вы обнаружите, что в среднем около 1,5 поисков, чтобы найти данный ключ в большом наборе данных

(из-за того, что происходят столкновения DO , а при столкновении должно быть назначено другое местоположение)

Кроме того, на практике HashMaps поддерживаются массивами с начальным размером, который «увеличивается» до двойного размера, когда он достигает 70% заполненности в среднем, что дает относительно хорошее адресное пространство. После 70% полноты столкновения растут быстрее.

Теория большого О гласит, что если у вас есть алгоритм O (1) или даже алгоритм O (2), критическим фактором является степень отношения между размером набора ввода и шагами для вставки / извлечения одного из них. , O (2) по-прежнему постоянное время, поэтому мы просто приближаем его к O (1), потому что это означает более или менее одно и то же.

В действительности, существует только 1 способ получить «идеальную хеш-таблицу» с O (1), и для этого требуется:

1. Глобальный идеальный генератор хэш-ключей
2. Неограниченное адресное пространство.

( Исключительный случай : если вы можете заранее вычислить все перестановки разрешенных ключей для системы, а адресное пространство целевого резервного хранилища определяется как размер, в котором он может содержать все ключи, которые являются разрешено, тогда вы можете иметь идеальный хеш, но это «ограниченное доменом» совершенство)

При фиксированном распределении памяти это вряд ли возможно, поскольку предполагается, что у вас есть какой-то волшебный способ упаковать бесконечное количество данных в фиксированное пространство без потери данных, и это логистически невозможно.

Итак, ретроспективно, получая O (1.5), который все еще остается постоянным временем, в ограниченном объеме памяти даже при относительно наивном генераторе ключей хеша, я считаю чертовски крутым.

Дополнительная заметка Примечание. Здесь я использую O (1.5) и O (2). Они на самом деле не существуют в биг-о. Это всего лишь то, что люди, которые не знают, что такое "большой", считают разумным.

Если что-то требует 1,5 шага, чтобы найти ключ, или 2 шага, чтобы найти этот ключ, или 1 шаг, чтобы найти этот ключ, но количество шагов никогда не превышает 2, и если это занимает 1 шаг или 2, является совершенно случайным, то это все еще Big-O O (1). Это связано с тем, что независимо от того, сколько элементов добавляется к размеру набора данных, он все равно сохраняет <2 шага. Если для всех таблиц> 500 ключей требуется 2 шага, то можно предположить, что эти 2 шага на самом деле являются одностадийными с 2 частями ... что по-прежнему равно O (1).

Если вы не можете сделать это предположение, тогда вы вообще не мыслите Big-O, потому что тогда вы должны использовать число, представляющее число конечных вычислительных шагов, необходимых для выполнения всего, а «одношаговый» не имеет смысла тебе. Просто подумайте, что существует прямая корреляция NO между Big-O и числом задействованных циклов выполнения.

Answer 3

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

Вы должны принять весь этот большой анализ с учетом контекста и здравого смысла. Это может быть чрезвычайно полезным инструментом или смешным, в зависимости от того, как вы его используете.