Есть ли случаи, когда вы бы предпочли более высокий алгоритм сложности с большим временем, чем более низкий?

243

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

У вас есть примеры?

V.Leymarie
источник
67
Я бы предпочел O(log n)алгоритм O(1)алгоритму, если понимаю первое, но не второе ...
Кодор
14
Есть масса непрактичных структур данных с O (1) операциями из теоретической информатики. Одним примером будет select () для битовых векторов, который может поддерживаться в o (n) дополнительном пространстве и O (1) на операцию, используя 5 уровней косвенности. Простой двоичный поиск в сочетании с O (1) rank () оказывается быстрее на практике, согласно автору сжатой структуры данных
Никлас Б.
17
Более низкая асимптотическая сложность не гарантирует более быстрое время выполнения. Исследование матрицы умножения для конкретного примера.
Коннор Кларк
54
Также ... любой алгоритм может быть преобразован в O (1), учитывая достаточно большой поиск в таблице;)
Коннор Кларк,
19
@Hoten - Предполагается, что поиск по таблице равен O (1), что совсем не дано для размера таблиц, о которых вы говорите! :)
январь

Ответы:

267

Может быть много причин предпочесть алгоритм с более высокой сложностью O-времени по сравнению с более низкой:

  • Большую часть времени труднее достичь более низкой сложности Big-O, требующей квалифицированной реализации, большого количества знаний и большого количества тестирования.
  • big-O скрывает детали о константе : алгоритм, который работает 10^5лучше, с точки зрения big-O, чем 1/10^5 * log(n)( O(1)vs O(log(n)), но для наиболее разумного nпервый будет работать лучше. Например, лучшая сложность для умножения матриц заключается в O(n^2.373)том, что константа настолько высока, что никакие (насколько мне известно) вычислительные библиотеки ее не используют.
  • big-O имеет смысл, когда вы рассчитываете что-то большое. Если вам нужно отсортировать массив из трех чисел, это не имеет большого значения, используете ли вы 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 не очень велико. Проблема в том, что вы можете долго ждать, но очень сомневаетесь, что сможете найти достаточно большой объем ОЗУ, чтобы использовать его с вашим алгоритмом.
  • распараллеливание - хорошая функция в нашем распределенном мире. Существуют алгоритмы, которые легко распараллеливаются, а есть алгоритмы, которые вообще не распараллеливаются. Иногда имеет смысл запускать алгоритм на 1000 обычных машинах с более высокой сложностью, чем на одной машине с немного большей сложностью.
  • в некоторых местах (безопасность) сложность может быть требованием. Никто не хочет иметь алгоритм хеширования, который может молниеносно быстро хэшировать (потому что тогда другие люди могут обмануть вас намного быстрее)
  • хотя это не связано с переключением сложности, но некоторые функции безопасности должны быть написаны таким образом, чтобы предотвратить атаку по времени . Они в основном остаются в одном классе сложности, но модифицируются таким образом, что всегда требуется худший случай, чтобы что-то сделать. Один пример сравнивает, что строки равны. В большинстве приложений имеет смысл быстрое прерывание, если первые байты отличаются, но в безопасности вы все равно будете ждать, пока самый конец не сообщит плохие новости.
  • кто-то запатентовал алгоритм более низкой сложности, и для компании более экономно использовать более высокую сложность, чем платить деньги.
  • некоторые алгоритмы хорошо адаптируются к конкретным ситуациям. Например, O(n^2)сортировка вставкой имеет среднюю сложность по времени , хуже, чем быстрая сортировка или сортировка слиянием, но в качестве онлайн-алгоритма она может эффективно сортировать список значений по мере их получения (как ввод данных пользователем), где большинство других алгоритмов могут работать только эффективно. на полный список значений.
Сальвадор Дали
источник
6
Кроме того, я несколько раз видел, что люди были сосредоточены на большом количестве их центрального алгоритма, но игнорировали затраты на установку. Например, создание хеш-таблицы может оказаться более дорогостоящим, чем линейный просмотр массива, если вам не нужно делать это снова и снова. Фактически, благодаря тому, как создаются современные процессоры, даже что-то вроде двоичного поиска может быть столь же быстрым в отсортированных массивах, как и линейный поиск - профилирование является необходимостью.
Луаан
@Luaan "На самом деле, благодаря тому, как создаются современные процессоры, даже что-то вроде двоичного поиска в отсортированных массивах может быть столь же быстрым, как и линейный поиск - профилирование является необходимостью". Интересный! Можете ли вы объяснить, как бинарный поиск и линейный поиск могут занимать одинаковое количество времени в современном процессоре?
DJG
3
@Luaan - Неважно, я нашел это: schani.wordpress.com/2010/04/30/linear-vs-binary-search
DJG
2
@DenisdeBernardy: Нет, на самом деле это не так. Они могут быть алгоритмами в P. И даже если бы они не были, при разумных определениях, что означает распараллеливание, это также не подразумевало бы P! = NP. Также помните, что поиск пространства возможных прогонов недетерминированной машины Тьюринга вполне параллелизуем.
einpoklum
228

Всегда есть скрытая константа, которая может быть ниже в алгоритме O (log n ). Таким образом, на реальных данных он может работать быстрее.

Есть также проблемы с пространством (например, бег на тостере).

Существует также проблема времени разработчика - O (log n ) может быть в 1000 раз легче реализовать и проверить.

Алистра
источник
Приятно спасибо. Я думал, что также может быть целесообразно рассмотреть алгоритм O (logn) для обеспечения стабильности программы (например, в
самобалансируемых
16
Один пример, который я могу вспомнить: для небольшого отсортированного массива программисту было бы проще и компактнее реализовать функцию двоичного поиска, чем написать полную реализацию карты хеш-кода и использовать ее вместо этого.
полковник тридцать два
5
Пример сложности: найти медиану несортированного списка легко в O (n * log n), но трудно в O (n).
Пол Дрейпер
1
-1, не кладите бревна в тостер ... Шутка в сторону, это место. lg nэто так, так близко к kбольшому, nчто большинство операций никогда не заметят разницы.
CorsiKa
3
Существует также тот факт, что алгоритмические сложности, с которыми знакомы большинство людей, не учитывают эффекты кэширования. По мнению большинства людей поиск чего-либо в двоичном дереве - это O (log2 (n)), но на самом деле это намного хуже, потому что двоичные деревья имеют плохую локальность.
Доваль
57

Я удивлен, что никто еще не упомянул приложения, связанные с памятью.

Может существовать алгоритм, который имеет меньше операций с плавающей запятой либо из-за его сложности (то есть O (1) < O (log n )), либо потому, что константа перед сложностью меньше (то есть 2 n 2 <6 n 2 ) , Несмотря на это, вы все равно можете предпочесть алгоритм с большим количеством FLOP, если алгоритм с меньшим FLOP больше связан с памятью.

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

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

NoseKnowsAll
источник
1
Алистра обратилась к этому косвенно, когда говорила о «космических проблемах»
Зак Сауцер
2
Огромное количество пропусков кеша только умножает окончательное выполнение на постоянное значение (которое не больше 8 для 4-ядерного процессора с частотой 3,2 ГГц с частотой 1,6 ГГц, обычно оно намного ниже), поэтому оно считается постоянной величиной в большом -О записи. Таким образом, единственное, чего не хватает в кеше, - это сдвиг порогового значения n, когда решение O (n) начинает работать медленнее, чем решение O (1).
Мариан Спаник
1
@MarianSpanik Вы, конечно, правы. Но этот вопрос задал вопрос о ситуации, когда мы предпочли бы O(logn)закончить O(1). Вы можете легко представить себе ситуацию, когда, по всей вероятности n, приложение с меньшим объемом памяти будет работать быстрее, даже с большей сложностью.
NoseKnowsAll
@MarianSpanik - это не потеря кеша до 300 тактов? Откуда 8?
Надеемся, что
43

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

Кевин К
источник
6
Хотя то, что вы сказали, верно, в этом случае алгоритм, выполняемый в O (1), по определению неуязвим для временных атак.
Джастин Лессард
17
@JustinLessard: значение O (1) означает, что существует некоторый размер ввода, после которого время выполнения алгоритма ограничено константой. Что происходит ниже этого порога, неизвестно. Кроме того, пороговое значение может даже не быть соблюдено для любого реального использования алгоритма. Алгоритм может быть линейным и, таким образом, передавать информацию о длине ввода, например.
Йорг Миттаг
12
Время выполнения может также колебаться по-разному, но все еще ограничено. Если время выполнения пропорционально (n mod 5) + 1, оно все еще O(1), но показывает информацию о n. Поэтому более сложный алгоритм с более плавным временем выполнения может быть предпочтительным, даже если он может быть асимптотически (и, возможно, даже на практике) медленнее.
Кристиан Семрау
Именно поэтому bcrypt считается хорошим; это делает вещи медленнее
Дэвид говорит восстановить Монику
@DavidGrinberg Это причина, почему bcrypt используется, и подходит для вопроса. Но это не связано с этим ответом, который говорит о времени атаки.
Кристиан Семрау
37

Алистра прибила его, но не привела никаких примеров, так что я буду.

У вас есть список из 10000 кодов UPC для того, что продает ваш магазин. UPC из 10 цифр, целое число для цены (цена в копейках) и 30 символов описания для квитанции.

Подход O (log N): у вас есть отсортированный список. 44 байта, если ASCII, 84, если Unicode. С другой стороны, обработайте UPC как int64, и вы получите 42 и 72 байта. 10000 записей - в самом высоком случае вы смотрите на мегабайт памяти.

Подход O (1): не храните UPC, вместо этого вы используете его как запись в массиве. В самом низком случае вы смотрите почти треть терабайта памяти.

Какой подход вы используете, зависит от вашего оборудования. На большинстве разумных современных конфигураций вы будете использовать подход log N. Я могу представить себе, что второй подход - правильный ответ, если по какой-то причине вы работаете в среде, где ОЗУ критически мало, но у вас достаточно места для хранения. Треть терабайта на диске - это не проблема, получение ваших данных в одном исследовании диска чего-то стоит. Простой бинарный подход занимает в среднем 13. (Заметьте, однако, что, кластеризовав ваши ключи, вы можете получить это до гарантированного 3 чтения, и на практике вы бы кэшировали первое.)

Лорен Печтель
источник
2
Я немного запутался здесь. Вы говорите о создании массива с 10 миллиардами записей (большая часть которого будет неопределенной) и о том, что UPC рассматривается как индекс в этом массиве?
Дэвид З
7
@DavidZ Да. Если вы используете разреженный массив, вы можете не получить O (1), но он будет использовать только 1 МБ памяти. Если вы используете реальный массив, вам гарантирован доступ O (1), но он будет использовать 1/3 ТБ памяти.
Навин
В современной системе она будет использовать 1/3 ТБ адресного пространства, но это не значит, что она приблизится к такому выделенному количеству резервной памяти. Большинство современных ОС не выделяют хранилище для выделения ресурсов, пока в этом нет необходимости. При этом вы, по сути, скрываете ассоциативную структуру поиска ваших данных в системе виртуальной памяти ОС / оборудования.
Фил Миллер
@Novelocrat Правда, но если вы делаете это на скорости ОЗУ, время поиска не будет иметь значения, нет причин использовать 40 МБ вместо 1 МБ. Версия массива имеет смысл только тогда, когда доступ к хранилищу дорогой - вы отправляетесь на диск.
Лорен Печтел
1
Или когда это не критичная для производительности операция, а время разработчика стоит дорого - сказать malloc(search_space_size)и подписаться на то, что он возвращает, так же просто, как и получить.
Фил Миллер
36

Рассмотрим красно-черное дерево. Он имеет доступ, поиск, вставка и удаление O(log n). Сравните с массивом, который имеет доступ O(1)и остальные операции O(n).

Поэтому, учитывая приложение, в которое мы вставляем, удаляем или выполняем поиск чаще, чем получаем доступ, и выбираем только между этими двумя структурами, мы бы предпочли красно-черное дерево. В этом случае вы можете сказать, что мы предпочитаем более громоздкое O(log n)время доступа к красно-черному дереву .

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

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

jpmc26
источник
Не уверен, что операции, которые позволяют использовать массив с поиском O (1) и обновлениями O (n), соответствуют красно-черному дереву, о чем раньше думали (по крайней мере, я). Большую часть времени я бы сначала подумал о поиске на основе ключей для красно-черного дерева. Но для сопоставления с массивом это должна быть немного другая структура, которая хранит количество подузлов в верхних узлах для обеспечения поиска на основе индекса и переиндексации при вставке. Хотя я согласен с тем, что красно-черный цвет можно использовать для поддержания баланса, вы можете использовать сбалансированное дерево, если хотите быть неясным в деталях соответствующих операций.
оны
@ony Красно-черное дерево можно использовать для определения структуры типа карты / словаря, но это не обязательно. Узлы могут быть просто элементами, по сути, реализующими отсортированный список.
jpmc26
отсортированный список и массив, который определяет порядок элементов, имеют различное количество информации. Один основан на порядке между элементами и множеством, а другой определяет произвольную последовательность, которая необязательно определяет порядок между элементами. Другое дело, что такое «доступ» и «поиск», которые вы объявляете O(log n)«красно-черным деревом»? Вставка 5в позицию 2 массива [1, 2, 1, 4]приведет к [1, 2, 5, 1 4](элемент 4получит индекс, обновленный с 3 до 4). Как вы собираетесь включить это поведение в O(log n)«красно-черное дерево», которое вы называете «отсортированным списком»?
оны
@ony "отсортированный список и массив, который определяет порядок элементов, имеют различное количество информации." Да, и это является частью того, почему они имеют разные характеристики производительности. Вы упускаете суть. Один не является заменой другого во всех ситуациях. Они оптимизируют разные вещи и делают разные компромиссы , и дело в том, что разработчики постоянно принимают решения об этих компромиссах.
jpmc26
@ony Доступ, поиск, вставка и удаление имеют определенные значения в контексте производительности алгоритма. Доступ извлекает элемент по позиции. Поиск - это поиск элемента по значению (который имеет практическое применение только в качестве проверки локализации для структуры, не связанной с картой). Вставить и удалить должно быть просто. Пример использования можно увидеть здесь .
jpmc26
23

Да.

В реальном случае мы выполнили несколько тестов по поиску в таблице как с короткими, так и с длинными строковыми ключами.

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

Якк - Адам Невраумонт
источник
21

Возможность выполнения алгоритма параллельно.

Я не знаю, есть ли пример для классов O(log n)и O(1), но для некоторых проблем вы выбираете алгоритм с более высоким классом сложности, когда алгоритм легче выполнять параллельно.

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

симулянт
источник
Но все, что делает распараллеливание, это уменьшает постоянный фактор, о котором говорили другие, верно?
gengkev
1
Да, но параллельный алгоритм может делить постоянный коэффициент на 2 каждый раз, когда вы удваиваете количество исполняющих машин. Другой однопоточный алгоритм может уменьшить постоянный коэффициент только один раз постоянным образом. Таким образом, с помощью параллельного алгоритма вы можете динамически реагировать на размер n и быть быстрее во время выполнения настенных часов.
Simulant
15

Допустим, вы внедряете черный список во встроенной системе, где цифры от 0 до 1 000 000 могут быть в черном списке. Это оставляет вам два возможных варианта:

  1. Используйте набор битов в 1 000 000 бит
  2. Используйте отсортированный массив чисел в черном списке и используйте двоичный поиск, чтобы получить к ним доступ

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

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

И даже если вы не разрабатываете для встраиваемой системы, где не хватает памяти, я просто могу увеличить произвольный предел от 1 000 000 до 1 000 000 000 000 и выдвинуть тот же аргумент. Тогда для набора битов потребуется около 125 ГБ памяти. Наличие гарантированной комплексности O (1) в худшем случае может не убедить вашего босса предоставить вам такой мощный сервер.

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

Филипп Классен
источник
12

Люди уже ответили на ваш точный вопрос, поэтому я решу немного другой вопрос, о котором люди могут подумать, приезжая сюда.

Многие алгоритмы «O (1) времени» и структуры данных на самом деле занимают только ожидаемое время O (1), а это означает, что их среднее время работы составляет O (1), возможно, только при определенных допущениях.

Типичные примеры: хеш-таблицы, расширение «списков массивов» (или динамических размеров массивов / векторов).

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

user541686
источник
11

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

Джон Колман
источник
10

Чтобы положить мои 2 цента в:

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

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

uylmz
источник
Я мог бы добавить здесь, что на диске или ленте с последовательным доступом алгоритм O (1) вместо этого становится O (n), поэтому последовательное решение становится более выгодным. Многие операции O (1) зависят от добавления и индексации поиска, являющегося алгоритмом с постоянным временем, которого он не находится в пространстве последовательного доступа.
TheHansinator
9

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

Восстановить Монику
источник
9

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

Рассмотрим следующий пример из словаря хакеров, предлагающий алгоритм сортировки, основанный на интерпретации квантовой механики множественных миров :

  1. Перестановка массива случайным образом, используя квантовый процесс,
  2. Если массив не отсортирован, уничтожьте юниверс.
  3. Все оставшиеся вселенные теперь отсортированы [включая ту, в которой вы находитесь].

(Источник: http://catb.org/~esr/jargon/html/B/bogo-sort.html )

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

Однако в большинстве случаев мы, вероятно, не хотим рисковать тем, что множественные миры могут быть неправильными, не говоря уже о том, что действие по осуществлению шага 2 все еще «оставлено в качестве упражнения для читателя».

TheHansinator
источник
7

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

Дмитрий Рубанович
источник
6

В ситуации реального времени, когда вам нужна четкая верхняя граница, вы должны выбрать, например, heapsort, а не Quicksort, потому что среднее поведение heapsort также является его худшим вариантом.

Маркиз Лорн
источник
6

Добавление к и без того хорошим ответам. Практическим примером могут служить хэш-индексы и индексы B-дерева в базе данных postgres.

Хеш-индексы образуют хеш-таблицу для доступа к данным на диске, в то время как btree, как следует из названия, использует структуру данных Btree.

В Big-O это O (1) против O (logN).

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

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

Madusudanan
источник
4

Когда nмало и O(1)постоянно медленно.

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

или

  1. Когда требования к памяти или другим ресурсам, отличным от времени, в алгоритме O (1) исключительно велики по сравнению с алгоритмом O (log n).
Джоэл Коухорн
источник
3
  1. при перепроектировании программы выясняется, что процедура оптимизируется с помощью O (1) вместо O (lgN), но если это не является узким местом этой программы, и трудно понять O (1) alg. Тогда вам не придется использовать алгоритм O (1)
  2. когда O (1) требуется много памяти, которую вы не можете предоставить, тогда как время O (lgN) может быть принято.
yanghaogn
источник
1

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

Вот несколько примеров из головы.

  • Хеширование паролей иногда выполняется произвольно медленно, чтобы было сложнее угадывать пароли методом грубой силы. В этом посте по информационной безопасности есть пуля (и многое другое).
  • Bit Coin использует контролируемую медленную задачу, которую сеть компьютеров решает, чтобы «добыть» монеты. Это позволяет коллективной системе добывать валюту по контролируемому курсу.
  • Асимметричные шифры (такие как RSA ) предназначены для преднамеренно медленной расшифровки без ключей, чтобы предотвратить взлом шифрования кем-либо еще без секретного ключа. Алгоритмы предназначены для взлома во O(2^n)время, которое, мы надеемся, nбудет битовой длиной ключа (это грубая сила).

В других местах в CS быстрая сортировка O(n^2)в худшем случае, но в общем случае O(n*log(n)). По этой причине анализ Big O иногда не является единственной вещью, о которой вы заботитесь при анализе эффективности алгоритма.

Фрэнк Брайс
источник