Сложность перечисления

Я вижу много вопросов о сложности встроенных методов Python во время выполнения, и есть много ответов для многих методов (например, https://wiki.python.org/moin/TimeComplexity, https://www.ics.uci.edu/~pattis/ICS-33/лекции/complexitypython.txt , Стоимость функции len() и т. д.)

Что-то я не вижу ничего, что адреса перечислять. Я знаю, что он возвращает по крайней мере один новый массив (индексы), но сколько времени потребуется для его создания, и является ли другой массив исходным массивом?

Другими словами, я предполагаю, что это O (n) для создания нового массива (итерации) и O (1) для повторного использования исходного массива... всего O (n) (я думаю). Является ли другой O (n) для копии, делающей это O (n ^ 2), или что-то еще...?


python arrays enumerate time-complexity big-o
person 10'004    schedule 30.06.2015    source источник
comment
O (n ^ 2) будет означать O (n * n), а не O (n + n)   -  person Ryan Haining    schedule 30.06.2015
comment
enumerate возвращает объект перечисления, который является объектом итератора, а не списком, поэтому его сложность будет зависеть от того, как он используется.   -  person martineau    schedule 30.06.2015
comment
нет list.enumerate. Существует встроенная функция enumerate(), которая работает с произвольными итерируемыми объектами.   -  person jfs    schedule 01.07.2015

Ответы (3)


arrow_upward
8
arrow_downward

Предполагая наивный подход (enumerate дублирует массив, затем перебирает его), у вас есть время O (n) для дублирования массива, а затем время O (n) для его повторения. Если бы это было просто n вместо O(n), у вас было бы 2 * n всего времени, но это не то, как работает O(n); все, что вы знаете, это то, что количество времени, которое потребуется, будет некоторым кратным n. Это (в основном) то, что в любом случае означает O (n), поэтому в любом случае функция перечисления составляет O (n) общее время.

person Sam Estep    schedule 30.06.2015
comment
Как и в примере @caenyon, и учитывая, как люди часто используют перечисление, я предполагаю, что ситуация, подобная for i,v in enumerate(a), будет O (n + n + 1) и, следовательно, O (2n)? - person 10'004; 30.06.2015
comment
@10'004 Нет. В любой ситуации, когда доминирующий член сложности алгоритма является линейным (т. е. если время, затрачиваемое алгоритмом, кратно n), сложность составляет O(n ). Независимо от того, равно ли фактическое время 2n, 3n, 4n, 0,5n или любому кратному n, сложность всегда равна O(n). - person Sam Estep; 30.06.2015
comment
@ 10'004: enumerate() может работать с бесконечными генераторами и поэтому не копирует свой ввод. Хотя это не изменит временную сложность, даже если это произойдет (для конечного ввода). - person jfs; 01.07.2015

arrow_upward
18
arrow_downward

Функция перечисления возвращает итератор. Концепция итератора описана здесь.

В основном это означает, что итератор инициализируется, указывая на первый элемент списка, а затем возвращает следующий элемент списка каждый раз, когда вызывается его метод next().

Итак, сложность должна быть:

Инициализация: O(1)

Возврат следующего элемента: O(1)

Возврат всех элементов: n * O(1)

Обратите внимание, что перечисление НЕ создает новую структуру данных (список кортежей или что-то в этом роде)! Он просто перебирает существующий список, помня об индексе элемента.

Вы можете попробовать это сами:

# First, create a list containing a lot of entries:
# (O(n) - executing this line should take some noticeable time)
a = [str(i) for i in range(10000000)] # a = ["0", "1", ..., "9999999"]

# Then call the enumeration function for a.
# (O(1) - executes very fast because that's just the initialization of the iterator.)
b = enumeration(a)

# use the iterator
# (O(n) - retrieving the next element is O(1) and there are n elements in the list.)
for i in b:
    pass  # do nothing
person Felix    schedule 30.06.2015

arrow_upward
4
arrow_downward

Как указал Мартино, enumerate() не делает копию массива. Вместо этого он возвращает объект, который вы используете для перебора массива. Вызов самого enumerate() - это O (1).

person James    schedule 30.06.2015