Почему это решение O (n ^ 2) работает быстрее, чем решение O (n)?

редактировать: Извините! Похоже, я небрежно скопировал тот же код.

Вопрос:

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

то есть ввод [0, 1, 3, 4, 5] должен возвращать 2.

Я нашел два решения, одно, я думаю, за O (n), а другое за (On ^ 2).

Решение O(n)

def alt_find_missing(input_list):
    input_sum = sum(input_list)
    range_sum = sum([i for i in range(min(input_list), max(input_list)+1)])
    return range_sum - input_sum

Решение O(n^2)

def find_missing(input_list):
    input_set = set(input_list)
    for i in range(min(input_list), max(input_list)+1):
        if i not in input_set:
            return i

Однако решения O(n^2) работают быстрее, чем O(n) в нескольких timeit тестах:

List with 4 elements, using for ... in set (x 1 000 000)
1.1550223514080038
List with 4 elements, using difference of sums (x 1 000 000)
1.391524411772641
List with 100 elements, using for ... in set (x 1 000 000)
8.43574248785071
List with 100 elements, using difference of sums (x 1 000 000)
8.94695660741872
List with 1000 elements, using for ... in set (x 100 000)
8.1138781071155
List with 1000 elements, using difference of sums (x 100 000)
8.383110816298519

Почему это?


python set performance algorithm timeit
person ning    schedule 12.01.2017    source источник
comment
Я думаю, что вы получили свой титул задом наперед.   -  person user2357112 supports Monica    schedule 12.01.2017
comment
Ваши две функции выглядят одинаково для меня.   -  person user2357112 supports Monica    schedule 12.01.2017
comment
Не уверен, для чего нужен список композиций, когда вы также можете сделать sum(range(min(input_list), max(input_list)+1)), поскольку проблема гласит, что диапазоны от 0 to N - 1 вы можете просто иметь sum(range(max(input_list)+1))   -  person Steven Summers    schedule 12.01.2017
comment
Кроме того, сумма чисел до n равна n^2/2 + n/2.   -  person Klaus D.    schedule 12.01.2017
comment
поскольку функции одинаковы, единственное, о чем я могу думать, это то, что второй запуск использует преимущества значений CACHE... если это так, то увеличение набора данных до действительно большого набора (не вписывающегося в CACHE) или аннулирование кеша с помощью различные данные перед каждым запуском уравняют время выполнения.   -  person Spektre    schedule 12.01.2017
comment
Я не знаю, почему за это проголосовали. Я думаю, что вопрос поставлен правильно, и вы немного подумали, +1 от меня. Я хотел бы увидеть ваш набор кода решения. И комментарий от Клауса Д. великолепен.   -  person lhk    schedule 12.01.2017
comment
Вы используете Python 2 или Python 3? Если вы используете Python 2, вам следует изменить range() на xrange(), потому что range() создает список. Вы также создаете список и отбрасываете его (после использования для вычисления суммы) с пониманием списка. Было бы полезно, если бы вы предоставили более подробную информацию о примере O (n ^ 2). Ваш набор данных может быть настолько мал, что накладные расходы на некоторые из ваших операций снижают производительность решения O (n). И имейте в виду, что O(n) означает, что оно всегда будет превосходить решение O(n^2), так как по мере того, как дела становятся большими, оно в конечном итоге будет работать лучше.   -  person John Szakmeister    schedule 12.01.2017
comment
Всем привет! Извините за этот дубликат. Я только что исправил это, надеюсь, что это может прояснить некоторые вещи.   -  person ning    schedule 13.01.2017

Ответы (1)


arrow_upward
2
arrow_downward

Второй алгоритм не O (n ^ 2). Поиск набора — O(1), а повторение набора — O(n). Таким образом, разница между двумя алгоритмами связана с разными постоянными факторами.

Вот короткий скрипт, который показывает линейное поведение обеих функций

import timeit
from functools import partial
from matplotlib import pyplot as plt

def alt_find_missing(input_list):
    input_sum = sum(input_list)
    range_sum = sum([i for i in range(min(input_list), max(input_list)+1)])
    return range_sum - input_sum


def find_missing(input_list):
    input_set = set(input_list)
    for i in range(min(input_list), max(input_list)+1):
        if i not in input_set:
            return i


t1=[]
t2=[]

rng=range(10000,1000000,10000)

for n in rng:
    func1=partial(find_missing,range(n))
    func2=partial(alt_find_missing,range(n))
    t1.append(timeit.timeit(func1,number=5))
    t2.append(timeit.timeit(func2,number=5)) 

plt.plot(rng,t1, label='Find missing')
plt.plot(rng,t2, label='Alt find missing')
plt.ylabel('Execution time')
plt.xlabel('Problem size')
plt.legend()
plt.show()

Результат кажется мне довольно линейным :) Конечно, при некоторых размерах задач происходит что-то странное, но ничего, что значительно выбрасывало бы результаты из зоны линейности.

С Уважением. Две линейные функции

person Dennis Sakva    schedule 12.01.2017
comment
Набор поисковых запросов составляет O (1) в лучшем случае и O (n) в худшем случае. С одной стороны у вас есть создание набора n * (O (1).. O (n)) и его доступ n * (O (1).. O (n)). С другой стороны у вас есть n-список и его цикл FOR (O(n)). Таким образом, в худшем случае это может составить O (n ^ 2). - person cosmin; 12.01.2017
comment
Да, я заранее погуглил, чтобы проверить временную сложность поиска множества, в худшем случае кажется O(n): wiki.python.org/moin/TimeComplexity - person ning; 13.01.2017
comment
O (n) в худшем случае не делает алгоритм O (n) таким же, как O (n ^ 2) в худшем случае, сложность быстрой сортировки не делает его квадратичным. В Python наборы реализуются через хэш-таблицы, поэтому наибольшая временная сложность достигается, когда все ваши хэши сталкиваются. Что довольно маловероятно. - person Dennis Sakva; 13.01.2017