Что произошло с O (1)?

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

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

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

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

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

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

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

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

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

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

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

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

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

(из-за к тому, что коллизии ДЕЛАЮТ , происходят, и после столкновения, различное местоположение должно быть присвоено)

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

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

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

1. А Глобальный Идеальный Генератор Ключа Хеша
2. Неограниченное адресуемое пространство.

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

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

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

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

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

, Если Вы не можете сделать это предположение, тогда Ваш то, что я был Большими-O взглядами вообще, потому что тогда необходимо использовать число, которое представляет количество конечных вычислительных шагов, требуемых сделать все и "один шаг", бессмысленно Вам. Просто имейте в голове, что существует НИКАКОЙ прямая корреляция между Большим-O и количеством включенных циклов выполнения.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Все хорошо. Давайте попытаемся добавить дополнительную запись [1 116]. Однако существует проблема, как [1 117] возвраты 18 , который является тем же хешем для "Name" ключ.

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

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

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

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

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

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

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

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

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

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

Проблема состоит в том, что люди действительно неаккуратны с терминологией. Здесь существует 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-функции, когда размер набора данных склоняется к бесконечности.

, Когда каждый говорит, что алгоритм берет 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 (журнал (n)) структура как AVL или B-дерево может быть превосходящей альтернативой.