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

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

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

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

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

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

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

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

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

O (1) средний случай

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Поскольку вставка и поиск зависят только от результата хеш-функции, а не от размера хеш-таблицы или количества хранимых элементов, хеш-таблица имеет 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).

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

(из-за того, что столкновения ДЕЙСТВИТЕЛЬНО происходят, и при столкновении должно быть назначено другое местоположение)

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

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

На самом деле есть только один способ создать «идеальную хеш-таблицу» с O (1), и для этого требуется:

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

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

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

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

Суффиксное примечание Примечание. Я использую здесь O (1.5) и O (2). Их на самом деле не существует в большом количестве. Это просто то, что люди, которые не разбираются в больших вещах, считают логическим обоснованием.

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

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

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

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

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

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

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

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

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

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

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

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

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