Вопросы относительно кода в книге «Структуры данных и алгоритмы»

Question

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

1. Это тот случай, когда они объясняют логику добавления элемента по определенному индексу в списке. Я понимаю логику, это довольно просто. Переместите все элементы, начиная с самого правого, одного индекса вправо, чтобы освободить место для элемента в индексе. Код для этого в книге дан:

   for j in range(self._n, k, −1): self._A[j] = self._A[j−1]

   То, что я не получаю, это диапазон цикла. Технически, self._n эквивалентно len(list) (внутреннее состояние, поддерживаемое списком). И если вы начинаете с len(list), вы сразу же начинаете с IndexOutOfBoundError. Во-вторых, даже если это не так, цикл заменяет n на n-1. Нигде он фактически не перемещается n в n+1 первым, так что значение теряется. Я что-то здесь упускаю? Я действительно опробовал эти условия на интерпретаторе Python, и они, кажется, подтверждают мое понимание.

2. Некоторые анализы времени выполнения для операций со списками меня смущают. Например: data.index(value) --> O(k+1) value in data --> O(k+1) data1 == data2 (similarly !=, <, <=, >, >=) --> O(k+1) data[j:k] --> O(k−j+1)

   Я не понимаю, почему +1 в конце каждого анализа времени выполнения. Давайте рассмотрим операцию data.index(value), которая в основном возвращает первый индекс, по которому найдено определенное значение. В худшем случае он должен выполнять итерацию по всем n элементам списка, но если нет, если поиск находит что-то по индексу k, он возвращается оттуда. Почему O(k+1) там? Та же логика применима и к другим случаям, особенно к разрезанию списка. Когда вы нарезаете список, разве это не просто O(k-j)? Напротив, фактические показатели от j до k-1.

Это понимание должно быть довольно элементарным, и я действительно чувствую себя глупо, не в состоянии понять это. Или я не знаю, есть ли в книге подлинные ошибки, и я правильно понимаю. Может ли кто-нибудь уточнить это для меня? Помощь очень ценится.

Answer 1

Примечание (из комментариев): книга, о которой идет речь, Структуры данных и алгоритмы на Python Гудрича, Тамассии и Гольдвассера , и вопросы о страницах с 202 по 204.

Если вы посмотрите на полное определение insert из книги, это имеет больше смысла.

def insert(self, k, value):
    if self.n == self.capacity:
        self.resize(2 * self.capacity)

    for j in range(self.n, k, −1):
        self.A[j] = self.A[j−1]

    self.A[k] = value
    self.n += 1

Первая строка подразумевает, что self.n - это количество элементов и соответствует индексу за концом, что означает, что для пользователя списка доступ к нему по этому индексу будет ошибочным. Но этот код принадлежит списку, и поскольку он имеет емкость в дополнение к размеру, он может использовать self.A[n], если self.n < self.capacity (что верно при запуске цикла for).

Цикл просто перемещает последний элемент (с индексом n-1) к следующему пространству в памяти, которое выходит за пределы для пользователя, но не для внутреннего использования. В конце n увеличивается, чтобы отразить новый размер, а n-1 становится индексом того «следующего пространства в памяти», которое теперь содержит последний элемент.

Что касается временной сложности различных операций: ну, они не являются неправильными. Даже если O(n+1) = O(n), вы все равно можете написать O(n+1), если хотите, и в некоторых случаях это может быть более "точным".

Например, написано, что data.index(value) имеет сложность O(k+1), с k индексом искомого значения. Ну, если это значение в самом начале, тогда k = 0, а сложность O(0+1) = O(1). И это правда: если вы всегда ищете значение, которое, как вы знаете, находится в самом начале, даже если эта операция бессмысленна, она имеет постоянную сложность по времени. Если бы вы изначально написали O(k) вместо этого, то вы бы получили O(0) за эту последнюю операцию, которую я никогда не видел, но я бы подумал, что операция мгновенная.

То же самое происходит с нарезкой: они, вероятно, написали O(k−j+1), потому что если вы берете только один элемент, то j = k и сложность составляет O(1) вместо O(0).

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

Answer 2

В первом случае, я думаю, предполагается, что у вас есть список фиксированной максимальной длины, и вы должны потерять последний пункт данных. Кроме того, вы уверены, что self._n == len(n) а не self._n == len(n)-1?

Во втором случае, насколько я понимаю, O (k + 1) совпадает с O (k), поэтому не имеет смысла говорить O (k + 1). Но опять же, если мы действительно хотим знать, как кто-то может считать до k + 1 ... Я думаю, этот парень считает, начиная с 0. Так что для перехода с 0-го на k-й индекс потребуется k + 1 операций.

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