Алгоритмы и структуры данных — мысли как программист

1. Зачем разработчику алгоритмы

Алгоритм — просто пошаговая инструкция для решения задачи. Их не учат ради экзамена: понимание сложности помогает не писать программы, которые «зависают» на больших данных, и заметить, что решение можно ускорить в тысячи раз.

// простейший алгоритм: найти максимум в списке
def max_value(items):
    best = items[0]
    for x in items:
        if x > best:
            best = x
    return best      # перебрали все — n шагов

2. Оценка сложности O(n)

«O большое» описывает, как растёт время (или память) с ростом входных данных. Говорим не про секунды, а про порядок роста:

O(1)      — всегда одно действие     # взять arr[5]
O(log n)  — растёт очень медленно    # бинарный поиск
O(n)      — линейно, n операций      # перебор по списку
O(n log n)— «хорошие» сортировки     # merge sort
O(n^2)    — квадратично, опасно      # вложенные циклы
O(2^n)    — экспонента, почти всегда тупик

3. Массивы и списки

Массив (в Python — список) хранит элементы подряд, поэтому доступ по индексу мгновенный — O(1). Но вставка или удаление в середине требует сдвига элементов — O(n).

arr = [10, 20, 30, 40]

arr[0]            # 10 — O(1), адрес считается по индексу
arr.append(50)    # в конец — обычно O(1)
arr.insert(1, 15) # 15 в середину — сдвигаем хвост, O(n)
arr.remove(30)    # ищем и сдвигаем, O(n)

• массив требует сплошной кусок памяти;
• связанный список хранит элементы в разных местах и связывает ссылками;
• в связанном списке вставка в середину — O(1), но поиск по номеру — O(n).

4. Стек и очередь

Стек работает по принципу LIFO — последним зашёл, первым вышел. Очередь — FIFO: первым пришёл, первым ушёл. Это две самые полезные «наивные» структуры.

// стек (Python: список)
stack = []
stack.append("a")   # push
stack.append("b")
stack.pop()         # вернёт "b" — последний

// очередь (FIFO)
from collections import deque
q = deque()
q.append("task1")   # в конец
q.popleft()         # из начала: "task1"

5. Хеш-таблицы

Хеш-таблица (в Python — dict, в JS — Map/объект) хранит пары «ключ — значение» и находит значение по ключу за O(1). Ради неё и стоит дружить с алгоритмами.

phones = {}
phones["anna"] = "8-900-111-22-33"
phones["petr"] = "8-900-444-55-66"

"anna" in phones        # True — O(1)
phones.get("oleg")      # None

# классика: посчитать частоту слов
count = {}
for w in words:
    count[w] = count.get(w, 0) + 1

• ключ превращается в число хеш-функцией, а оно — в ячейку массива;
• коллизии (два ключа в одну ячейку) решаются цепочками;
• в худшем случае — O(n), на практике почти всегда O(1).

// замена вложенного цикла хеш-таблицей
// было O(n^2):
for a in list1:
    for b in list2:
        if a == b: ...

// стало O(n):
set2 = set(list2)
for a in list1:
    if a in set2: ...

6. Деревья и графы

Дерево — иерархическая структура «родитель → потомки». Граф — произвольные связи между узлами. Деревья в коде встречаются чаще, чем кажется: DOM-дерево, меню, структура каталогов.

class Node:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

// двоичное дерево поиска
root = Node(50)
root.left  = Node(30)
root.right = Node(70)

// обход в глубину (DFS) — рекурсивно
def walk(node):
    if node is None:
        return
    walk(node.left)
    print(node.value)
    walk(node.right)

7. Сортировки

Сортировка встречается везде: товары по цене, логи по дате. В языке она уже встроена (sorted(), arr.sort()), но принцип надо понимать, чтобы уметь делать «почти отсортированный» случай и отвечать на собеседованиях.

// пузырёк: простой, но O(n^2)
def bubble(a):
    for i in range(len(a)):
        for j in range(len(a) - i - 1):
            if a[j] > a[j + 1]:
                a[j], a[j + 1] = a[j + 1], a[j]

// встроенная сортировка — O(n log n)
sorted([3, 1, 2])   # [1, 2, 3]

8. Бинарный поиск

Если данные отсортированы, искать можно не перебором, а «вилкой»: посмотреть середину и отбросить половину. Получаем O(log n) вместо O(n).

// ищем x в отсортированном массиве
def binary_search(arr, x):
    lo, hi = 0, len(arr) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if arr[mid] == x:
            return mid
        if arr[mid] < x:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1

• требование: массив отсортирован по возрастанию;
• за 10 шагов находится элемент среди миллиона;
• ошибка «на единицу» (off-by-one) — самая частая при реализации, проверяйте на массивах из 1 и 2 элементов.

9. Рекурсия

Рекурсия — функция, которая вызывает саму себя с меньшей задачей. Обязательный базовый случай останавливает её. Классика — факториал, обход дерева, разбор выражений.

def factorial(n):
    # базовый случай — выход
    if n <= 1:
        return 1
    # рекурсивный случай
    return n * factorial(n - 1)

// каждый вызов живёт в стеке
factorial(3)
  → 3 * factorial(2)
    → 2 * factorial(1)
      → 1            # базовый случай
    → 2 * 1 = 2
  → 3 * 2 = 6

10. Динамическое программирование

Динамическое программирование (ДП) — решение задачи путём сохранения ответов для подзадач. Нужно, когда одни и те же подзадачи пересчитываются снова и снова.

// лестница: способов подняться на n ступеней,
// если можно шагать на 1 или 2 (числа Фибоначчи)
def ways(n):
    if n <= 2:
        return n
    a, b = 1, 2
    for _ in range(3, n + 1):
        a, b = b, a + b
    return b

ways(4)   # 5

11. Практика на Codewars и LeetCode

Теория закрепляется практикой. Планируйте по 15–30 минут в день, от лёгких задач к средним, и ведите учёт решённых.

// план на первые 4 недели
1-я неделя  — 8kyu/легкие: массивы, строки, циклы
2-я неделя  — хеш-таблицы, два указателя
3-я неделя  — стеки, очереди, рекурсия
4-я неделя  — бинарный поиск, сортировки, простые ДП

12. Поиск в ширину и поиск в глубину

Обход графа решает множество задач: поиск кратчайшего пути, связности, обход лабиринта. Два главных способа — BFS и DFS.

BFS (поиск в ширину) идёт «слоями» от стартового узла и находит кратчайший путь в невзвешенном графе. Реализуется через очередь.

from collections import deque
def bfs(graph, start):
    visited = set([start])
    queue = deque([start])
    while queue:
        node = queue.popleft()
        print(node)
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)   # порядок определяет «ширину»

DFS (в глубину) уходит вглубь ветки, пока возможно, затем отступает. Обычная реализация — рекурсия или явный стек.

def dfs(graph, node, visited=None):
    if visited is None:
        visited = set()
    visited.add(node)
    for neighbor in graph[node]:
        if neighbor not in visited:
            dfs(graph, neighbor, visited)   # углубляемся

13. Жадные алгоритмы

Жадные алгоритмы на каждом шаге берут «максимально выгодное» решение в надежде, что локальная выгода даст глобальный оптимум. Так работают выдача сдачи монетами, алгоритм Дейкстры, расписание по дедлайнам.

// жадно: набрать максимальное количество задач
def max_tasks(tasks):
    tasks.sort(key=lambda t: t[1])   # по времени окончания
    last_end = 0
    result = []
    for start, end in tasks:
        if start >= last_end:        # берём, если не пересекается
            result.append((start, end))
            last_end = end
    return result

14. Кучи и очередь с приоритетом

Очередь с приоритетом достаёт всегда «самый важный» элемент за O(log n). Встроенная структура — heap (куча): в Python это модуль heapq.

import heapq
tasks = []
heapq.heappush(tasks, (3, "низкий приоритет"))
heapq.heappush(tasks, (1, "срочно"))
heapq.heappush(tasks, (2, "обычный"))
while tasks:
    print(heapq.heappop(tasks))   # всегда минимальный приоритет

• куча находит минимум/максимум за O(1), вставка за O(log n);
• применяется: очередь задач, топ-K элементов, алгоритм Дейкстры;
• в Python heapq — это min-heap на обычном списке.

15. Проект: свой поиск по хешу

Соберём микросистему, которая использует почти всё из курса: индекс по хеш-таблице для быстрого поиска товаров.

products = {
    "p1": {"name": "Мышь", "price": 1200},
    "p2": {"name": "Клавиатура", "price": 3400},
}

def find(pid):
    item = products.get(pid)          # O(1) по ключу
    return item or "не найдено"

def top_by_price(limit=1):
    return sorted(products.values(),
                  key=lambda x: x["price"],
                  reverse=True)[:limit]   # O(n log n)

Реальная система сделает то же самое, но с миллионами ключей и индексами на диске. Принцип тот же: ключ → хеш → ячейка.

16. Два указателя и скользящее окно

Метод двух указателей и техника скользящего окна решают задачи, которые «в лоб» требуют O(n²), за один проход за O(n). Это must-have для собеседований.

# Два указателя: найти пару с заданной суммой
def two_sum_sorted(nums, target):
    l, r = 0, len(nums) - 1
    while l < r:
        s = nums[l] + nums[r]
        if s == target:
            return [l, r]
        if s < target:
            l += 1
        else:
            r -= 1
    return []

• два указателя: массивы «отсортированы» и двигаются навстречу;
• скользящее окно: фиксированная длина подмассива, «окно» сдвигается по решению;
• применения: поиск пар, треугольники, максимальная сумма подмассива K, уникальные символы;
• сложность — O(n), память — O(1).

17. Префиксные суммы

Префиксные суммы (prefix sum) позволяют отвечать на запрос «сумма на отрезке» за O(1) вместо O(n). Построение массива — O(n), а дальше любой диапазон считается одной формулой.

def prefix_sum(arr):
    pref = [0] * (len(arr) + 1)
    for i, x in enumerate(arr):
        pref[i + 1] = pref[i] + x
    return pref

def range_sum(pref, l, r):
    return pref[r + 1] - pref[l]

18. Графы: кратчайшие пути (Дейкстра)

Алгоритм Дейкстры находит кратчайшие пути от одной вершины до всех остальных в графе с неотрицательными рёбрами за O(E log V) с кучей. Это фундамент навигации, сетей и оптимизации маршрутов.

import heapq

def dijkstra(graph, start):
    dist = {v: float('inf') for v in graph}
    dist[start] = 0
    pq = [(0, start)]
    while pq:
        d, u = heapq.heappop(pq)
        if d > dist[u]:
            continue
        for v, w in graph[u]:
            nd = d + w
            if nd < dist[v]:
                dist[v] = nd
                heapq.heappush(pq, (nd, v))
    return dist

• с отрицательными весами Дейкстра не работает — используйте Беллмана-Форда;
• куча обеспечивает быстрый выбор ближайшей вершины;
• восстановление пути — через массив предыдущих вершин;
• применимо: карты, планирование, сети доставки.

19. Как готовиться к собеседованию

Алгоритмы на интервью — это не зубрёжка, а метод: читать условие, выбирать структуру, оценивать сложность и доводить рэшение до корректного кода. Тренируйтесь системно.

1. повторяйте базовые структуры: массив, хеш, стек, очередь, куча, дерево;
2. решайте задачи по категориям, а не подряд — так вы выработаете паттерны;
3. тренируйте «думать вслух»: собеседник хочет видеть ход мысли;
4. сначала набросайте brute force, затем оптимизируйте — так вы не утонете;
5. раз в неделю переписывайте ключевые алгоритмы по памяти.

План на 6 недель:
1-я: простые задачи, строки и хеши
2-я: скользящее окно и указатели
3-я: деревья и обходы
4-я: графы — Дейкстра и BFS
5-я: динамическое программирование
6-я: смешанный набор + выговоры времени

20. Битовые операции и их применение

Побитовые операторы работают быстрее арифметики и лежат в основе масок, кодирования и оптимизации. На собеседованиях они появляются в задачах про чётность, уникальные числа и флаги.

x & 1        // 1, если x нечётное
x >> 1       // деление на 2
x ^ x        // 0: XOR сам с собой
mask & (1<<i) // проверка i-го бита

• XOR-свойства (a ^ a = 0, a ^ 0 = a) решают задачи «найди уникальное»;
• выражение x & (-x) выделяет младший единичный бит — база BIT-деревьев;
• маски перебираются по 2^n вариантов в задачах о подмножествах;
• битовые операции выполняются за O(1) и экономят память.

21. Топологическая сортировка и сильно связанные компоненты

Направленные графы описывают зависимости: сборку модулей, порядок курсов, расписания. Топологическая сортировка задаёт порядок вершин без нарушений зависимостей, а алгоритмы типа Kosaraju находят сильно связанные компоненты.

1. топологический порядок существует только в ациклическом графе (DAG);
2. простой способ — DFS с добавлением вершин на выходе из рекурсии;
3. алгоритм Кана выводит первые вершины и ловит циклы по числу вершин;
4. компоненты сильной связности находятся за два обхода графа.

22. Строковые алгоритмы: префикс-функция и Z-функция

Поиск подстроки «в лоб» за O(n·m) не подходит для больших текстов. Префикс-функция и Z-функция находят совпадения за линейное время и служат основой многих строковых задач.

• префикс-функция pi[i] показывает длину собственного префикса-суффикса;
• алгоритм Кнута–Морриса–Пратта ищет подстроку за O(n + m);
• Z-функция считает длину наибольшего совпадения префикса с позиции i;
• обе функции применяются в редакторах, поиске и антиспаме.

23. Указатели и скользящее окно: расширения

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

• два указателя с двусторонним движением — задачи про суммы и пары;
• скользящее окно — максимум, минимум или количество подмассивов по условию;
• корректность: инвариант окна фиксируется перед каждым сдвигом;
• сложность O(n) при амортизированном движении каждого указателя.

Что дальше

Возьмите 2 задачи в день на Codewars и через месяц добавьте разбор типовых вопросов из Резюме и собеседования. Дальше углубитесь: хеш-таблицы и деревья пригодятся в SQL, а графы — в курсах по базам данных. Общий план развития — в Дорожной карте.

← Вернуться к курсам