База для программиста, часть 5: алгоритмы и структуры данных, которые реально нужны новичку

Для старта в программировании нужен небольшой набор: списки, словари и множества, понимание того, как растёт время работы программы с ростом данных, и умение выбрать подходящую структуру. Красно-чёрные деревья, динамическое программирование и сложные графовые алгоритмы подождут до собеседований или специализации. Ниже разберём, что нужно знать сейчас, с замерами на Python, которые вы можете повторить у себя.

Это пятая часть серии «База для программиста». В части 4 мы разобрали Git. Здесь появится код на Python, но читать его можно и без знания языка: мы разберём каждую строку.

Что нужно на старте, а что можно отложить

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

Что такое алгоритм и структура данных

• Алгоритм — последовательность шагов, решающая задачу. Рецепт борща — алгоритм.
• Структура данных — способ хранить данные так, чтобы с ними было удобно работать. Список покупок и картотека с алфавитными разделителями — разные структуры, и в каждой по-своему удобно искать нужное.

Выбор структуры влияет на скорость не меньше, чем сам алгоритм. Дальше мы увидим на цифрах, насколько.

Структуры данных, которые нужны с первого дня

Список (массив). Упорядоченная последовательность элементов. В Python это list.

fruits = ["яблоко", "груша", "слива"]
fruits.append("вишня")      # добавить в конец
print(fruits[0])            # первый элемент: яблоко

Доступ по номеру быстрый. А вот чтобы проверить, есть ли в списке нужный элемент, Python в худшем случае просмотрит весь список.

Словарь. Набор пар «ключ → значение». Находит значение по ключу практически мгновенно, не перебирая все элементы.

text = "кот пёс кот рыба пёс кот"
counts = {}
for word in text.split():
    counts[word] = counts.get(word, 0) + 1
print(counts)

{'кот': 3, 'пёс': 2, 'рыба': 1}

Это классический приём: посчитать, сколько раз что-то встречается. Он нужен постоянно.

Множество. Набор уникальных элементов, в котором очень быстро проверять, есть ли элемент внутри. Если вам нужно только знать «есть или нет» и порядок не важен, используйте множество.

Стек и очередь. Стек работает по принципу «последним пришёл — первым вышел» (стопка тарелок). Очередь — «первым пришёл — первым вышел».

from collections import deque

stack = ["a", "b", "c"]
print(stack.pop())          # c

queue = deque(["a", "b", "c"])
print(queue.popleft())      # a

Для очереди используют deque, потому что list.pop(0) вынуждает Python сдвигать все оставшиеся элементы, и на больших данных это медленно.

Сложность алгоритма на пальцах

Программисты оценивают алгоритм не секундами, а тем, как растёт число шагов, когда данных становится больше. Это записывают как O(…) и читают «о большое от…».

• O(1) — число шагов не зависит от размера данных. Пример: взять элемент списка по номеру, найти значение в словаре.
• O(log n) — данные выросли в тысячу раз, шагов стало больше всего на десяток. Пример: бинарный поиск.
• O(n) — шагов столько же, сколько данных. Пример: перебрать весь список в поисках элемента.
• O(n²) — шагов столько же, сколько данных в квадрате. Пример: цикл внутри цикла по одним и тем же данным.

Для 10 элементов разница незаметна. Для миллиона она решает, ответит программа за секунду или будет работать часами.

Проверим на практике: список против множества

Теория становится понятной на цифрах. Я запустил на Python 3.12.3 простой тест: есть миллион чисел, нужно проверить, есть ли среди них число, которого там нет (худший случай, придётся просмотреть всё). Один и тот же набор хранится и в списке, и в множестве.

import timeit

N = 1_000_000
data_list = list(range(N))
data_set = set(data_list)
missing = -1

t_list = timeit.timeit(lambda: missing in data_list, number=20) / 20
t_set = timeit.timeit(lambda: missing in data_set, number=20000) / 20000
print(f"list: {t_list*1000:.3f} ms, set: {t_set*1e6:.3f} us")

Результат в моём окружении:

list: 11.673 ms, set: 0.073 us, ratio: 160,860x

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

Практический вывод: если вы проверяете «есть ли элемент» много раз, превратите список в множество или словарь. Это один из самых частых и самых дешёвых способов ускорить программу.

Линейный и бинарный поиск

Линейный поиск — просто перебираем элементы по порядку, пока не найдём нужный. В худшем случае нужно просмотреть всё.

def linear_search(arr, x):
    for i, value in enumerate(arr):
        if value == x:
            return i
    return -1

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

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

Я подсчитал шаги для поиска последнего элемента в отсортированном списке из миллиона чисел:

linear steps: 1,000,000
binary steps: 20

Один миллион шагов против двадцати. В реальной работе вам редко придётся писать бинарный поиск самому: в Python для этого есть модуль bisect, а многие базы данных используют те же идеи. Но понимание, почему деление пополам даёт такой выигрыш, пригодится в других задачах.

Цикл в цикле: как появляется O(n²)

Когда один цикл вложен в другой по одним и тем же данным, число операций растёт как квадрат:

def pairs(n):
    count = 0
    for i in range(n):
        for j in range(n):
            count += 1
    return count

Замеры:

n=   10:       100 ops, 0.01 ms
n=  100:    10,000 ops, 0.24 ms
n= 1000: 1,000,000 ops, 32.08 ms

Данных стало в сто раз больше (с 10 до 1000), а работы в десять тысяч раз. Если вы видите вложенные циклы по большим данным, это сигнал: возможно, их можно заменить словарём или множеством.

Сортировка: что нужно знать новичку

Алгоритмы сортировки (пузырьком, вставками, быстрая, слиянием) стоит понять один раз, чтобы увидеть, что есть и медленные, и быстрые способы. Но в реальных проектах вы почти всегда используете встроенную сортировку:

numbers = [5, 2, 9, 1]
print(sorted(numbers))      # [1, 2, 5, 9]

Встроенная сортировка в Python быстрая: её время растёт как O(n log n), то есть заметно лучше, чем у «наивных» методов с вложенными циклами. Писать свою сортировку для работы не нужно, а вот объяснить идею быстрой сортировки или сортировки слиянием на собеседовании могут попросить.

Что можно не учить на старте

• Красно-чёрные деревья, B-деревья, сбалансированные деревья «изнутри».
• Динамическое программирование и сложные графовые алгоритмы.
• Реализацию хеш-таблицы с нуля.

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

Как учить, чтобы это работало

1. Измеряйте. Любое утверждение вроде «словарь быстрее списка» проверяйте на своём компьютере, как мы сделали выше. Привычка проверять ценнее, чем знание таблиц.
2. Решайте небольшие задачи. Подходят площадки с учебными задачами: LeetCode, Codewars, Яндекс Контест. Начинайте с лёгких, цель — понять, какую структуру выбрать, а не набрать очки.
3. Разбирайте решения. После своего варианта посмотрите чужой и сравните: почему он быстрее или проще.
4. Возвращайтесь через время. Идея запоминается, когда вы применяете её в проекте, а не когда читаете определение.

Типичные ошибки новичков

• Учить сортировки наизусть и не понимать, где они нужны. Сначала задачи, потом теория.
• Проверять in по огромному списку в цикле. Одна из самых частых причин, почему программа тормозит.
• Использовать list.pop(0) как очередь. Каждое такое удаление сдвигает весь список. Берите deque.
• Применять бинарный поиск к неотсортированным данным. Он тогда просто ничего не найдёт или найдёт случайно.
• Оптимизировать раньше времени. Если данных мало, разница незаметна, и ясный код важнее быстрого. Оптимизируйте там, где измерили проблему.

Мини-упражнение

1. Создайте список из 100 000 чисел и множество из тех же чисел.
2. Проверьте с помощью timeit, сколько занимает -1 in список и -1 in множество. Запишите оба результата.
3. Увеличьте размер данных в 10 раз и повторите замер. Что изменилось у списка и что у множества?
4. Напишите функцию, которая считает, сколько раз каждое слово встречается в предложении, с помощью словаря.
5. Перепишите поиск дубликатов в списке с помощью множества вместо вложенных циклов и сравните время.

Если во втором пункте время списка выросло примерно в 10 раз, а множества почти не изменилось, вы увидели на практике, что такое O(n) и O(1).

Что дальше

Когда понятно, как хранить данные и оценивать скорость, остаётся научиться искать ответы и разбираться в чужом коде. Об этом следующая часть серии: про чтение документации. <!-- добавить ссылку на часть 6 после публикации -->

Если вы подбираете курс по программированию или аналитике, программы собраны в каталоге MAXCOURSE. Все части серии доступны по тегу baza-programmista.

Частые вопросы

Нужно ли знать алгоритмы, чтобы стать программистом?
Базовые понятия нужны: структуры данных, оценка скорости, умение выбрать подходящий вариант. Сложные алгоритмы чаще требуются на собеседованиях и в узких специализациях, и их можно изучать позже.

Что такое O большое простыми словами?
Это способ описать, как растёт время работы программы при росте данных. Он не говорит, сколько секунд займёт работа, а показывает, насколько быстро эта цифра увеличивается.

Нужна ли математика, чтобы разбираться в алгоритмах?
Для базового уровня хватает школьной арифметики и понимания степеней. Глубокая математика нужна для узких областей: машинного обучения, криптографии, олимпиадного программирования.

Чем список отличается от массива?
В разных языках слова употребляют по-разному. В Python list — это динамический массив: его размер можно менять, а элементы хранятся в порядке добавления. В языках вроде C или Java массив обычно имеет фиксированную длину.

С какого языка начинать изучать алгоритмы?
С того, который вы уже учите. Python удобен тем, что меньше отвлекает синтаксисом, но идеи алгоритмов одинаковы для всех языков.

Проверено: Python 3.12.3. Замеры времени выполнены в тестовом окружении, на вашем компьютере цифры будут другими.