Что это за сложность?

Question

Мне была дана небольшая и простая функция для рефакторинга в функцию сложности O (n). Тем не менее, я считаю, что данная функция уже есть, если я что-то упустил?

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

for i in self.items:
        if i == item:
            self.items.pop(i)

Я знаю, что цикл for придает этому сложность O (n), но добавляет ли дополнительный оператор if усложнение? Я не думал, что это будет в худшем случае для этого простого куска кода.

Если это так, есть ли способ, которым это может быть переписано, чтобы быть O (n)?

Я не могу придумать другой способ перебора списка и удаления элемента без использования цикла For, а затем с помощью оператора if для сравнения?

PS. self.items представляет собой список слов

Answer 1

Метод list.pop имеет среднюю и наихудшую временную сложность O (n) , поэтому в сочетании с циклом он делает код O (n ^ 2) в сложность времени.

И, как @juanpa.arrivillaga уже указывал в комментариях, вместо этого вы можете использовать понимание списка, чтобы отфильтровать элементы с определенным значением в O (n) сложность времени:

self.items = [i for i in self.items if i != item]

Answer 2

for i in self.items: # grows with the cardinal n of self.items
    if i == item:
        self.items.pop(i) # grows with the cardinal n of self.items

Итак, у вас сложность O(n²).

Метод list remove(item) в Python имеет сложность O(n), поэтому вы бы предпочли использовать его.

self.items.remove(item)

Answer 3

Во-первых, вам нужно немного изменить свой код. Аргумент, заданный для pop(), в настоящее время является элементом, где он должен быть индексом (используйте remove(), чтобы удалить первое вхождение элемента).

for i, item in enumerate(self.items):
        if item == target:
            self.items.pop(i)

Сложность зависит от того, как часто item соответствует элементу в вашем списке.

Используя n=len(items) и k для количества совпадений, сложность составляет O(n, k) = O(n) + k O(n). Первое слагаемое происходит из-за того, что мы перебираем весь список, второе соответствует отдельным .pop(i) операциям.

Таким образом, общая сложность для k=1 просто равна O(n) и может возрасти до O(n*n) для k=n.

Обратите внимание, что сложность для .pop(i) составляет O(n-i). Следовательно, выталкивание первого и последнего элемента равно O(n) и O(1) соответственно.

Наконец, я бы вообще рекомендовал не добавлять / удалять элементы к объекту, который вы сейчас просматриваете.

Answer 4

Ваше текущее решение имеет временную сложность O (n ^ 2).

Для решения O (n) вы можете просто использовать, например, понимание списка, чтобы отфильтровать все ненужные элементы из списка:

self.items = [i for i in self.items if i != item]