Что случилось с 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

Проблема в том, что люди действительно небрежны с терминологией. Здесь есть 3 важных, но различных класса:

O (1) наихудший случай

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

O (1) амортизированный наихудший случай

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

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

O (1) средний регистр

Этот самый хитрый. Существует два возможных определения среднего случая: одно для рандомизированных алгоритмов с фиксированными входами и одно для детерминированных алгоритмов с рандомизированными входами.

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

В другом случае нам нужно распределение вероятностей по входам. Например, если бы мы измерили алгоритм сортировки, одним из таких распределений вероятности было бы распределение, которое имеет все N! возможные перестановки ввода одинаково вероятны. Тогда среднее время выполнения - это среднее время работы по всем возможным входам, взвешенное по вероятности каждого входа.

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

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

См. Также Отказ в обслуживании по алгоритмической сложности . В этой статье авторы обсуждают, как они использовали некоторые слабые места в хеш-функциях по умолчанию, используемых двумя версиями Perl для генерации большого числа строк с коллизиями хешей. Вооружившись этим списком строк, они сгенерировали атаку типа «отказ в обслуживании» на некоторых веб-серверах, передав им эти строки, что привело к наихудшему поведению O(N) в хеш-таблицах, используемых веб-серверами.

Answer 2

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

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

Answer 3

O (1) означает постоянное время и (обычно) фиксированное пространство

Просто чтобы прояснить это два отдельных утверждения. Вы можете иметь O (1) во времени, но O (n) в пространстве или что-то еще.

Признается ли, что даже O (1) может быть нежелательно большим, хотя и почти постоянным?

O (1) может быть ОГРОМНО ОГРОМНЫМ, и все равно O (1). Часто пренебрегают тем, что если вы знаете, что у вас будет очень маленький набор данных, константа важнее, чем сложность, а для относительно небольших наборов данных это баланс двух. Алгоритм O (n!) Может превзойти O (1), если константы и размеры наборов данных имеют соответствующий масштаб.

Обозначение O () является мерой сложности, а не временем, которое займет алгоритм, или чистой мерой того, насколько «хорош» данный алгоритм для данной цели.

Answer 4

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

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

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

Answer 5

Hashtables - это структура данных, которая поддерживает O (1) поиск и вставку.

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

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

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

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

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

---

Давайте посмотрим на пример. Давайте используем хеш-таблицу для хранения следующих (key, value) пар:

• (Name, Bob)
• (Occupation, Student)
• (Location, Earth)

Мы реализуем хеш-таблицу с массивом из 100 элементов.

key будет использоваться для определения элемента массива для хранения пары (key, value). Для определения элемента будет использоваться hash_function:

• hash_function("Name") возврат 18
• hash_function("Occupation") возвращает 32
• hash_function("Location") возвращает 74 .

Из приведенного выше результата мы назначим пары (key, value) в элементы массива.

array[18] = ("Name", "Bob")
array[32] = ("Occupation", "Student")
array[74] = ("Location", "Earth")

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

Аналогично, при поиске элемента используется хеш-функция.

Если мы хотим найти ключ "Name", мы выполним hash_function("Name"), чтобы определить, в каком элементе массива находится нужное значение.

Кроме того, поиск не зависит ни от размера хеш-таблицы, ни от количества хранимых элементов, поэтому операция O (1).

Все хорошо. Попробуем добавить дополнительную запись ("Pet", "Dog"). Однако есть проблема, поскольку hash_function("Pet") возвращает 18 , что является тем же хешем для клавиши "Name".

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

array[29] = ("Pet", "Dog")

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

Эта проблема также возникает, когда мы пытаемся найти ключ "Pet", так как попытка найти элемент, содержащий ключ "Pet", выполнив hash_function("Pet"), всегда будет возвращать 18 изначально.

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

Answer 6

Может быть концептуальная ошибка относительно того, как вы понимаете обозначение Big-Oh. Это означает, что для заданного алгоритма и набора входных данных верхняя граница времени выполнения алгоритма зависит от значения O-функции, когда размер набора данных стремится к бесконечности.

Когда говорят, что алгоритм занимает O (n) времени, это означает, что время выполнения для худшего случая алгоритма линейно зависит от размера входного набора.

Когда алгоритм занимает O (1) времени, единственное, что он означает, это то, что, учитывая функцию T (f), которая вычисляет время выполнения функции f (n), существует натуральное положительное число k, такое что T (f)

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

Например, поиск экземпляра значения в связанном списке является операцией O (n). Но если я скажу, что список содержит не более 8 элементов, то O (n) становится O (8) становится O (1).

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

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

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

Answer 7

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

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

Имейте в виду, это предполагает, что вычисление хеша также равно O (1). Можно утверждать, что для строк длины K любой хеш минимально равен O (K). В действительности вы можете довольно легко связать K, скажем, K <1000. O (K) ~ = O (1) для K <1000. </p>

Answer 8

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

Answer 9

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

---

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

Answer 10

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

Время сбора мусора зависит от используемого алгоритма. Обычно современные сборщики мусора переключают режимы, когда память заполняется, чтобы держать эти расходы под контролем. Например, общий подход состоит в том, чтобы использовать сборщик копий в стиле Чейни при низком давлении памяти, потому что он платит стоимость, пропорциональную размеру живого набора, в обмен на использование большего пространства, и переключаться на сборщик меток и свипов, когда давление памяти становится больше, потому что, несмотря на то, что он платит стоимость, пропорциональную действующему набору для маркировки и всей куче или мертвому наметанию для подметания. К тому времени, когда вы добавляете маркировку карт и другие оптимизации и т. Д., Наихудшие затраты на практический сборщик мусора могут на самом деле быть немного хуже, учитывая дополнительный логарифмический фактор для некоторых моделей использования.

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

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

Более того, помимо проблемы копирования и сжатия, а также проблемы метки и развертки, детали реализации могут существенно повлиять на возникающие сложности:

1. Инкрементные сборщики мусора, которые отслеживают грязные биты и т. Д., Могут просто заставить эти большие повторные обходы исчезнуть.
2. Это зависит от того, работает ли ваш GC периодически на основе времени на часах или работает пропорционально количеству распределений.
3. Является ли алгоритм меток и стилей развертки одновременным или остановит мир
4. отмечает ли он новые выделения черным, если оставляет их белыми, пока не уронит их в черный контейнер.
5. Допускает ли ваш язык модификацию указателей, некоторые сборщики мусора могут работать за один проход.

Наконец, при обсуждении алгоритма мы обсуждаем соломенного человека. Асимптотика никогда не будет полностью включать все переменные вашей среды. Редко когда-либо вы реализуете каждую деталь структуры данных, как задумано. Вы заимствуете функцию здесь и там, вы отбрасываете хеш-таблицу, потому что вам нужен быстрый неупорядоченный доступ к ключу, вы используете объединение-поиск по непересекающимся наборам со сжатием пути и объединением по рангу, чтобы объединить области памяти там, потому что вы не можете позволить себе оплачивать расходы, пропорциональные размеру регионов, когда вы их объединяете или что у вас есть. Эти структуры являются мыслительными примитивами, и асимптотика помогает вам при планировании общих характеристик производительности для структуры «в целом», но также важно знать, что такое константы.

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