O (n log n) vs O (n) - практические различия во временной сложности

Ответ 1

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

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

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

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

Ответ 2

Это зависит.

Я работал на amazon, был метод, который выполнял линейный поиск в списке. Мы могли бы использовать Hashtable и искать в O (1) по сравнению с O (n).

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

Однако, если вход большой, тогда это будет иметь значение.

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

Всегда хорошо знать ваши варианты и как вы можете оптимизировать.

Ответ 3

Бывают случаи, когда вы будете работать с миллиардами элементов (и более), где это различие, безусловно, будет значительным.

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

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

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

Ответ 4

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

Таким образом, у вас могут быть два алгоритма, один из которых - O (n), а один из них - O (nlogn), а для каждого значения - до количества атомов во Вселенной и за ее пределами (до некоторого конечного значения n), алгоритм O (nlogn) превосходит алгоритм O (n). Это может быть потому, что доминируют члены более низкого порядка, или это может быть из-за того, что в среднем случае алгоритм O (nlogn) является фактически O (n) или потому, что фактическое количество шагов составляет примерно 5 000 000 n против 3nlogn.

Ответ 5

PriorityQueue Сортирует каждый элемент, который вы добавляете каждый раз при использовании Collections.sort(), сортирует все элементы за один раз. Но если у вас есть проблема, когда вы хотите как можно скорее получить самый большой элемент, используйте PriorityQueue, если вам нужно выполнить некоторые вычисления, но требует сортировки элемента, а затем использовать ArrayList с коллекциями. Сорт лучше