Структуры данных и сложность операций Flashcards
Массив.
Получение элемента по индексу - O[1]
Вставка - O[N] - то же самое - нужно передвинуть часть элементов
Удаление - O[N]- нужно сшифтить все элементы чтобы заполнить пустое место
Поиск в несортированном - O[N]
Поиск в сортированном - O[logN]
Что такое сложность операций?
Это функция, показывающая как растёт время выполнения программы в зависимости от количества входных элементов.
Он используется для оценки верхней границы (наихудшего случая), временной сложности алгоритма.
Стек
LIFO
Получение элемента по индексу - O(N)
Вставка - O(1) - добавление всегда в конец (push)
Удаление - O(1) - удаление всегда с конца (pop)
Поиск - O(N)
Односвязный список
Получение элемента по индексу - O(N) - нужно пройти весь список
Вставка - O(1) - вставка в начало/конец
Удаление - O(N) - поиск узла занимает O(N), затем удаление O(1)
Поиск - O(N)
Очередь
FIFO
Получение элемента по индексу - O(N)
Вставка - O(1) - добавление в конец
Удаление - O(1) - удаление из начала
Поиск - O(N)
Двусвязный список
Получение элемента по индексу - O(N)
Вставка - O(1) - добавление в начало/конец
Удаление - O(1) - если известен узел, иначе O(N) на поиск
Поиск - O(N)
B-дерево
Получение элемента по индексу - O(N)
Вставка - O(N) - если дерево несбалансированное
Удаление - O(N) - если дерево несбалансированное
Поиск - O(N) - в худшем случае
AVL дерево
Получение элемента по индексу - O(log N)
Вставка - O(log N) - за счёт балансировки
Удаление - O(log N) - поддерживается балансировка
Поиск - O(log N)
Красно-чёрное дерево
Получение элемента по индексу - O(log N)
Вставка - O(log N) - за счёт балансировки
Удаление - O(log N) - поддерживается балансировка
Поиск - O(log N)
Хэш-таблица
Получение элемента по индексу - O(N) - в худшем случае (при коллизиях). Т.е. если всё будет лежать в одном бакете
Вставка - O(N) - в худшем случае из-за коллизий
Удаление - O(N) - в худшем случае при высокой заполненности таблицы
Поиск - O(N) - если много коллизий, иначе O(1) в среднем
