Временная сложность путаницы

Question

Я всегда был немного смущен этим, возможно, из-за моего непонимания в компиляторах. Но позволяет использовать python в качестве примера. Если бы у нас был некоторый большой список чисел, называемый numlist, и мы хотели избавиться от любых дубликатов, мы могли бы использовать оператор set в списке, например set set (numlist). Взамен мы имели бы набор наших чисел. Эта операция, насколько мне известно, будет выполнена в O (n) времени. Хотя, если бы я должен был создать свой собственный алгоритм для обработки этой операции, самым лучшим, на что я мог бы надеяться, является O (n^2).

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

Answer 1

Вы можете сделать это в O (N) на любом языке, в основном, как:

# Get min and max values O(n). 

min = oldList[0] 
max = oldList[0] 
for i = 1 to oldList.size() - 1: 
    if oldList[i] < min: 
     min = oldList[i] 
    if oldList[i] > max: 
     max = oldList[i] 

# Initialise boolean list O(n) 

isInList = new boolean[max - min + 1] 
for i = min to max: 
    isInList[i] = false 

# Change booleans for values in old list O(n) 

for i = 0 to oldList.size() - 1: 
    isInList[oldList[i] - min] = true 

# Create new list from booleans O(n) (or O(1) based on integer range). 

newList = [] 
for i = min to max: 
    if isInList[i - min]: 
     newList.append (i) 

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

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

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

В крайнем примере вы можете использовать тот же метод внепространства для сортировки произвольного числа 32-разрядных целых чисел (например, каждый из которых имеет только 255 или менее дубликатов) в O (n) времени, при условии, что вы можете выделить около четырех миллиардов байтов для хранения счетчиков.

Просто инициализируйте все отсчеты до нуля и пройдите через каждую позицию в своем списке, увеличивая счет на основе числа в этой позиции. Это O (n).

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

Это тоже O (1) сложность пространства, но очень большая «1». Обычно компромиссы не так уж и серьезны.

Answer 2

Сложность связана алгоритма не имеет никакого отношения к ли он реализован «внутри» или «снаружи»

Answer 3

Off стороны, я не могу думать о том, как сделать это в O (N), но здесь прохладная вещь:

Разница между n^2 и n настолько велика, что разница между вами и реализацией python крошечная по сравнению с алгоритмом, используемым для ее реализации. n^2 всегда хуже, чем O (n), даже если n^2 находится в C, а O (n) - в python. Вы никогда не должны думать, что такая разница возникает из-за того, что вы не пишете на языке низкого уровня.

Это означает, что если вы хотите реализовать свои собственные, вы можете сделать сортировку, а затем удалить дубликаты. вид n * ln (n) и удаленные дубликаты в O (n) ...

Answer 4

Ввод списка и его включение в набор через set() - O (n).

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

Чтобы понять, как работает реализация хэш см artcle википедии на hash tables

Answer 5

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

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

Асимптотическая сложность алгоритма не изменяется, если она реализуется разработчиками языка и реализуется пользователем этого языка. Пока оба реализованы на полном языке Turing со случайными моделями памяти, у них одинаковые возможности и алгоритмы, реализованные в каждом, будут иметь одинаковую асимптотическую сложность. Если алгоритм теоретически O(f(n)) не имеет значения, будет ли он реализован на языке ассемблера, C# или Python на нем все равно будет O(f(n)).

Answer 6

Здесь есть две проблемы.

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

Фактическая скорость (скажем, в миллисекундах) алгоритма - это временная сложность, умноженная на константу (в идеальном мире).

Два человека могут реализовать одинаковое удаление алгоритма дубликатов с сложностью O (log (n) * n), но если записать его на Python, а другой записать в оптимизированном C, программа C будет быстрее.