Что случилось с O(1)?
Я заметил очень странное использование O(1) при обсуждении алгоритмов, включающих хеширование и типы поиска, часто в контексте использования типа словаря, предоставляемого языковой системой, или использования словарей или типов хеш-массивов, используемых с использованием массива -индексная запись.
В основном, O(1) означает ограниченное постоянным временем и (обычно) фиксированным пространством. Некоторыми довольно фундаментальными операциями являются O(1), хотя использование промежуточных языков и специальных виртуальных машин имеет тенденцию искажать мысли, которые здесь возникают (например, как амортизировать сборщик мусора и другие динамические процессы по сравнению с действиями O(1)).
Но, игнорируя амортизацию задержек, сборку мусора и т. Д., Я до сих пор не понимаю, как можно сделать скачок к предположению, что некоторые методы, которые включают в себя какой-либо поиск, могут быть O(1), за исключением очень особых условий.
Хотя я уже заметил это раньше, в вопросе Пандинкуса только что появился пример: "Правильная" коллекция, используемая для получения элементов за O(1) времени в C# .NET?",
Как я там заметил, единственная известная мне коллекция, которая предоставляет доступ O(1) в качестве гарантированной границы, - это массив с фиксированной границей и целочисленным индексным значением. Предполагается, что массив реализован путем некоторого отображения в оперативную память, которая использует O(1) операции для определения местоположения ячейки, имеющей этот индекс.
Для коллекций, в которых используется какой-либо поиск для определения местоположения соответствующей ячейки для индекса другого типа (или для разреженного массива с целочисленным индексом), жизнь не так проста. В частности, если есть конфликты и возможна перегрузка, доступ не является точно O(1). И если коллекция является гибкой, необходимо распознать и амортизировать стоимость расширения базовой структуры (например, дерева или хеш-таблицы), для которой устраняется перегрузка (например, высокая частота столкновений или дисбаланс дерева).
Я никогда бы не подумал говорить об этих гибких и динамических структурах как о (1). Тем не менее, я вижу, что они предложены как O(1) решения без какой-либо идентификации условий, которые должны поддерживаться, чтобы фактически обеспечить доступ O(1) (а также иметь эту константу пренебрежимо малой).
ВОПРОС: Вся эта подготовка действительно для вопроса. Что такое случайность вокруг O(1) и почему это так слепо принято? Признается ли, что даже O(1) может быть нежелательно большим, хотя и почти постоянным? Или O(1) просто присвоение понятия сложности вычислений для неформального использования? Я озадачен
ОБНОВЛЕНИЕ: Ответы и комментарии указывают, где я был случайен относительно определения O(1) самостоятельно, и я исправил это. Я все еще ищу хорошие ответы, и в некоторых случаях некоторые потоки комментариев более интересны, чем их ответы.
13 ответов
Насколько я понимаю, 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), но это крайне маловероятно, учитывая два вышеизложенных предположения.
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")возвращает 18hash_function("Occupation")возвращает 32hash_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 для размера набора данных, то ее сложность будет 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-дерево, может быть лучшей альтернативой.
HashTable ищет O(1) по отношению к количеству элементов в таблице, потому что независимо от того, сколько элементов вы добавляете в список, стоимость хеширования одного элемента практически одинакова, и создание хеша скажет Вы адрес пункта.
Чтобы ответить, почему это актуально: ФП спросил о том, почему О (1), казалось, так небрежно разбрасывалось, когда, по его мнению, он не мог применяться во многих обстоятельствах. Этот ответ объясняет, что время O(1) действительно возможно в этих обстоятельствах.
В общем, я думаю, что люди используют их сравнительно, безотносительно к точности. Например, структуры данных на основе хеш-функции выглядят как O(1) (в среднем), если они хорошо спроектированы и у вас хороший хеш. Если все хешируется в одно ведро, то это O(n). Как правило, хотя используется хороший алгоритм и ключи разумно распределены, так что об этом удобно говорить как O (1) без всяких оговорок. Аналогично со списками, деревьями и т. Д. Мы имеем в виду определенные реализации, и о них просто удобнее говорить при обсуждении общностей без уточнений. Если, с другой стороны, мы обсуждаем конкретные реализации, то, возможно, стоит быть более точным.
Реализации хеш-таблиц на практике не "точно" используют O(1), если вы протестируете одну из них, вы обнаружите, что в среднем около 1,5 поисков, чтобы найти заданный ключ в большом наборе данных
(из-за того, что коллизии действительно имеют место, и при столкновении должно быть назначено другое местоположение)
Кроме того, на практике HashMaps поддерживаются массивами с начальным размером, который "увеличивается" до двойного размера, когда он достигает 70% заполненности в среднем, что дает относительно хорошее адресное пространство. После 70% полноты столкновения растут быстрее.
Теория большого О гласит, что если у вас есть алгоритм O(1) или даже алгоритм O(2), критическим фактором является степень зависимости между размером набора ввода и шагами для вставки / извлечения одного из них. O(2) все еще остается постоянным временем, поэтому мы просто приближаем его к O(1), потому что это означает более или менее одно и то же.
В действительности, есть только 1 способ иметь "идеальную хеш-таблицу" с O(1), и это требует:
- Глобальный идеальный генератор хэш-ключей
- Неограниченное адресное пространство.
(Исключительный случай: если вы можете заранее вычислить все перестановки разрешенных ключей для системы, а адресное пространство целевого резервного хранилища определено равным размеру, в котором оно может содержать все разрешенные ключи, тогда вы можете иметь идеальный хеш, но это "ограниченный домен" совершенство)
При фиксированном распределении памяти это маловероятно, потому что предполагается, что у вас есть какой-то волшебный способ упаковать бесконечное количество данных в фиксированное пространство без потери данных, и это невозможно с логистической точки зрения.,
Итак, ретроспективно, получая O(1.5), который все еще остается постоянным, в ограниченном объеме памяти даже с относительно наивным генератором ключей хеша, я считаю чертовски крутым.
Примечание к примечанию Я использую здесь O(1.5) и O(2). Это на самом деле не существует в биг-о. Это всего лишь то, что люди, которые не знают, что такое крупное, считают логическим обоснованием.
Если что-то занимает 1,5 шага, чтобы найти ключ, или 2 шага, чтобы найти этот ключ, или 1 шаг, чтобы найти этот ключ, но число шагов никогда не превышает 2, и если это займет 1 шаг или 2, является совершенно случайным, то это все еще Биг-О о (1). Это происходит потому, что независимо от того, сколько элементов вы добавляете к размеру набора данных, он все равно поддерживает <2 шага. Если для всех таблиц> 500 ключей требуется 2 шага, то можно предположить, что эти 2 шага на самом деле являются одностадийными с 2 частями... что по-прежнему равно O(1).
Если вы не можете сделать это предположение, тогда вы вообще не мыслите Big-O, потому что тогда вы должны использовать число, представляющее число конечных вычислительных шагов, необходимых для выполнения всего, и "одношаговый" для вас не имеет смысла. Просто подумайте, что нет прямой корреляции между Big-O и количеством задействованных циклов выполнения.
O(1) точно означает, что временная сложность алгоритма ограничена фиксированным значением. Это не означает, что он постоянный, только то, что он ограничен независимо от входных значений. Строго говоря, многие предположительно O(1) алгоритмы времени на самом деле не являются O(1) и просто идут настолько медленно, что они ограничены для всех практических входных значений.
Да, сборка мусора влияет на асимптотическую сложность алгоритмов, выполняемых на арене сбора мусора. Это не без затрат, но очень сложно анализировать без эмпирических методов, потому что затраты на взаимодействие не являются композиционными.
Время, затрачиваемое на сбор мусора, зависит от используемого алгоритма. Обычно современные сборщики мусора переключают режимы, когда память заполняется, чтобы держать эти расходы под контролем. Например, общий подход состоит в том, чтобы использовать сборщик копий в стиле Чейни при низком давлении памяти, поскольку он платит стоимость, пропорциональную размеру живого набора, в обмен на использование большего пространства, и переключаться на сборщик меток и свипов, когда давление памяти становится больше, потому что даже при том, что он платит стоимость, пропорциональную действующему набору для маркировки и всей куче или мертвому наметанию для подметания. К тому времени, когда вы добавляете маркировку карт и другие оптимизации и т. Д., Наихудшие затраты на практический сборщик мусора могут на самом деле быть немного хуже, учитывая дополнительный логарифмический фактор для некоторых моделей использования.
Таким образом, если вы выделяете большую хеш-таблицу, даже если вы обращаетесь к ней с помощью поиска O(1) за все время в течение ее времени жизни, если вы делаете это в среде сборки мусора, иногда сборщик мусора будет проходить через весь массив, потому что он размер O(n), и вы будете периодически оплачивать эту стоимость во время сбора.
Причина, по которой мы обычно исключаем сложный анализ алгоритмов, заключается в том, что сборщик мусора взаимодействует с вашим алгоритмом нетривиальными способами. Насколько это плохо, во многом зависит от того, что еще вы делаете в том же процессе, поэтому анализ не является композиционным.
Кроме того, помимо проблемы копирования и сжатия, а также проблемы с метками и развертками, детали реализации могут существенно повлиять на возникающие сложности:
- Инкрементные сборщики мусора, которые отслеживают грязные биты и т. Д., Могут практически исключить эти большие повторные обходы.
- Это зависит от того, работает ли ваш GC периодически на основе времени на часах или работает пропорционально количеству распределений.
- Является ли алгоритм метки и стиля свипирования параллельным или остановочным
- Отмечает ли он новые выделения черным, если оставляет их белыми, пока не уронит их в черный контейнер.
- Допускает ли ваш язык изменения указателей, может позволить некоторым сборщикам мусора работать за один проход.
Наконец, обсуждая алгоритм, мы обсуждаем соломенного человека. Асимптотика никогда не будет полностью включать все переменные вашей среды. Редко когда-либо вы реализуете каждую деталь структуры данных, как задумано. Вы заимствуете функцию здесь и там, вы отбрасываете хеш-таблицу, потому что вам нужен быстрый неупорядоченный доступ к ключу, вы используете объединение-поиск по непересекающимся наборам со сжатием пути и объединением по рангу, чтобы объединить области памяти там, потому что вы не можете позволить себе оплачивать расходы, пропорциональные размеру регионов, когда вы их объединяете или что у вас есть. Эти структуры являются мыслительными примитивами, и асимптотика помогает вам при планировании общих характеристик производительности для структуры "в целом", но также важно знать, что такое константы.
Вы можете реализовать эту хеш-таблицу с идеально асимптотическими характеристиками O(1), просто не используйте сборку мусора; отобразить его в память из файла и управлять им самостоятельно. Вам, вероятно, не понравится вовлеченные константы.
Я думаю, что когда многие люди используют термин "O(1)", они неявно имеют в виду "маленькую" константу, что бы ни означало "маленький" в их контексте.
Вы должны принять весь этот большой анализ с учетом контекста и здравого смысла. Это может быть чрезвычайно полезным инструментом или может быть смешным, в зависимости от того, как вы его используете.