Что случилось с O(1)?
https://stackoverflow.com/questions/332952
-
22-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianВопрос
Я заметил очень странное использование O(1) при обсуждении алгоритмов, включающих хеширование и типы поиска, часто в контексте использования типа словаря, предоставляемого языковой системой, или использования типов словаря или хеш-массива, используемых с использованием массива. -индексное обозначение.
По сути, O(1) означает ограниченность постоянным временем и (обычно) фиксированным пространством.Некоторые довольно фундаментальные операции относятся к O(1), хотя использование промежуточных языков и специальных виртуальных машин имеет тенденцию искажать мышление (например, как можно амортизировать сборщик мусора и другие динамические процессы по сравнению с тем, что в противном случае было бы действиями O(1)).
Но игнорируя амортизацию задержек, сборку мусора и т. д., я до сих пор не понимаю, как можно сделать шаг к предположению, что определенные методы, предполагающие какой-то вид поиска, могут быть O (1), за исключением очень особых условий.
Хотя я замечал это раньше, пример только что появился в Вопрос Пандинкуса: «Правильная коллекция, которую можно использовать для получения элементов за время O(1) в C# .NET?».
Как я уже отмечал там, единственная известная мне коллекция, которая обеспечивает доступ O(1) в качестве гарантированной привязки, — это массив с фиксированной привязкой и целочисленным индексным значением.Предполагается, что массив реализуется путем некоторого сопоставления с оперативной памятью, которое использует операции O (1) для поиска ячейки, имеющей этот индекс.
Для коллекций, которые включают в себя своего рода поиск для определения местоположения соответствующей ячейки для другого типа индекса (или для разреженного массива с целочисленным индексом), жизнь не так проста.В частности, если есть коллизии и возможна перегрузка, доступ не совсем равен O(1).А если коллекция гибкая, необходимо признать и амортизировать затраты на расширение базовой структуры (например, дерева или хеш-таблицы) для который облегчение заторов (например, высокая частота столкновений или дисбаланс деревьев).
Мне бы никогда не пришло в голову говорить об этих гибких и динамических структурах как об O(1).Тем не менее, я вижу, что они предлагаются как решения O(1) без какого-либо определения условий, которые должны соблюдаться, чтобы действительно обеспечить доступ O(1) (а также чтобы эта константа была пренебрежимо малой).
ВОПРОС:Вся эта подготовка на самом деле предназначена для вопроса.В чем необоснованность O(1) и почему ее принимают так слепо?Признается ли, что даже O(1) может быть нежелательно большим, хотя и почти постоянным?Или O(1) — это просто присвоение понятия вычислительной сложности для неформального использования?Я озадачен.
ОБНОВЛЯТЬ:Ответы и комментарии указывают на то, что я сам небрежно определял O(1), и я это исправил.Я все еще ищу хорошие ответы, и некоторые ветки комментариев в некоторых случаях более интересны, чем их ответы.
Решение
Насколько я понимаю, O (1) не обязательно является постоянным; скорее это не зависит от рассматриваемых переменных. Таким образом, можно сказать, что поиск хеша равен O (1) относительно количества элементов в хеше, но не относительно длины хешируемых данных или отношения элементов к сегментам в хэше.
Другим элементом путаницы является то, что большие обозначения O описывают ограничивающее поведение. Таким образом, функция f (N) для малых значений N может действительно показывать большие вариации, но вы все равно правильно сказали бы, что это O (1), если предел при приближении N к бесконечности постоянен по отношению к N.
Другие советы
Проблема в том, что люди действительно небрежно относятся к терминологии. Здесь есть 3 важных, но различных класса:
O (1) наихудший случай
Это просто - все операции в худшем случае и, следовательно, во всех случаях занимают не более постоянного времени. Доступ к элементу массива - O(1) наихудший случай.
O (1) амортизированный наихудший случай
Амортизация означает, что не каждая операция выполняется в худшем случае O(N), но для любой последовательности из N операций общая стоимость последовательности не равна <=> в худшем случае. Это означает, что даже если мы не можем связать стоимость какой-либо отдельной операции с константой, всегда будет достаточно & Quot; quick & Quot; операции, чтобы восполнить " медленный " такие операции, что время выполнения последовательности операций является линейным по количеству операций.
Например, стандартный динамический массив , который удваивает свою емкость при заполнении, требует <= > амортизированное время для вставки элемента в конце, даже если для некоторых вставок требуется <=> время - всегда достаточно <=> вставок, чтобы вставка N элементов всегда занимала <=> всего времени.
O (1) средний случай
Этот самый хитрый. Существует два возможных определения среднего случая: одно для рандомизированных алгоритмов с фиксированными входами и одно для детерминированных алгоритмов с рандомизированными входами.
Для рандомизированных алгоритмов с фиксированными входами мы можем вычислить среднее время выполнения для любого заданного входа, проанализировав алгоритм и определив распределение вероятностей всех возможных времен выполнения и взяв среднее по этому распределению (в зависимости от алгоритма, это может или не может быть возможно из-за проблемы остановки).
В другом случае нам нужно распределение вероятностей по входам. Например, если бы мы измерили алгоритм сортировки, одним из таких распределений вероятности было бы распределение, которое имеет все N! возможные перестановки ввода одинаково вероятны. Тогда среднее время выполнения - это среднее время работы по всем возможным входам, взвешенное по вероятности каждого входа.
Поскольку предметом этого вопроса являются хеш-таблицы, которые являются детерминированными, я сосредоточусь на втором определении среднего случая. Теперь мы не всегда можем определить распределение вероятностей входных данных, потому что мы можем хэшировать что угодно, и эти элементы могут поступать от пользователя, вводящего их в файловую систему или из нее. Поэтому, когда речь идет о хеш-таблицах, большинство людей просто предполагают, что входные данные ведут себя хорошо, а хеш-функция работает правильно, так что хеш-значение любого ввода по существу случайным образом распределено равномерно по всему диапазону возможных хеш-значений.
Потратьте немного времени и позвольте этой последней точке проявиться - средняя производительность <=> для хеш-таблиц зависит от предположения, что все хеш-значения распределены равномерно. Если это предположение нарушается (что обычно не происходит, но, безусловно, может и происходит), время выполнения больше не будет в среднем <=>.
См. также Отказ в обслуживании по алгоритмической сложности . В этой статье авторы обсуждают, как они использовали некоторые слабые места в хеш-функциях по умолчанию, используемых двумя версиями Perl для генерации большого числа строк с коллизиями хешей. Вооружившись этим списком строк, они сгенерировали атаку типа «отказ в обслуживании» на некоторых веб-серверах, передав им эти строки, что привело к наихудшему поведению <=> в хеш-таблицах, используемых веб-серверами.
O (1) означает постоянное время и (обычно) фиксированное пространство
Просто чтобы уточнить, это два отдельных утверждения. Вы можете иметь O (1) во времени, но O (n) в пространстве или что-то еще.
Признается ли, что даже O (1) может быть нежелательно большим, хотя и почти постоянным?
O (1) может быть ОГРОМНО ОГРОМНЫМ, и все равно это O (1). Часто пренебрегают тем, что если вы знаете, что у вас будет очень маленький набор данных, константа важнее, чем сложность, а для относительно небольших наборов данных это баланс двух. Алгоритм O (n!) Может превзойти O (1), если константы и размеры наборов данных имеют соответствующий масштаб.
ОбозначениеO () является мерой сложности, а не временем, которое займет алгоритм, или чистой мерой того, как " good " данный алгоритм предназначен для данной цели.
Я понимаю, что вы говорите, но я думаю, что есть несколько основных предположений, лежащих в основе утверждения о том, что поиск в хэш-таблице имеет сложность O (1).
- Хэш-функция разумно спроектирована так, чтобы избежать большого количества коллизий.
- Набор ключей распределен в значительной степени случайным образом или, по крайней мере, не предназначен специально для того, чтобы хеш-функция работала плохо.
Наихудшая сложность поиска в хеш-таблице равна O(n), но это крайне маловероятно, учитывая два приведенных выше предположения.
Хэш-таблицы — это структура данных, которая поддерживает поиск и вставку 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).
Хеширование Cuckoo поддерживает инвариант, так что в хэш-таблице нет цепочек. Вставка амортизируется O (1), поиск всегда O (1). Я никогда не видел реализацию этого, это то, что было недавно открыто, когда я учился в колледже. Для относительно статических наборов данных это должен быть очень хороший O (1), поскольку он вычисляет две хеш-функции, выполняет два поиска и сразу же знает ответ.
Имейте в виду, это предполагает, что вычисление хеша также равно O (1). Можно утверждать, что для строк длины K любой хеш минимально равен O (K). В действительности вы можете легко связать K, скажем, K & Lt; 1000. O (K) ~ = O (1) для K & Lt; 1000.
Может быть концептуальная ошибка в том, как вы понимаете нотацию Big-Oh. Это означает, что с учетом алгоритма и набора входных данных верхняя граница времени выполнения алгоритма зависит от значения O-функции, когда размер набора данных стремится к бесконечности.
Когда говорят, что алгоритм занимает O (n) времени, это означает, что время выполнения для наихудшего случая алгоритма линейно зависит от размера входного набора.
Когда алгоритм занимает O (1) времени, единственное, что он означает, это то, что, учитывая функцию T (f), которая вычисляет время выполнения функции f (n), существует натуральное положительное число k, такое что T (е) & k для любого входа n. По сути, это означает, что верхняя граница времени выполнения алгоритма не зависит от его размера и имеет фиксированный конечный предел.
Теперь, это никоим образом не означает, что предел мал, просто он не зависит от размера входного набора. Поэтому, если я искусственно определю границу 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-дерево, может быть лучшей альтернативой.
В целом, я думаю, что люди используют их сравнительно, безотносительно к точности. Например, структуры данных на основе хеша выглядят как O (1) (в среднем), если они хорошо спроектированы и у вас хороший хеш. Если все хешируется в одно ведро, то это O (n). Как правило, хотя используется хороший алгоритм и ключи разумно распределены, так что об этом удобно говорить как O (1) без всяких оговорок. Аналогично со списками, деревьями и т. Д. Мы имеем в виду определенные реализации, и о них просто удобнее говорить при обсуждении общностей без оговорок. Если, с другой стороны, мы обсуждаем конкретные реализации, то, возможно, стоит быть более точным.
HashTable ищет O (1) по отношению к количеству элементов в таблице, потому что независимо от того, сколько элементов вы добавляете в список, стоимость хеширования одного элемента почти одинакова, и создание хеш скажет вам адрес элемента.
<Ч>Чтобы ответить, почему это актуально: ФП спросил о том, почему О (1), кажется, так небрежно разбрасывается, когда, по его мнению, он не может применяться во многих обстоятельствах. Этот ответ объясняет, что O (1) время действительно возможно в этих обстоятельствах.
Реализации хеш-таблиц на практике не являются " в точности " O (1) используется, если вы протестируете один, вы обнаружите, что в среднем около 1,5 поисков, чтобы найти данный ключ в большом наборе данных
(из-за того, что DO происходят коллизии, а после коллизии должно быть назначено другое местоположение)
Кроме того, на практике HashMaps поддерживаются массивами с начальным размером, то есть " grow " удвоить размер, когда он достигает 70% заполненности в среднем, что дает относительно хорошее адресное пространство. После 70% полноты столкновения растут быстрее.
Теория большого O утверждает, что если у вас есть алгоритм O (1) или даже алгоритм O (2), критическим фактором является степень отношения между размером набора ввода и шагами для вставки / извлечения одного из них. , O (2) по-прежнему постоянное время, поэтому мы просто приближаем его к O (1), потому что это означает более или менее одно и то же.
На самом деле, есть только 1 способ получить " perfect hashtable " с O (1), и это требует:
<Ол>( Исключительный случай : если вы можете заранее вычислить все перестановки разрешенных ключей для системы, а адресное пространство целевого резервного хранилища определяется как размер, в котором могут храниться все ключи, которые разрешены, тогда вы можете иметь идеальный хеш, но это " домен ограничен " совершенство)
При фиксированном распределении памяти это вряд ли возможно, поскольку предполагается, что у вас есть какой-то волшебный способ упаковать бесконечное количество данных в фиксированное пространство без потери данных, и это логистически невозможно.
Итак, ретроспективно, получая O (1.5), который все еще остается постоянным, в конечном объеме памяти даже с относительно Na & # 239; у нас есть генератор хеш-ключей, я считаю довольно чертовски крутым.
Дополнительная заметка Примечание. Здесь я использую O (1.5) и O (2). Они на самом деле не существуют в биг-о. Это всего лишь то, что люди, которые не знают, что такое крупное, считают логическим обоснованием.
Если что-то требует 1,5 шага, чтобы найти ключ, или 2 шага, чтобы найти этот ключ, или 1 шаг, чтобы найти этот ключ, но количество шагов никогда не превышает 2, и если это занимает 1 шаг или 2, является совершенно случайным, то это все еще Big-O O (1). Это потому, что независимо от того, сколько элементов вы добавляете к размеру набора данных, он по-прежнему поддерживает & Lt; 2 шага. Если для всех таблиц & Gt; 500 клавиш это занимает 2 шага, тогда вы можете предположить, что эти 2 шага на самом деле являются одностадийными с 2 частями, что по-прежнему равно O (1).
Если вы не можете сделать это предположение, то вы вообще не мыслите Big-O, потому что тогда вы должны использовать число, представляющее число конечных вычислительных шагов, необходимых для выполнения всего, и " one- & шаг Quot; бессмысленно для вас. Просто подумайте, что НЕТ существует прямая корреляция между Big-O и числом задействованных циклов выполнения.
O (1) означает, что сложность алгоритма во времени ограничена фиксированным значением. Это не значит, что он постоянный, только то, что он ограничен независимо от входных значений. Строго говоря, многие предположительно O (1) алгоритмы времени на самом деле не являются O (1) и просто идут настолько медленно, что они ограничены для всех практических входных значений.
Да, сборка мусора влияет на асимптотическую сложность алгоритмов, выполняемых на арене сбора мусора. Это не без затрат, но очень сложно анализировать без эмпирических методов, потому что затраты на взаимодействие не являются композиционными.
Время, затраченное на сбор мусора, зависит от используемого алгоритма. Обычно современные сборщики мусора переключают режимы, когда память заполняется, чтобы держать эти расходы под контролем. Например, общий подход состоит в том, чтобы использовать сборщик копий в стиле Чейни при низком давлении памяти, потому что он платит стоимость, пропорциональную размеру живого набора, в обмен на использование большего пространства, и переключаться на сборщик меток и свипов, когда давление памяти становится больше, потому что, несмотря на то, что он платит стоимость, пропорциональную действующему набору для маркировки и всей куче или мертвому наметанию для подметания. К тому времени, когда вы добавляете маркировку карты и другие оптимизации и т. Д., Наихудшие затраты на практический сборщик мусора могут на самом деле быть немного хуже, учитывая дополнительный логарифмический фактор для некоторых моделей использования.
Таким образом, если вы выделяете большую хеш-таблицу, даже если вы обращаетесь к ней с помощью поиска O (1) за все время в течение ее времени жизни, если вы делаете это в среде сборки мусора, иногда сборщик мусора будет проходить через весь массив потому что это размер O (n), и вы будете периодически оплачивать эту стоимость во время сбора.
Причина, по которой мы обычно исключаем сложный анализ алгоритмов, заключается в том, что сборщик мусора взаимодействует с вашим алгоритмом нетривиальными способами. Насколько это плохо, во многом зависит от того, что еще вы делаете в том же процессе, поэтому анализ не является композиционным.
Кроме того, помимо проблемы копирования и сжатия, а также проблемы маркировки и очистки детали реализации могут существенно повлиять на возникающие сложности:
<Ол>Наконец, при обсуждении алгоритма мы обсуждаем соломенного человека. Асимптотика никогда не будет полностью включать все переменные вашей среды. Редко когда-либо вы реализуете каждую деталь структуры данных, как задумано. Вы заимствуете функцию здесь и там, вы отбрасываете хеш-таблицу, потому что вам нужен быстрый неупорядоченный доступ к ключу, вы используете объединение-поиск по непересекающимся наборам со сжатием пути и объединением по рангу, чтобы объединить области памяти там, потому что вы не можете позволить себе оплачивать расходы, пропорциональные размеру регионов, когда вы их объединяете или что у вас есть. Эти структуры являются мыслительными примитивами, и асимптотика помогает вам при планировании общих характеристик производительности для структуры «в целом», но также важно знать, что такое константы.
Вы можете реализовать эту хеш-таблицу с идеально асимптотическими характеристиками O (1), просто не используйте сборку мусора; отобразить его в память из файла и управлять им самостоятельно. Вам, вероятно, не понравятся задействованные константы.
Я думаю, что когда многие люди используют термин " O (1) " они неявно имеют в виду " small " константа, что угодно " small " значит в их контексте.
Вы должны принять весь этот анализ Big-O с учетом контекста и здравого смысла. Это может быть чрезвычайно полезным инструментом или смешным, в зависимости от того, как вы его используете.
