Расчет сложности алгоритма (Big-O) - PullRequest
Новая
       10

Расчет сложности алгоритма (Big-O)

0 голосов
/ 14 апреля 2019

В настоящее время я работаю над сложностью Big-O и вычислением сложности алгоритмов.

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

Функция: 

index = 0
    while index < len(self.items):
        if self.items[index] == item:
            self.items.pop(index)
        else:
            index += 1

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

Моя проблема в том, что, насколько я думал, операторы присваивания и операторы if имеют сложность O (1), тогда как цикл while имеет сложность (n), а в худшем случае любые операторы внутри цикла while. мог выполнить n раз. Так что я работаю как 1 + n + 1 = 2 + n = O(n)

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

Любая помощь с этим очень ценится.

Ответы [ 3 ]

2 голосов
/ 14 апреля 2019

Если self.items является списком, операция pop имеет сложность "k", где k - индекс, так что это не O (N) только из-за операции pop.
Возможно, упражнение выполнено для того, чтобы вы использовали какой-то другой метод итерации и удаления из списка.

Чтобы сделать это O (N), вы можете сделать: 

self.items = [x for x in self.items if x == item]
1 голос
/ 14 апреля 2019

Без аргументов для всплытия его O (1)

С аргументом для всплытия:

  • Среднее время Сложность O (k) (k представляет число, переданное в видеаргумент для pop
  • Амортизированная временная сложность в наихудшем случае O (k)
  • Временная сложность в худшем случае O (n)

Сложность времени - Python Wiki

Чтобы сделать ваш код эффективным, позвольте пользователю всплыть в конце списка:

, например: 

def pop():
    list.pop(-1)

Ссылка

Поскольку вы передаете index на self.items.pop(index), это НЕ O (1).

1 голос
/ 14 апреля 2019

Если вы используете встроенную в Python структуру данных списка, операция pop() не является постоянной в худшем случае и составляет O(N).Таким образом, ваша общая сложность составляет O(N^2).Вам нужно будет использовать некоторую другую структуру данных, такую ​​как связанный список, если вы не можете использовать вспомогательное пространство.

...