Есть ли случаи, когда вы бы предпочли O(log n)
сложность O(1)
времени сложности времени? Или O(n)
к O(log n)
?
У вас есть примеры?
algorithm
big-o
time-complexity
V.Leymarie
источник
источник
O(log n)
алгоритмO(1)
алгоритму, если понимаю первое, но не второе ...Ответы:
Может быть много причин предпочесть алгоритм с более высокой сложностью O-времени по сравнению с более низкой:
10^5
лучше, с точки зрения big-O, чем1/10^5 * log(n)
(O(1)
vsO(log(n)
), но для наиболее разумногоn
первый будет работать лучше. Например, лучшая сложность для умножения матриц заключается вO(n^2.373)
том, что константа настолько высока, что никакие (насколько мне известно) вычислительные библиотеки ее не используют.O(n*log(n))
илиO(n^2)
алгоритм.O(log log N)
временную сложность , чтобы найти элемент, но есть также бинарное дерево , которое находит то же самое вO(log n)
. Даже для огромного количестваn = 10^20
разница незначительна.O(n^2)
и требуетO(n^2)
памяти. Это может быть предпочтительным воO(n^3)
времени иO(1)
пространстве, когда n не очень велико. Проблема в том, что вы можете долго ждать, но очень сомневаетесь, что сможете найти достаточно большой объем ОЗУ, чтобы использовать его с вашим алгоритмом.в некоторых местах (безопасность) сложность может быть требованием. Никто не хочет иметь алгоритм хеширования, который может молниеносно быстро хэшировать (потому что тогда другие люди могут обмануть вас намного быстрее)O(n^2)
сортировка вставкой имеет среднюю сложность по времени , хуже, чем быстрая сортировка или сортировка слиянием, но в качестве онлайн-алгоритма она может эффективно сортировать список значений по мере их получения (как ввод данных пользователем), где большинство других алгоритмов могут работать только эффективно. на полный список значений.источник
Всегда есть скрытая константа, которая может быть ниже в алгоритме O (log n ). Таким образом, на реальных данных он может работать быстрее.
Есть также проблемы с пространством (например, бег на тостере).
Существует также проблема времени разработчика - O (log n ) может быть в 1000 раз легче реализовать и проверить.
источник
lg n
это так, так близко кk
большому,n
что большинство операций никогда не заметят разницы.Я удивлен, что никто еще не упомянул приложения, связанные с памятью.
Может существовать алгоритм, который имеет меньше операций с плавающей запятой либо из-за его сложности (то есть O (1) < O (log n )), либо потому, что константа перед сложностью меньше (то есть 2 n 2 <6 n 2 ) , Несмотря на это, вы все равно можете предпочесть алгоритм с большим количеством FLOP, если алгоритм с меньшим FLOP больше связан с памятью.
Под «привязкой к памяти» я подразумеваю, что вы часто получаете доступ к данным, которые постоянно находятся вне кэша. Чтобы получить эти данные, вы должны извлечь память из фактически используемой памяти в кэш-память, прежде чем сможете выполнять с ней операции. Этот шаг извлечения часто довольно медленный - намного медленнее, чем ваша операция.
Следовательно, если вашему алгоритму требуется больше операций (хотя эти операции выполняются с данными, уже находящимися в кэше [и, следовательно, выборка не требуется]), он все равно превзойдет ваш алгоритм с меньшим количеством операций (которые должны быть выполнены вне -кэшировать данные [и, следовательно, требовать выборку]) с точки зрения фактического времени ожидания.
источник
O(logn)
закончитьO(1)
. Вы можете легко представить себе ситуацию, когда, по всей вероятностиn
, приложение с меньшим объемом памяти будет работать быстрее, даже с большей сложностью.В тех случаях, когда важна безопасность данных, более сложный алгоритм может быть предпочтительнее, чем менее сложный алгоритм, если более сложный алгоритм обладает большей устойчивостью к атакам по времени .
источник
(n mod 5) + 1
, оно все ещеO(1)
, но показывает информацию оn
. Поэтому более сложный алгоритм с более плавным временем выполнения может быть предпочтительным, даже если он может быть асимптотически (и, возможно, даже на практике) медленнее.Алистра прибила его, но не привела никаких примеров, так что я буду.
У вас есть список из 10000 кодов UPC для того, что продает ваш магазин. UPC из 10 цифр, целое число для цены (цена в копейках) и 30 символов описания для квитанции.
Подход O (log N): у вас есть отсортированный список. 44 байта, если ASCII, 84, если Unicode. С другой стороны, обработайте UPC как int64, и вы получите 42 и 72 байта. 10000 записей - в самом высоком случае вы смотрите на мегабайт памяти.
Подход O (1): не храните UPC, вместо этого вы используете его как запись в массиве. В самом низком случае вы смотрите почти треть терабайта памяти.
Какой подход вы используете, зависит от вашего оборудования. На большинстве разумных современных конфигураций вы будете использовать подход log N. Я могу представить себе, что второй подход - правильный ответ, если по какой-то причине вы работаете в среде, где ОЗУ критически мало, но у вас достаточно места для хранения. Треть терабайта на диске - это не проблема, получение ваших данных в одном исследовании диска чего-то стоит. Простой бинарный подход занимает в среднем 13. (Заметьте, однако, что, кластеризовав ваши ключи, вы можете получить это до гарантированного 3 чтения, и на практике вы бы кэшировали первое.)
источник
malloc(search_space_size)
и подписаться на то, что он возвращает, так же просто, как и получить.Рассмотрим красно-черное дерево. Он имеет доступ, поиск, вставка и удаление
O(log n)
. Сравните с массивом, который имеет доступO(1)
и остальные операцииO(n)
.Поэтому, учитывая приложение, в которое мы вставляем, удаляем или выполняем поиск чаще, чем получаем доступ, и выбираем только между этими двумя структурами, мы бы предпочли красно-черное дерево. В этом случае вы можете сказать, что мы предпочитаем более громоздкое
O(log n)
время доступа к красно-черному дереву .Зачем? Потому что доступ не является нашей главной заботой. Мы делаем компромисс: на производительность нашего приложения больше влияют другие факторы, чем этот. Мы позволяем этому конкретному алгоритму снижать производительность, потому что мы добиваемся большого выигрыша, оптимизируя другие алгоритмы.
Таким образом, ответ на ваш вопрос просто так: когда скорость роста алгоритма не то, что мы хотим оптимизировать , когда мы хотим оптимизировать что-то еще, Все остальные ответы являются частными случаями этого. Иногда мы оптимизируем время выполнения других операций. Иногда мы оптимизируем для памяти. Иногда мы оптимизируем для безопасности. Иногда мы оптимизируем ремонтопригодность. Иногда мы оптимизируем время разработки. Даже переопределяющая константа, будучи достаточно низкой, чтобы иметь значение, оптимизирует время выполнения, когда вы знаете, что скорость роста алгоритма не оказывает наибольшего влияния на время выполнения. (Если бы ваш набор данных был вне этого диапазона, вы бы оптимизировали скорость роста алгоритма, потому что он в конечном итоге доминировал бы над константой.) Все имеет свою стоимость, и во многих случаях мы обмениваем стоимость более высокой скорости роста на алгоритм оптимизации чего-то другого.
источник
O(log n)
«красно-черным деревом»? Вставка5
в позицию 2 массива[1, 2, 1, 4]
приведет к[1, 2, 5, 1 4]
(элемент4
получит индекс, обновленный с 3 до 4). Как вы собираетесь включить это поведение вO(log n)
«красно-черное дерево», которое вы называете «отсортированным списком»?Да.
В реальном случае мы выполнили несколько тестов по поиску в таблице как с короткими, так и с длинными строковыми ключами.
Мы использовали a
std::map
, astd::unordered_map
с хешем, который выбирает самое большее в 10 раз по длине строки (наши ключи имеют тенденцию быть похожими на guid, так что это прилично), и хеш, который выбирает каждый символ (в теории уменьшает коллизии), несортированный вектор, в котором мы выполняем==
сравнение, и (если я правильно помню) несортированный вектор, в котором мы также сохраняем хеш, сначала сравниваем хеш, а затем сравниваем символы.Эти алгоритмы варьируются от
O(1)
(unordered_map) доO(n)
(линейный поиск).Для скромного размера N довольно часто O (n) побеждает O (1). Мы подозреваем, что это связано с тем, что контейнеры на основе узлов требовали, чтобы наш компьютер больше перемещался в памяти, а контейнеры на линейной основе - нет.
O(lg n)
существует между двумя. Я не помню, как это было.Разница в производительности была не такой большой, и на больших наборах данных хэш-результаты работали намного лучше. Итак, мы остановились на неупорядоченной карте на основе хеша.
На практике для разумных размеров n
O(lg n)
естьO(1)
. Если на вашем компьютере есть место только для 4 миллиардов записей в вашей таблице, тоO(lg n)
оно ограничено сверху32
. (lg (2 ^ 32) = 32) (в информатике lg - сокращение от журнала на основе 2).На практике алгоритмы lg (n) работают медленнее, чем алгоритмы O (1), не из-за логарифмического фактора роста, а потому, что часть lg (n) обычно означает, что алгоритм имеет определенный уровень сложности, и эта сложность добавляет больший постоянный фактор, чем любой из «роста» от члена LG (N).
Однако сложные алгоритмы O (1) (такие как отображение хеша) могут легко иметь аналогичный или больший постоянный коэффициент.
источник
Возможность выполнения алгоритма параллельно.
Я не знаю, есть ли пример для классов
O(log n)
иO(1)
, но для некоторых проблем вы выбираете алгоритм с более высоким классом сложности, когда алгоритм легче выполнять параллельно.Некоторые алгоритмы не могут быть распараллелены, но имеют очень низкий класс сложности. Рассмотрим другой алгоритм, который достигает того же результата и может быть легко распараллелен, но имеет более высокий класс сложности. При выполнении на одной машине второй алгоритм работает медленнее, но при выполнении на нескольких машинах реальное время выполнения становится все меньше и меньше, в то время как первый алгоритм не может ускориться.
источник
Допустим, вы внедряете черный список во встроенной системе, где цифры от 0 до 1 000 000 могут быть в черном списке. Это оставляет вам два возможных варианта:
Доступ к битам будет иметь гарантированный постоянный доступ. С точки зрения сложности времени, это оптимально. Как с теоретической, так и с практической точки зрения (это O (1) с чрезвычайно низким постоянным расходом).
Тем не менее, вы можете предпочесть второе решение. Особенно, если вы ожидаете, что число чисел, занесенных в черный список, будет очень маленьким, так как это будет более эффективно использовать память.
И даже если вы не разрабатываете для встраиваемой системы, где не хватает памяти, я просто могу увеличить произвольный предел от 1 000 000 до 1 000 000 000 000 и выдвинуть тот же аргумент. Тогда для набора битов потребуется около 125 ГБ памяти. Наличие гарантированной комплексности O (1) в худшем случае может не убедить вашего босса предоставить вам такой мощный сервер.
Здесь я бы настоятельно предпочел бинарный поиск (O (log n)) или двоичное дерево (O (log n)) над набором битов O (1). И, вероятно, хеш-таблица с наихудшей сложностью O (n) превзойдет их всех на практике.
источник
Мой ответ здесь Быстрый случайный взвешенный выбор по всем строкам стохастической матрицы является примером, где алгоритм со сложностью O (m) быстрее, чем алгоритм со сложностью O (log (m)), когда
m
он не слишком велик.источник
Люди уже ответили на ваш точный вопрос, поэтому я решу немного другой вопрос, о котором люди могут подумать, приезжая сюда.
Многие алгоритмы «O (1) времени» и структуры данных на самом деле занимают только ожидаемое время O (1), а это означает, что их среднее время работы составляет O (1), возможно, только при определенных допущениях.
Типичные примеры: хеш-таблицы, расширение «списков массивов» (или динамических размеров массивов / векторов).
В таких сценариях вы можете предпочесть использовать структуры данных или алгоритмы, чье время гарантированно будет абсолютно логарифмически ограничено, даже если они в среднем могут работать хуже.
Таким образом, примером может служить сбалансированное двоичное дерево поиска, время выполнения которого в среднем хуже, но лучше в худшем случае.
источник
Более общий вопрос, если есть ситуации , в которых один предпочел бы
O(f(n))
алгоритм вO(g(n))
алгоритм , хотя ,g(n) << f(n)
какn
стремится к бесконечности. Как уже упоминали другие, ответ явно «да» в том случае, когдаf(n) = log(n)
иg(n) = 1
. Иногда да даже в случаеf(n)
полиномиального, ноg(n)
экспоненциального. Известный и важный пример - это Симплексный алгоритм для решения задач линейного программирования. В 1970-х годах это было доказаноO(2^n)
. Таким образом, его худшее поведение невозможно. Но - его поведение в среднем случае чрезвычайно хорошо, даже для практических задач с десятками тысяч переменных и ограничений. В 1980-х годах алгоритмы полиномиального времени (такиеАлгоритм внутренней точки Кармаркара ) для линейного программирования был открыт, но спустя 30 лет симплекс-алгоритм все еще остается алгоритмом выбора (за исключением некоторых очень больших задач). Это по очевидной причине, что поведение в среднем случае часто более важно, чем поведение в худшем случае, но также и по более тонкой причине, что симплексный алгоритм в некотором смысле более информативен (например, информацию о чувствительности легче извлечь).источник
Чтобы положить мои 2 цента в:
Иногда алгоритм худшей сложности выбирается вместо лучшего, когда алгоритм работает в определенной аппаратной среде. Предположим, что наш алгоритм O (1) не последовательно обращается к каждому элементу очень большого массива фиксированного размера для решения нашей проблемы. Затем поместите этот массив на механический жесткий диск или магнитную ленту.
В этом случае алгоритм O (logn) (предположим, он последовательно обращается к диску) становится более благоприятным.
источник
Существует хороший вариант использования алгоритма O (log (n)) вместо алгоритма O (1), который многие другие ответы проигнорировали: неизменность. Хеш-карты имеют O (1), помещают и получают, предполагая хорошее распределение значений хеша, но они требуют изменяемого состояния. Неизменяемые древовидные карты имеют O (log (n)), которые помещают и получают, что асимптотически медленнее. Однако неизменность может быть достаточно ценной, чтобы компенсировать худшую производительность, и в случае, когда необходимо сохранить несколько версий карты, неизменность позволяет избежать необходимости копировать карту, то есть O (n), и, следовательно, может улучшить производительность.
источник
Просто: потому что коэффициент - затраты, связанные с настройкой, хранением и временем выполнения этого шага - может быть намного, намного больше при меньшей проблеме большого-O, чем при большей. Big-O является лишь мерой масштабируемости алгоритмов .
Рассмотрим следующий пример из словаря хакеров, предлагающий алгоритм сортировки, основанный на интерпретации квантовой механики множественных миров :
(Источник: http://catb.org/~esr/jargon/html/B/bogo-sort.html )
Обратите внимание на то, что биг-О этого алгоритма
O(n)
превосходит любой известный на сегодняшний день алгоритм сортировки общих элементов. Коэффициент линейного шага также очень низок (поскольку это только сравнение, а не своп, который выполняется линейно). Подобный алгоритм может фактически использоваться для решения любой проблемы как в NP, так и в co-NP за полиномиальное время, поскольку каждое возможное решение (или возможное доказательство отсутствия решения) может быть сгенерировано с использованием квантового процесса, а затем проверено в полиномиальное времяОднако в большинстве случаев мы, вероятно, не хотим рисковать тем, что множественные миры могут быть неправильными, не говоря уже о том, что действие по осуществлению шага 2 все еще «оставлено в качестве упражнения для читателя».
источник
В любой точке, когда n ограничено и коэффициент умножения алгоритма O (1) выше, чем предел для log (n). Например, хранение значений в хэш-наборе равно O (1), но может потребовать дорогостоящего вычисления хеш-функции. Если элементы данных можно сравнивать тривиально (относительно некоторого порядка), а ограничение на n таково, что log n значительно меньше, чем вычисление хеш-функции для любого одного элемента, тогда сохранение в сбалансированном двоичном дереве может быть быстрее, чем сохранение в хэшсет.
источник
В ситуации реального времени, когда вам нужна четкая верхняя граница, вы должны выбрать, например, heapsort, а не Quicksort, потому что среднее поведение heapsort также является его худшим вариантом.
источник
Добавление к и без того хорошим ответам. Практическим примером могут служить хэш-индексы и индексы B-дерева в базе данных postgres.
Хеш-индексы образуют хеш-таблицу для доступа к данным на диске, в то время как btree, как следует из названия, использует структуру данных Btree.
В Big-O это O (1) против O (logN).
Хеш-индексы в настоящее время не одобряются в postgres, поскольку в реальной ситуации, особенно в системах баз данных, хеширование без коллизий очень сложно (может привести к O (N) сложности в худшем случае), и из-за этого его еще сложнее сделать они безопасны при сбоях (называется запись впереди регистрации - WAL в postgres).
Этот компромисс достигается в этой ситуации, поскольку O (logN) достаточно хорош для индексов, а реализация O (1) довольно сложна, и разница во времени не будет иметь большого значения.
источник
Когда
n
мало иO(1)
постоянно медленно.источник
или
источник
источник
Это часто относится к приложениям безопасности, в которых мы хотим разрабатывать задачи, алгоритмы которых умышленно работают медленно, чтобы помешать кому-либо получить ответ на проблему слишком быстро.
Вот несколько примеров из головы.
O(2^n)
время, которое, мы надеемся,n
будет битовой длиной ключа (это грубая сила).В других местах в CS быстрая сортировка
O(n^2)
в худшем случае, но в общем случаеO(n*log(n))
. По этой причине анализ Big O иногда не является единственной вещью, о которой вы заботитесь при анализе эффективности алгоритма.источник