Приведите примеры алгоритмов, изучаемых вами в школе

Ниже — примеры алгоритмов, которые обычно изучают в школе. Для каждого даю суть, пошаговый разбор и пример задачи, а также указания по сложности. Поскольку предмет и класс не указаны, ориентируюсь на среднюю школу и базовый уровень объяснений. 1) Линейный поиск (linear search) - Что делает: ищет целевой элемент в любом массиве, просматривая элементы слева направо. - Пошаговый разбор: 1) Берём первый элемент массива. 2) Сравниваем с искомым значением. 3)Если совпало — возвращаем индекс. Если нет — переходим к следующему элементу. 4) Если дошли до конца массива — элемента нет. - Пример: найти число 7 в [3, 4, 7, 1]. - i=0: 3 ≠ 7 - i=1: 4 ≠ 7 - i=2: 7 = 7 — нашли на позиции 2 (нумерация с 0) или 3 (с 1). - Сложность: время O(n) в худшем и среднем случае, память O(1). - Когда применяется: когда массив не упорядочен или его размер небольшой. 2) Бинарный поиск (binary search) - Что делает: ищет элемент в отсортированном массиве, каждый раз деля диапазон пополам. - Пошаговый разбор: 1) Берем середину диапазона и сравниваем с искомым. 2) Если равно — нашли. 3) Если цель меньше середины — смотрим левую половину, иначе — правую. 4) Повторяем, пока диапазон не пуст. - Пример: найти 26 в [3, 7, 12, 18, 26, 31]. - середина = 12, 26 > 12 → смотрим справа - новая середина = 26 → нашли - Сложность: время O(log n), память O(1). - Когда применяется: когда массив отсортирован и нужно быстро найти элемент. 3) Сортировка пузырьком (bubble sort) - Что делает: многократно строит проход по массиву, буквально «всплывая» максимальные элементы в конец. - Пошаговый разбор (упрощённо): 1) Пробегаем соседние элементы слева направо. 2) Меняем местами соседние элементы, если они стоят в неправильном порядке. 3) После первого полного прохода самый большой элемент оказывается в конце. 4) Повторяем для остальных элементов. - Пример: [5, 1, 4, 2] → после 1-го прохода: [1, 4, 2, 5], затем [1, 2, 4, 5]. - Сложность: время O(n^2) в худшем и среднем случаях, память O(1). - Когда применяется: для небольших массивов или как наглядный пример сортировки. 4) Сортировка вставками (insertion sort) - Что делает: строит отсортированную часть слева, вставляя каждый новый элемент на своё место. - Пошаговый разбор: 1) Берём второй элемент и вставляем его в отсортированную лево часть [a1]. 2) Затем берём третий элемент и вставляем в правильную позицию в уже отсортированной части [a1, a2]. 3) И так далее. - Пример: [3, 1, 4, 2] → [1, 3, 4, 2] → [1, 2, 3, 4]. - Сложность: время O(n^2) в худшем, O(n) в лучшем случае (когда массив уже отсортирован), память O(1). - Когда применяется: эффективна на маленьких массивах или когда данные почти отсортированы. 5) Сортировка слиянием (merge sort) - Что делает: разделяет массив пополам, сортирует каждую половину, затем объединяет их в один отсортированный массив. - Пошаговый разбор (разделение и слияние): 1) Разделить массив на две половины до размера 1. 2) Восстанавливать отсортированную последовательность путем попарного сравнения элементов левой и правой частей. - Пример: [5, 2, 4, 6, 1] → делим на [5,2,4] и [6,1], далее сортируем и сливаем в [1,2,4,5,6]. - Сложность: время O(n log n) в любом случае, память O(n) (доп. массив для слияния). - Когда применяется: стабильная сортировка, когда важна предсказуемая сложность. 6) Быстрая сортировка (quick sort) - Что делает: выбирает опорный элемент, распаковывает массив на элементы меньше опорного и больше его, и рекурсивно сортирует части. - Пошаговый разбор (пример): 1) Выбираем опорный элемент, например первый. 2) Разделяем массив на две части: меньше опорного и больше опорного. 3) Рекурсивно сортируем каждую часть и соединяем. - Пример: [3, 6, 8, 2, 10] → опорный 3 → [2 | 3 | 6,8,10] → далее сортируем подмассивы. - Сложность: среднее время O(n log n), худшее O(n^2) в неблагоприятном выборе опорного, память O(log n) за счёт рекурсии. - Когда применяется: общая цель — быстрая сортировка в большинстве случаев, без гарантии стабильности. 7) Поиск в графе: BFS и DFS - Что делают: - BFS (обход в ширину): посещает вершины по уровням, используется для нахождения кратчайших путей в невзвешенных графах. - DFS (обход в глубину): идёт как можно глубже по ветвям, полезен для проверки связности, топологической сортировки и т.д. - Пошаговый разбор (BFS): 1) Помещаем начальную вершину в очередь. 2) Пока очередь не пуста — вытаскиваем вершину, помечаем посещённой, добавляем соседей. 3) Повторяем. - Пример: найти кратчайший путь от вершины A к всем остальным в неориентированном графе без весов. - Сложность: O(V + E) по времени, O(V) по памяти. - Когда применяется: поиск путей на графах, проверка связности, планирование маршрутов. - Пример DFS: исследуем глубину, помечаем посещённые вершины, возвращаемся обратно при отсутствии соседей. 8) Алгоритм Дейкстры (Dijkstra) - Что делает: на графе с неотрицательными весами ищет кратчайшие расстояния от одной вершины до всех остальных. - Пошаговый разбор (упрощённо): 1) Все расстояния до вершин устанавливаем как бесконечность, расстояние до начальной — 0. 2) Из непосещённых вершин выбираем ту, у которой минимское текущее расстояние. 3) Обновляем расстояния для соседей этой вершины: dist(сосед) = min(dist(сосед), dist(текущая) + вес ребра). 4) Помечаем вершину как посещённую и повторяем. - Пример: граф с узлами A, B, C и весами ребер; найти кратчайшие пути от A. - Сложность: без структуры данных — O(V^2); с мин-кучей — O((V + E) log V). - Когда применяется: любые задачи на кратчайшие пути в графах с положительными весами. 9) Алгоритм Флойд–Уоршелла (Floyd-Warshall) - Что делает: на графе с произвольными весами (включая отрицательные, без отрицательных циклов) находит кратчайшие расстояния между всеми парами вершин. - Пошаговый разбор: 1) Инициализируем матрицу расстояний: dist[i][j] = вес ребра i→j или бесконечность, если такого ребра нет; dist[i][i] = 0. 2) Для каждого промежуточного узла k обновляем dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]). 3) Повторяем для всех пар i, j и для всех k. - Пример: найти кратчайшие расстояния между любыми двумя вершинами в небольшом графе. - Сложность: время O(n^3), пространство O(n^2). - Когда применяется: когда нужно знать кратчайшие расстояния между всеми парами вершин. 10) Динамическое программирование: задача о наибольшей общей подпоследовательности (LCS) - Что делает: находит длину (или саму последовательность) наибольшей общей подпоследовательности между двумя строками. - Пошаговый разбор: 1) Пусть dp[i][j] — длина LCS для первых i символов строки A и первых j символов строки B. 2) Если A[i-1] == B[j-1], то dp[i][j] = dp[i-1][j-1] + 1. 3) Иначе dp[i][j] = max(dp[i-1][j], dp[i][j-1]). 4) Ответ — dp[len(A)][len(B)]. - Пример: A = "AGGTAB", B = "GXTXAYB" → LCS длины 4 ("GTAB"). - Сложность: время O(nm), память O(nm). - Когда применяется: сравнение строк, анализ версий текста, многие задачи на строки. 11) 0-1 Knapsack (рюкзак 0/1) - Что делает: выбираем предметы с весом и стоимостью так, чтобы общая стоимость была максимальной при ограничении по весу. - Пошаговый разбор: 1) Пусть dp[i][w] — максимальная стоимость, используя первые i предметов и ограничение веса w. 2) Решение: либо не берем i-й предмет → dp[i-1][w], либо берем → dp[i-1][w - weight[i]] + value[i] (если w >= weight[i]). 3) dp[i][w] = max( dp[i-1][w], dp[i-1][w - weight[i]] + value[i] ). - Пример: есть предметы (вес, стоимость): (3, 4), (4, 5), максимум вес 7. - Сложность: время O(nW), память O(nW). - Когда применяется: учебная задача по динамике, реальные задачи оптимизации. 12) Жадные алгоритмы: задача размена монет (coin change) в канонических системах - Что делает: с минимальным количеством монет подбираем сдачу. - Пошаговый разбор (для канонических монет, например 1, 5, 10, 25): 1) Берём наибольшую монету, которая не превышает требуемую сумму. 2) Вычитаем её значение и повторяем, пока сумма не станет 0. - Пример: сумма 63, монеты 25, 10, 5, 1 → берём 25: остаётся 38; снова 25 → 13; 10 → 3; 1+1+1 → всего 6 монет. - Сложность: время O(k) где k — число монет в размене (часто линейно по количеству монет), память O(1). - Когда применяется: задачи с конкретной монетной системой, где жадный подход даёт оптимальное решение. 13) Жадные против ветвей и границ и backtracking (упрощённо) - Что делает: искатель решений в пространства вариантов. - Пошаговый разбор (обзорный): 1) Возьмём ветку решений и вычислим нижнюю/верхнюю оценку. 2) Отбрасываем ветви, которые не могут привести к лучшему решению. 3) Рекурсивно исследуем только перспективные ветви. - Пример в школе: задача раскраски графа двумя цветами, задача N-ферзей. - Сложность зависит от задачи и реализации; иногда экспоненциальная без оптимизаций, но даёт полезное представление о технике. Советы по изучению: - Понимайте принцип работы каждого алгоритма на простых примерах (чтобы увидеть «почему так»). - Разбирайте сложность и память: это помогает сравнивать алгоритмы для разных задач. - Пишите маленькие псевдокоды или короткие примеры выполнения вручную — это облегчает запоминание. - Задавайте вопросы на конкретных примерах: задача на поиск в графе, задача на сортировку или задача на динамику. Если хочется, могу привести развернутый разбор одной конкретной задачи по выбранному алгоритму: например, возьмём задачу на Dijkstra с минимальным графом и пройдём её пошагово, или сделаем разбор задачи на LCS с двумя строками. Какой алгоритм выбрать для детального примера?