Сложность различных операций с различными структурами данных в соответствии с нотой Big-O

Question

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

http://bigocheatsheet.com/

Мои вопросы:

1. Если я хочу, чтобы удалить элемент в массиве, это O(n^2)? (поиск и удаление)
2. Если я хочу удалить элемент в стеке, это O(n)?
3. Какой из них более эффективен, является ли он одним связанным списком или двойным единственным списком?
4. В каком случае операция вставки равна O(1) или O(n) в хеш-таблице?
5. Если я хочу удалить элемент в двоичном дереве поиска, то это O(log(n)*log(n)), а вставка - только O(log(n))?

Спасибо.

Answer 1

Позвольте мне ответить на ваши вопросы:

1. Nope. Это O(n) + O(n) = O(n).
2. Нет, это O(1), но у вас только есть доступ к одному, очень сверху элемента. Для других элементов это O (n).
3. Двойной одиночный список будет не хуже, может быть быстрее, но требуется больше памяти для дополнительных ссылок.
4. Лучшее время - когда нет элемента с этим хешем, Хуже, когда все вставленные элементы имеют одинаковый хеш в соответствии с некоторым модулем. Например, если вы сравниваете по модулю 3 хэшей, и ваша хеширующая функция всегда возвращает число, которое составляет 3k для некоторого k, вы получите O(n).
5. Нет, согласно вашей таблице, это худший случай O (n).

Я объясню больше через минуту.

Answer 2

1. Когда вы выполняете одну операцию, а затем другую, вы не умножаете свою сложность - побеждает максимум. В этом случае O (n) + O (n) = O (n)
2. Имеет ли стек API-интерфейс «удалить произвольный элемент»? Если вы раскрываете базовую структуру данных, это совсем другое дело, но стек обычно имеет один способ «поп-элементов»
3. Какой прецедент?
4. Посмотрите, что происходит во время hash collisions.

Answer 3

1. Если вы хотите удалить элемент из массива, сначала вы должны искать его (берет O(n)), а затем вы должны переместить элементы, чтобы заполнить этот пробел (занимает O(n)). Таким образом, эффективная временная сложность составляет O(n).
2. Если вы хотите удалить элемент из стека, вы можете удалить только самый верхний элемент (свойство структуры данных стека).Таким образом, это можно сделать в O(1).
3. Какой тип связанного списка более эффективен, зависит от ваших требований. Например, если вы хотите сохранить память, вы можете не использовать двусвязные списки из-за накладных расходов на поддержание дополнительной ссылки указателя. Но, если вы хотите, чтобы вы проходили свой список в обоих направлениях, вам нужно использовать двусвязный список. Реализация двусвязного списка немного длинна, так как вам нужно выполнять больше операций с указателями, но многие операции (например, удаление последнего элемента) могут выполняться с легкостью.
4. Мы предпочитаем использовать таблицы Хэш, потому что мы можем достичь времени ввода и поиска O(1). O(n) Время ввода занимает почти все другие структуры данных. (O(n) класс включает O(log n), O(1) и т. Д.). Предположим, что мы используем separate chaining в хэш-таблице, где каждая цепочка является отсортированным связанным списком. Затем для каждой вставки нам нужно найти связанный список, чтобы найти нужную позицию для вставки (точно так же, как Sorting Sort), что приведет к худшему случаю O(n).
5. Если вам нужно удалить элемент из BST, сначала вы должны его искать (в среднем случае принимает O(log n)), а затем вы должны заменить удаленный узел своим преемником или предшественником (принимает O(log n)). Таким образом, эффективное время удаления среднего времени составляет O(log n).