O (log N) == O (1) - Почему бы и нет?

Ответ 1

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

Использование функции Аккермана?

Процитировать меня от комментариев по другому ответу:

[Big-Oh] 'Анализ' имеет значение только для факторов которые не менее O (N). Для любого меньший коэффициент, большой-ой анализ бесполезно, и вы должны измерить.

и

"С O (logN) ваш размер ввода материи". В этом весь смысл вопрос. Конечно, это важно... в теории. Вопрос, который задает ОП действительно ли это имеет значение на практике? я утверждают, что ответа нет, там не является и никогда не будет, набором данных для которых logN будет расти так быстро, как всегда избивать постоянное время алгоритм. Даже для самых больших практический набор данных, который можно представить в жизни наших внуков, logN алгоритм имеет справедливые шансы на избиение алгоритм с постоянным временем - вы должны всегда измерять.

ИЗМЕНИТЬ

Хороший разговор:

http://www.infoq.com/presentations/Value-Identity-State-Rich-Hickey

примерно на полпути, Рич обсуждает Clojure хеш-попытки, которые явно O (logN), но база логарифма велика, и поэтому глубина trie не более 6, даже если она содержит 4 миллиарда значений. Здесь "6" по-прежнему является значением O (logN), но это невероятно малое значение, поэтому вы выбрали эту удивительную структуру данных, потому что "мне действительно нужно O (1)", это глупо. Это подчеркивает, что большинство других ответов на этот вопрос просто ошибочны с точки зрения прагматика, который хочет, чтобы их алгоритм "быстро работал" и "хорошо масштабировался", независимо от того, что говорит "теория".

ИЗМЕНИТЬ

См. также

http://queue.acm.org/detail.cfm?id=1814327

в котором говорится

Какая польза от алгоритма O (log2 (n)) если эти операции вызывают сбои страницы и медленные операции с дисками? Для большинства соответствующие наборы данных O (n) или даже O (n ^ 2), который избегает страницы сбои, вокруг него будут круги.

(но прочитайте статью для контекста).

Ответ 2

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

O (1) и O (logn) делает большой разницу, когда вы начинаете комбинировать алгоритмы.

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

Для больших входов, если у вас уже был алгоритм O (n ^ 2), вы бы скорее сделали операцию, которая была O (1) внутри, а не O (logn) внутри.

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

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

Ответ 3

Это распространенная ошибка - помните, что примечание Big O НЕ говорит вам об абсолютной производительности алгоритма при заданном значении, просто рассказывая вам о поведении алгоритма при увеличении размера ввода.

Когда вы берете его в этом контексте, становится ясно, почему алгоритм A ~ O (logN) и алгоритм алгоритма B ~ O (1) различны:

если я запустил A на входе размера a, а затем на входе размером 1000000 * a, я могу ожидать, что второй вход займет log (1,000,000) раз, пока первый вход

если я запустил B на входе размера a, то на входе размером 1000000 * a, я могу ожидать, что второй вход займет примерно столько же времени, что и первый вход

EDIT: размышляя над своим вопросом, я думаю, что в нем есть какая-то мудрость. Хотя я бы никогда не сказал, что правильно сказать O (lgN) == O (1), It IS, возможно, что алгоритм O (lgN) может использоваться по алгоритму O (1). Это приводит к тому, что выше абсолютной производительности: просто знание одного алгоритма - O (1), а другой алгоритм O (lgN) - NOT, чтобы объявить, что вы должны использовать O (1) над O (lgN), конечно, возможно, учитывая ваш диапазон возможных входов, O (lgN) может служить вам лучше всего.

Ответ 4

Вы попросили пример в реальном мире. Я дам вам один. Вычислительная биология. Одна цепочка ДНК, закодированная в ASCII, находится где-то на уровне гигабайт в пространстве. У типичной базы данных, очевидно, будет много тысяч таких нитей.

Теперь, в случае алгоритма индексирования/поиска, лог (n) множественный имеет большую разницу при сочетании с константами. Причина почему? Это одно из приложений, где размер вашего ввода является астрономическим. Кроме того, размер ввода будет продолжать расти.

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

Ответ 5

Равенство, как вы его описываете, является распространенным злоупотреблением нотами.

Чтобы уточнить: мы обычно пишем f (x) = O (logN), чтобы обозначить: "f (x) есть O (logN)".

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

Ответ 6

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

Что делать, если все операции занимают 1 час? Разность между O (log N) и O (1) тогда велика даже при малых N.

Или, если вам нужно запустить алгоритм десять миллионов раз? Хорошо, это заняло 30 минут, поэтому, когда я запускаю его в наборе данных в сто раз больше, он все равно должен принимать 30 минут, потому что O (logN) "тот же", что и O (1)... eh... what?

Ваше утверждение, что "я понимаю O (f (N))", явно неверно.

Приложения реального мира, о... Я не знаю.... КАЖДОЕ ИСПОЛЬЗОВАНИЕ O() - обозначение КОГДА-ЛИБО?

Двоичный поиск в отсортированном списке из 10 миллионов элементов, например. Это очень ПРИЧИНА, мы используем хеш-таблицы, когда данные становятся достаточно большими. Если вы считаете, что O (logN) совпадает с O (1), то почему вы ВСЕГДА используете хеш вместо двоичного дерева?

Ответ 7

Как уже многие говорили, для реального мира вам нужно сначала взглянуть на постоянные факторы, прежде чем даже беспокоиться о факторах O (log N).

Затем рассмотрите, что вы ожидаете от N. Если у вас есть веские основания думать, что N < 10, вы можете использовать линейный поиск вместо двоичного. Это O (N) вместо O (log N), которое в соответствии с вашими огнями было бы значительным, но линейный поиск, который перемещает найденные элементы на фронт, может превосходить более сложное сбалансированное дерево в зависимости от приложения.

С другой стороны, обратите внимание, что даже если лог N не может превышать 50, коэффициент производительности 10 действительно огромен - если вы связаны с вычислением, такой фактор может легко сделать или сломать ваш выражение. Если этого недостаточно для вас, вы часто увидите факторы (log N) ^ 2 или (logN) ^ 3 в алгоритмах, поэтому, даже если вы считаете, что можете игнорировать один фактор (log N), это не означает вы можете игнорировать их больше.

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

Около 30 лет назад кто-то разработал алгоритм полиномиального времени для линейного программирования, но он не был изначально практичным, потому что результат был слишком медленным.

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

Ответ 8

Замечание о том, что O(log n) часто неотличимо от O(1), является хорошим.

В качестве знакомого примера предположим, что мы хотели найти один элемент в отсортированном массиве из 1 000 000 000 000 элементов:

• с линейным поиском поиск занимает в среднем 500 000 000 000 шагов
• с бинарным поиском, поиск занимает в среднем 40 шагов.

Предположим, мы добавили один элемент в массив, который мы ищем, и теперь мы должны искать другой элемент:

• с линейным поиском поиск занимает в среднем 500 000 000 001 шаг (неразличимые изменения)
• с бинарным поиском, поиск занимает в среднем 40 шагов (неразличимое изменение)

Предположим, что мы удвоили количество элементов в массиве, который мы ищем, и теперь мы должны искать другой элемент:

• с линейным поиском поиск занимает в среднем 1 000 000 000 000 шагов (необычайно заметное изменение).
• с бинарным поиском, поиск занимает в среднем 41 шаг (неразличимое изменение)

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

Точка выгрузки такова: * мы используем алгоритмы O(log n), потому что они часто неотличимы от постоянного времени и потому, что они часто выполняют феноменально лучше, чем линейные алгоритмы времени.

Очевидно, что эти примеры предполагают разумные константы. Очевидно, что это общие наблюдения и не применяются ко всем случаям. Очевидно, что эти точки применимы к асимптотическому концу кривой, а не к концу n=3.

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

Ответ 9

Вам может быть интересен Soft-O, который игнорирует логарифмическую стоимость. Проверьте этот пункт в Википедии.

Ответ 10

Что вы имеете в виду, важно ли это или нет?

Если вы столкнулись с выбором алгоритма O(1) и O(lg n), то вы не должны считать, что они равны. Вы должны выбрать постоянное время. Почему бы вам не быть?

И если алгоритм с постоянным временем не существует, то логарифмическое время обычно лучше всего вы можете получить. Опять же, имеет ли это значение? Вам просто нужно взять самое быстрое, что вы можете найти.

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

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

Поэтому вместо того, чтобы спрашивать, "важно", чтобы вы считали логарифмическую сложность постоянной в "реальном мире", я бы спросил, есть ли в этом смысл.

Часто вы можете предположить, что логарифмические алгоритмы достаточно быстры, но что вы получаете, считая их постоянными?

Ответ 11

O (logN) * ​​O (logN) * ​​O (logN) сильно отличается. O (1) * O (1) * O (1) по-прежнему постоянна. Также простой O (nlogn) в стиле быстрой сортировки отличается от O (n O (1)) = O (n). Попробуйте отсортировать 1000 и 1000000 элементов. Последнее не в 1000 раз медленнее, это 2000 раз, потому что log (n ^ 2) = 2log (n)

Ответ 12

Название вопроса является вводящим в заблуждение (хорошо подобранным для обсуждения, помните).

O (log N) == O (1), очевидно, неверно (и плакат знает об этом). Обозначение Big O, по определению, рассматривает асимптотический анализ. Когда вы видите O (N), N берется для приближения к бесконечности. Если N присваивается константа, это не Big O.

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

Анализ Big O классный, потому что он позволяет сравнивать алгоритмы, не увязывая проблемы платформы (размер слов, инструкции на операцию, скорость памяти и скорость диска). Когда N уходит в бесконечность, эти проблемы исчезают. Но когда N 10000, 1000, 100, эти проблемы вместе со всеми остальными, которые мы оставили вне функции O, начинают иметь значение.

Чтобы ответить на вопрос о плакате: O (log N)!= O (1), и вы правы, алгоритмы с O (1) иногда не намного лучше, чем алгоритмы с O (log N), в зависимости на размер ввода и все те внутренние константы, которые были опущены во время анализа Big O.

Если вы знаете, что собираетесь прокручивать N, используйте анализ Big O. Если вы этого не сделаете, вам потребуются эмпирические тесты.

Ответ 13

Теоретически

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

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

Практически

Если вы читаете оригинальные статьи Ларри Пейджа и Сергея Брина в архитектуре Google, они рассказывают об использовании хеш-таблиц для всего, чтобы убедиться, что, например, поиск кэшированной веб-страницы требует всего лишь одного поиска жесткого диска. Если вы использовали индексы B-tree для поиска, вам может понадобиться четыре или пять попыток жесткого диска, чтобы выполнить поиск без кэша [*]. Четырёхкратный набор требований к вашему хранилищу на вашем кэшированном хранилище веб-страниц стоит заботиться с точки зрения бизнеса и предсказуем, если вы не изгоняете все термины O (log (n)).

P.S. Извините за использование Google в качестве примера, они похожи на Гитлера в версии для компьютеров Закон Годвина.

[*] Предполагая, что 4KB читает с диска, 100bn веб-страниц в индексе, ~ 16 байт на ключ в B-дереве node.

Ответ 14

Да, log (N) < 100 для большинства практических целей, и Нет, вы не всегда можете заменить его на константу.

Например, это может привести к серьезным ошибкам в оценке производительности вашей программы. Если O (N) запрограммировал массив из 1000 элементов за 1 мс, вы уверены, что он обработает 10 элементов ⁶ за 1 секунду (или около того). Если, однако, программа O (N * logN), то для обработки 10 ⁶ элементов потребуется ~ 2 сек. Это различие может иметь решающее значение - например, вы можете подумать, что у вас достаточно мощности сервера, потому что вы получаете 3000 запросов в час, и вы думаете, что ваш сервер может обрабатывать до 3600.

Другой пример. Представьте, что у вас есть функция f(), работающая в O (logN), и на каждую итерационную функцию g(), которая также работает в O (logN). Затем, если вы замените оба журнала на константы, вы считаете, что ваша программа работает в постоянное время. Реальность будет жестокой, хотя - два журнала могут дать вам до 100 * 100 мультипликаторов.

Ответ 15

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

Однако, конечно, это не вся история - например, вы можете заметить, что алгоритмы quicksort всегда будут переключаться на сортировку вставки для небольших элементов (Wikipedia говорит 8-20) из-за поведения обоих алгоритмов на небольших наборах данных.

Итак, это вопрос понимания того, какие компромиссы вы будете делать, что подразумевает глубокое понимание проблемы, архитектуры и опыта, чтобы понять, что использовать, и как настроить константы.

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

Ответ 16

Правила определения нотации Big-O проще, если вы не решаете, что O (log n) = O (1).

Как сказал krzysio, вы можете накапливать O (log n) s, а затем они будут иметь очень заметную разницу. Представьте, что вы выполняете бинарный поиск: O (log n), а затем представляете, что каждая сложность сравнения O (log n). Если вы пренебрегаете обоими, вы получаете O (1) вместо O (log ² n). Точно так же вы можете как-то прийти к O (log ¹⁰ n), а затем вы заметите большую разницу для не слишком больших "n" s.

Ответ 17

Предположим, что во всем приложении один алгоритм составляет 90% времени, когда пользователь ждет самую обычную операцию.

Предположим, что в реальном времени операция O (1) занимает вторую по вашей архитектуре, а операция O (logN) в основном .5 секунд * log (N). Ну, в этот момент я бы очень хотел нарисовать вам график со стрелкой на пересечении кривой и линии, сказав: "Это имеет значение прямо здесь". Вы хотите использовать log (N) op для небольших наборов данных и O (1) op для больших наборов данных в таком сценарии.

Обозначение Big-O и оптимизация производительности - это академическое упражнение, а не предоставление реальной ценности пользователю для операций, которые уже дешевы, но если это дорогостоящая операция на критическом пути, то вы ставите в этом дело!

Ответ 18

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

Все большие-O говорят, что вы являетесь формой этой функции.

• O (1) означает, что существует некоторое число A такое, что f (N) A при больших N.

• O (N) означает, что существует некоторое A такое, что f (N) AN для больших N.

• O (N ^ 2) означает, что существует некоторое A такое, что f (N) AN ^ 2 при больших N.

• O (log (N)) означает, что существует некоторое A такое, что f (N) AlogN для больших N.

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

Ответ 19

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

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

Ответ 20

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

Ответ 21

O (log N) может вводить в заблуждение. Возьмем, к примеру, операции над Красно-Черные деревья.
Операции O (logN), но довольно сложные, что означает много операций низкого уровня.

Ответ 22

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

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

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

Я хочу сказать, что если у вас есть N элементов, они не могут исчезнуть. Другими словами, вы можете выбирать между неэффективными алгоритмами O (n ^ 2) или хуже, а O (n.logN): это реальный выбор. Но вы никогда не идете O (1).

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

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

Это хорошая идея сделать это случайно? Только если ваша проблема спросила также о втором, третьем и т.д. Элементах. Тогда ваша первоначальная проблема была действительно O (NLogN), а не O (N).

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

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

Ответ 23

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