Сложность базовых операций

Четыре основных операции

Любая структура данных поддерживает четыре базовые операции:

Операция	Описание
Поиск	Найти элемент по значению или ключу
Вставка	Добавить новый элемент
Удаление	Убрать элемент
Доступ	Получить элемент по позиции или ключу

Сравнение структур данных

Структура	Доступ	Поиск	Вставка	Удаление
Массив	`O(1)`	`O(n)`	`O(n)`	`O(n)`
Динамический массив	`O(1)`	`O(n)`	`O(1)`*	`O(n)`
Связный список	`O(n)`	`O(n)`	`O(1)`**	`O(1)`**
Хеш-таблица	—	`O(1)`	`O(1)`	`O(1)`
BST (сбал.)	`O(log n)`	`O(log n)`	`O(log n)`	`O(log n)`

* амортизированно; ** при наличии указателя на узел.

Важность выбора структуры

// Частый поиск по ключу → map
index := make(map[string]int)
index["alice"] = 42
v := index["alice"] // O(1)

// Частый доступ по позиции → slice
data := []int{10, 20, 30}
x := data[1] // O(1)

// Частые вставки/удаления в середину → list
import "container/list"
l := list.New()
e := l.PushBack(10)
l.InsertAfter(20, e) // O(1)

Амортизированная сложность

append к срезу — O(1) в среднем, но O(n) при перевыделении памяти. Амортизированная оценка усредняет стоимость по серии операций.

// Предвыделение избегает многократного копирования
s := make([]int, 0, 1000)
for i := 0; i < 1000; i++ {
    s = append(s, i) // ни одного перевыделения
}

Упражнения

№	Задание	Сложность
1	Упражнение 1	easy
2	Упражнение 2	easy
3	Упражнение 3	medium