Алгоритмы

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

Бинарный поиск делит ОТСОРТИРОВАННЫЙ массив пополам: сравнивает средний элемент с целью, отбрасывает половину, что не может её содержать, повторяет — O(log n). Данные нужно сначала отсортировать, иначе цель попадёт в отброшенную часть.

Линейный поиск перебирает элементы по одному, пока не найдёт цель или не исчерпает коллекцию — O(n). Он не требует упорядочивания и работает с любой последовательностью, но медленный на больших входах, ведь касается каждого элемента.

Используйте словарь «значение → индекс»: для каждого n, если target - n уже встречалось, верните оба индекса; иначе сохраните n -> i. Один проход, O(n) время и O(n) память — против перебора двойным циклом за O(n²). enumerate удобно даёт индекс.

Медиана — значение, не равное одновременно максимуму и минимуму. Чистый приём: a + b + c - max(a, b, c) - min(a, b, c). На сравнениях медиана — та, что лежит между двумя другими, например if (a <= b <= c) or (c <= b <= a): return b, и так далее. Равные значения обрабатываются, ведь <= сохраняет совпадения корректными.

Выбираем опорный элемент, разбиваем массив на меньшие и большие него, затем рекурсивно сортируем каждую часть; база рекурсии — 0 или 1 элемент. Средний и лучший случай — O(n log n), и работает на месте.

Поиск в ширину обходит граф уровень за уровнем через очередь, посещая всех соседей прежде, чем идти глубже — O(V + E). Он сообщает, есть ли путь, и находит КРАТЧАЙШИЙ путь в НЕВЗВЕШЕННОМ графе.

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

Итерируйте обменом кортежа: a, b = 0, 1; for _ in range(n): a, b = b, a + b; return a — O(n) время, O(1) память, без экспоненциальной рекурсии. Генератор выдаёт лениво: while True: yield a; a, b = b, a + b. Целые в Python произвольной точности, поэтому переполнения нет.

Жадный алгоритм строит решение, всегда беря локально оптимальный выбор на каждом шаге, в надежде прийти к глобальному оптимуму. Он прост и быстр, поэтому хорош как приближение, когда точное решение медленно, но не всегда оптимален.

Используйте два указателя: left в начале и right в конце. Двигайте каждый мимо не-букв, затем сравните s[left].lower() с s[right].lower(); при несовпадении верните False, иначе сдвиньте оба внутрь. Остановитесь, когда они пересекутся. Это O(n) время и O(1) память — без новой отфильтрованной строки. Инициализация right как len(s)-1 (а не -1) спасает от ошибки на единицу.

Бинарный поиск точки сдвига. Сравните nums[mid] с nums[high]: если nums[mid] > nums[high], пик в правой половине (low = mid + 1), иначе он в mid или левее (high = mid). Максимум — элемент прямо перед точкой сдвига: nums[low - 1], когда low встанет на минимум. O(log n); отсортированный массив без сдвига вернёт свой последний элемент.

Преобразуйте seen_ids в set один раз, затем пройдите recom_ids, оставляя элементы, чей id not in этого множества. Множество даёт O(1) проверку принадлежности, поэтому весь проход O(n); проверка in по списку сделала бы каждый тест O(m), а итог O(n*m). Проход по recom_ids напрямую сохраняет порядок.

Пройдите i от 0 до n-1, суммируя m[i][i] для главной диагонали и m[i][n-1-i] для побочной, затем верните abs(main - anti). Ключевой индекс побочной — n-1-i; ошибка на единицу здесь (использование n-i или счёт снизу вверх) — классический баг. Один проход — O(n).

Самый чистый способ с сохранением порядка — list(dict.fromkeys(items)): ключи словаря уникальны и с 3.7 хранят порядок вставки. Эквивалентно: пройти один раз и добавлять элементы, которых ещё нет в множестве seen, что даёт O(n). Простой set(items) убирает дубликаты, но теряет порядок, поэтому не удовлетворяет требованию.

Dijkstra находит путь наименьшего суммарного веса от источника во ВЗВЕШЕННОМ графе — ориентированном или нет, с циклами или без — пока веса рёбер НЕОТРИЦАТЕЛЬНЫ. Для отрицательных весов используйте Bellman-Ford.

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

Худший случай O(n^2) возникает при плохих опорных элементах — например, всегда брать первый или последний на отсортированном входе, что даёт максимально несбалансированные части. Смягчают это случайным опорным или медианой из трёх.

Отсортируйте goods один раз, затем для каждой потребности найдите точку вставки через bisect_left и сравните соседа снизу и сверху, взяв меньшее расстояние abs. Сумма даёт ответ за O((n+m) log n). Перебор — проход по всем товарам на покупателя — это O(n*m). Кандидаты вокруг индекса вставки — единственные два, что могут быть ближайшими.

Раз диапазон значений ограничен (256 значений байта), используйте сортировку подсчётом: читайте файл порциями, считайте частоту каждого байта в массиве из 256 ячеек, затем запишите каждое значение повторённым по его счётчику. Это O(n) время и O(1) доп. память (фиксированная таблица на 256 записей). Общий неограниченный случай потребовал бы внешней сортировки слиянием: разбить на отсортированные блоки на диске, затем слить.

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