Каковы наиболее распространенные структуры данных и Big O для операций с ними?

Question

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

Data Structure       Big O Search   Big O Insert
Array                    O(1)          O(n)
Hash                     O(1)          O(1)
Single Linked List       O(n)          O(1)
Double Linked List       O(n)          O(1)
Tree                   O(log n)      O(log n)

Answer 1

Для массива, чтобы получить / вернуть элемент, требуется O (1), но для поиска элемента нужно O (n). Для дерева я предполагаю, что вы имели в виду сбалансированное дерево двоичного поиска.

Answer 2

Для хеш-вставок помните, что O (1) является оптимальным. Если ваша хеш-таблица близка к полной, ваша эффективность приблизится к O (n).

Кроме того, для отсортированного массива поиск выполняется O (log n).