Информатика · Алгоритмы

Алгоритмы
простым языком

Пошаговые инструкции, которые превращают хаос данных в порядок. Разбираемся с нуля — с примерами, кодом и без заумных формул.

Сортировка Поиск Рекурсия Big-O Структуры данных
Основа основ

Что такое алгоритм?

Это просто набор инструкций для решения задачи. Ты уже составлял алгоритмы — каждый раз, когда следовал рецепту или собирал мебель из ИКЕИ.

🍳
Аналогия с кухней

Рецепт яичницы — это алгоритм: 1) Разбить яйца. 2) Взболтать. 3) Вылить на сковородку. 4) Жарить 2 минуты. Компьютер делает то же самое, только с цифрами и в миллиарды раз быстрее.

🧭
Аналогия с навигатором

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

⏱️

Быстрый

Хороший алгоритм решает задачу за минимум шагов. Двоичный поиск на 1 млн элементов — всего 20 шагов.

✅

Правильный

Алгоритм должен давать верный результат всегда. Не «иногда», не «в целом» — каждый раз.

🔄

Понятный

Другой программист должен разобраться в твоём алгоритме без словаря. Читаемый код — добрый код.

Сортировка — шаг за шагом

Сортировка выбором

Самый простой алгоритм сортировки. На каждом шаге ищем минимальный элемент и ставим его на своё место.

Как это работает

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

1 Массив: [5, 3, 8, 1, 2]
2 Ищем минимум во всём массиве → это 1
3 Меняем его с первым: [1, 3, 8, 5, 2]
4 Ищем минимум в [3,8,5,2] → это 2
5 Меняем со вторым: [1, 2, 8, 5, 3]
… Повторяем до конца → [1, 2, 3, 5, 8]
O(n²) медленный, но простой для понимания
Код на Python
# Сортировка выбором # Берём массив чисел arr = [5, 3, 8, 1, 2] # Внешний цикл — перебираем каждую позицию # i идёт от 0 до последнего индекса for i in range(len(arr)): # Считаем, что минимум стоит на позиции i min_idx = i # Внутренний цикл — ищем真正的 минимум # Перебираем элементы ПОСЛЕ i for j in range(i + 1, len(arr)): # Если нашли элемент меньше текущего минимума if arr[j] < arr[min_idx]: # Запоминаем его позицию min_idx = j # Меняем местами: ставим минимум в позицию i arr[i], arr[min_idx] = arr[min_idx], arr[i] # Результат: отсортированный массив print(arr) # → [1, 2, 3, 5, 8]
O(n²) память: O(1) — сортируем на месте
Ещё один способ сортировать

Пузырьковая сортировка

Сравниваем соседние элементы и меняем их местами, если левый больше правого. «Тяжёлые» элементы всплывают в конец, как пузыри.

Как это работает

Проходим по массиву и сравниваем каждую пару соседей. Если левый больше правого — меняем местами. За один проход самый большой элемент «всплывёт» в конец.

1 [5, 3, 8, 1] → сравниваем 5 и 3
2 5 > 3? Да → меняем: [3, 5, 8, 1]
3 5 и 8 — не трогаем. 8 и 1 — меняем → [3, 5, 1, 8]
4 Второй проход: [3,5,1] → меняем 5 и 1 → [3, 1, 5, 8]
5 Третий проход: [3,1] → меняем → [1, 3, 5, 8] ✓
O(n²) медленный, но наглядный
Код на Python
# Пузырьковая сортировка arr = [5, 3, 8, 1] # Сколько проходов нам нужно? # n-1 проходов достаточно for i in range(len(arr)): # На каждом проходе проходим по парам # Каждый раз последний элемент уже "на месте" for j in range(len(arr) - 1): # Сравниваем соседей: левый и правый if arr[j] > arr[j + 1]: # Левый больше — меняем местами arr[j], arr[j + 1] = arr[j + 1], arr[j] print(arr) # → [1, 3, 5, 8]
💡

Улучшение: Если за проход не было ни одной замены — массив уже отсортирован. Добавь флаг swapped и выйди раньше.

O(n²) с флагом: O(n) в лучшем случае
Сортировка быстрее

Быстрая сортировка

Выбираем опорный элемент и делим массив на две части: меньше опорного и больше. Затем сортируем каждую часть рекурсивно.

Как это работает

Берём число — это опора (pivot). Всё, что ≤ опоры — уходит влево. Всё, что > — вправо. Повторяем для каждой половины.

1 Массив: [6, 3, 8, 1, 5, 2], pivot = 5
2 Лево (≤ 5): [3, 1, 2]
3 Право (> 5): [6, 8]
4 Сортируем [3,1,2] → [1,2,3]
5 Сортируем [6,8] → [6,8]
✓ Склеиваем: [1, 2, 3, 5, 6, 8]
O(n log n) в среднем — один из лучших
Код на Python
# Быстрая сортировка (Quick Sort) def quick_sort(arr): # Базовый случай рекурсии: # Если 0 или 1 элемент — уже отсортировано if len(arr) <= 1: return arr # Выбираем опорный элемент (pivot) # Здесь берём первый элемент массива pivot = arr[0] # Разделяем на две части: # left — все элементы ≤ pivot (кроме самого pivot) left = [x for x in arr[1:] if x <= pivot] # right — все элементы строго больше pivot right = [x for x in arr[1:] if x > pivot] # Рекурсивно сортируем части # и склеиваем: левая + pivot + правая return quick_sort(left) + [pivot] + quick_sort(right) arr = [6, 3, 8, 1, 5, 2] print(quick_sort(arr)) # → [1, 2, 3, 5, 6, 8]
💡

Почему быстрее? Каждый раз делим пополам. log₂(n) уровней × n сравнений = n·log(n). Для 1 млн элементов: ~20 млн операций вместо ~1 трлн.

O(n log n) худший случай: O(n²), но редко
Найти элемент

Два способа поиска

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

Линейный поиск

Как ищешь ключ в куче вещей — смотришь на каждую вещь по очереди. Просто, но медленно при большом количестве.

# Линейный поиск # Пробегаем массив от начала до конца def find(arr, target): # Перебираем каждый элемент по порядку for i in range(len(arr)): # Сравниваем текущий элемент с искомым if arr[i] == target: # Нашли! Возвращаем его позицию (индекс) return i # Прошли весь массив — не нашли return -1 # Пример использования: nums = [4, 7, 2, 9, 1] print(find(nums, 9)) # → 3 (индекс числа 9)
O(n) в худшем случае — проверяем всё
Двоичный поиск

Как ищешь слово в словаре: открываешь посередине, смотришь, нужная буква раньше или позже — и перелистываешь нужную половину.

# Двоичный поиск # Работает ТОЛЬКО с отсортированным массивом! def binary_find(arr, target): # lo — начало области поиска (лево) # hi — конец области поиска (право) lo, hi = 0, len(arr) - 1 # Пока область поиска не пуста while lo <= hi: # Находим середину области mid = (lo + hi) // 2 # Сравниваем средний элемент с целью if arr[mid] == target: return mid # Нашли! elif arr[mid] < target: # Цель правее — сужаем левую границу lo = mid + 1 else: # Цель левее — сужаем правую границу hi = mid - 1 # Область пуста — элемента нет в массиве return -1 # Отсортированный массив! nums = [1, 2, 4, 7, 9] print(binary_find(nums, 9)) # → 4
💡

Красота логарифма: В массиве из 1 000 000 элементов двоичный поиск найдёт за 20 шагов. Линейному нужно до 1 000 000.

O(log n) каждый шаг отбрасывает половину
Функция вызывает сама себя

Что такое рекурсия?

Рекурсия — это когда функция внутри себя вызывает саму себя. Как матрёшка: внутри каждой куклы — такая же, только поменьше. И так, пока не дойдёшь до самой маленькой.

Вызов 1 fact(4) = 4 × fact(3)
↓ вызов
Вызов 2 fact(3) = 3 × fact(2)
↓ вызов
Вызов 3 fact(2) = 2 × fact(1)
↓ вызов
Базовый случай — стоп! fact(1) = 1
↑ return 1
↑ return 2 × 1 = 2
↑ return 3 × 2 = 6
↑ return 4 × 6 = 24
Факториал — классика

Факториал числа n! — это произведение всех чисел от 1 до n. Пример: 4! = 4 × 3 × 2 × 1 = 24.

# Факториал через рекурсию def factorial(n): # Базовый случай: # Если n ≤ 1, возвращаем 1 # Без этого функция вызывала бы себя бесконечно! if n <= 1: return 1 # Рекурсивный случай: # n умножаем на factorial(n-1) # Пример: factorial(4) = 4 * factorial(3) return n * factorial(n - 1) print(factorial(4)) # → 24 print(factorial(5)) # → 120
O(n) n вызовов функции
Числа Фибоначчи

Каждое число — сумма двух предыдущих: 0, 1, 1, 2, 3, 5, 8, 13… Это природа: спираль раковины, расположение листьев.

# Числа Фибоначчи через рекурсию def fib(n): # Базовый случай: # fib(0) = 0, fib(1) = 1 if n <= 1: return n # Рекурсивный случай: # Каждое число = сумма двух предыдущих # fib(n) = fib(n-1) + fib(n-2) return fib(n - 1) + fib(n - 2) # Выводим первые 8 чисел for i in range(8): print(fib(i), end=" ") # → 0 1 1 2 3 5 8 13
⚠️

Внимание: Рекурсивная версия вычисляет fib(40) за несколько секунд, а fib(50) — зависает. В реальных задачах используют итеративный подход или мемоизацию.

O(2ⁿ) очень медленно без оптимизации
Анализ эффективности

Big-O простым языком

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

O(1)
Мгновенно
O(log n)
Быстро
O(n)
Нормально
O(n log n)
Приемлемо
O(n²)
Медленно
O(2ⁿ)
Катастрофа
Нотация Что значит 10 элементов 1 000 элементов Пример
O(1) Постоянное время 1 1 Обращение по индексу
O(log n) Каждый шаг — вдвое быстрее 3 10 Двоичный поиск
O(n) Пропорционально данным 10 1 000 Линейный поиск
O(n log n) Чуть медленнее n 33 10 000 Быстрая сортировка
O(n²) Квадрат роста 100 1 000 000 Пузырьковая сортировка
O(2ⁿ) Экспоненциальный рост 1 024 ∞ (зависает) Перебор подмножеств
Бонус-блок

Три главные структуры данных

Алгоритмы работают с данными. Чтобы выбирать правильный алгоритм, нужно понимать, как организованы данные.

📦

Массив

Просто список элементов подряд. Доступ по индексу — мгновенный. А вот вставить в середину — дорого, потому что нужно сдвинуть остальные.

# Python-список — это массив arr = [10, 20, 30] arr[1] # → 20 (быстро!) arr.append(40) # → [10, 20, 30, 40]
📚

Стек

Как стопка тарелок: кладёшь сверху, берёшь сверху. Принцип LIFO — Last In, First Out. Идеально для рекурсии и отмены действий.

stack = [] stack.append("а") # кладём сверху stack.append("б") stack.append("в") stack.pop() # → "в" (последний!)
🚶

Очередь

Как очередь в магазине: встаёшь в конец, выходишь из начала. Принцип FIFO — First In, First Out. Используется в BFS.

from collections import deque q = deque() q.append("а") # встаём в конец q.append("б") q.popleft() # → "а" (первый!)