11 мин чтениясортировкабинарный поисксложностьдва указателяbisectзадание 17задание 25задание 26КЕГЭ
Сортировки, поиск и оценка сложности
Встроенные сортировки Python, сортировка по ключу, бинарный поиск и bisect, метод двух указателей, подсчёт инверсий и оценка времени работы для заданий 17, 25 и 26.
Открываем тему…
Почему важны сортировка и оценка сложности
В заданиях 17, 25 и 26 на экзамене приходят данные из файлов: от 10³ до 10⁷ чисел. Двойной цикл по всем парам — O(n²) — при n = 10⁵ уже требует 10¹⁰ операций и не уложится во время. Умение заменить перебор сортировкой, бинарным поиском или двумя указателями определяет, получит ли решение полный балл.
- O(n) — один проход; n = 10⁷ допустимо.
- O(n log n) — сортировка; n = 10⁶ приемлемо (около 2·10⁷ операций).
- O(n²) — вложенные циклы; допустимо только при n ≲ 5·10³.
- Бинарный поиск по отсортированному массиву — O(log n) на запрос; пакет из q запросов — O(q log n).
- Python-сортировка sorted() и list.sort() — устойчивая (равные по ключу элементы сохраняют исходный порядок), сложность O(n log n).
Типовые приёмы
- Сортировка по ключу: sorted(a, key=lambda t: (-t[1], t[0])) — по убыванию второго поля и по возрастанию первого.
- Бинарный поиск: from bisect import bisect_left, bisect_right; число элементов в [L, R] — bisect_right(a, R) − bisect_left(a, L).
- Два указателя по отсортированному массиву: подсчёт пар с заданной суммой, фрагменты с ограничением на сумму.
- Подсчётная сортировка: если значения ограничены (например, 0…10⁶), храните счётчики в списке — O(n + K).
- Жадность после сортировки: интервалы сортируют по правому концу, предметы — по массе (задание 26).
Примеры
ПримерСортировка по составному ключу
Дан список (фамилия, балл): Орлов 85, Волков 92, Белов 85, Зайцев 92, Алёшин 70. Упорядочьте его по убыванию балла, а при равных баллах — по алфавиту фамилий. Какая фамилия будет третьей?
Решение
students = [('Орлов', 85), ('Волков', 92), ('Белов', 85), ('Зайцев', 92), ('Алёшин', 70)]
students.sort(key=lambda t: (-t[1], t[0]))
print(students[2][0])
Порядок после сортировки: Волков 92, Зайцев 92, Белов 85, Орлов 85, Алёшин 70. Третья фамилия — Белов. Знак минус при балле инвертирует порядок по числовому ключу, а кортеж задаёт приоритет полей.
ПримерЧисло шагов бинарного поиска
Сколько сравнений в худшем случае потребуется, чтобы найти число в отсортированном массиве из 1000 элементов бинарным поиском?
Решение
Каждое сравнение сокращает диапазон поиска вдвое: после k сравнений остаётся не более 1000 / 2^k элементов. Поиск завершается, когда остался 1 элемент: 2^k ≥ 1000, то есть k = ⌈log₂ 1000⌉ = 10 (2⁹ = 512 < 1000 ≤ 1024 = 2¹⁰). Для линейного поиска в худшем случае понадобилось бы 1000 сравнений.
Примерbisect: сколько чисел лежит в отрезке
Массив [2, 5, 5, 7, 9, 12, 12, 12, 15, 20] отсортирован. Сколько его элементов принадлежит отрезку [5; 12]?
Решение
from bisect import bisect_left, bisect_right
a = [2,5,5,7,9,12,12,12,15,20]
print(bisect_right(a, 12) - bisect_left(a, 5))
bisect_left(a, 5) = 1 (позиция первой пятёрки), bisect_right(a, 12) = 8 (позиция после последней двенадцати). Разность 8 − 1 = 7: элементы 5, 5, 7, 9, 12, 12, 12. Для q запросов к массиву из n элементов суммарное время O(q log n) вместо O(q·n).
ПримерДва указателя: пары с заданной суммой
В отсортированном массиве 1, 2, 3, 4, 5, 6, 7, 8 найдите количество пар элементов с суммой 9.
Решение
Ставим указатели i = 0 и j = n − 1. Если a[i] + a[j] = 9 — пара найдена, сдвигаем оба; если сумма меньше — сдвигаем i вправо; если больше — j влево.
i, j, cnt = 0, len(a) - 1, 0
while i < j:
s = a[i] + a[j]
if s == 9:
cnt += 1
i += 1
j -= 1
elif s < 9:
i += 1
else:
j -= 1
Пары: (1, 8), (2, 7), (3, 6), (4, 5) — всего 4. Сложность O(n) вместо O(n²) при переборе всех пар. При повторяющихся значениях счётчик нужно считать с учётом кратностей.
ПримерИнверсии и обмены сортировки пузырьком
Сколько обменов соседних элементов выполнит сортировка пузырьком для массива 3, 1, 4, 1, 5, 9, 2, 6?
Решение
Каждый обмен соседних элементов устраняет ровно одну инверсию — пару (i < j), для которой a[i] > a[j]. Поэтому число обменов равно числу инверсий исходного массива:
inv = sum(1 for i in range(n) for j in range(i + 1, n) if a[i] > a[j])
Для 3, 1, 4, 1, 5, 9, 2, 6 получаем 8. Для массива из 10⁶ элементов этот двойной цикл слишком медленный; инверсии считают сортировкой слиянием за O(n log n).
ПримерМедиана и порядковая статистика
Найдите медиану набора 14, 3, 9, 27, 5, 18, 11, 22, 7, 31, 16.
Решение
Для нечётного количества элементов медиана — элемент на среднем месте в отсортированном списке. Сортируем: 3, 5, 7, 9, 11, 14, 16, 18, 22, 27, 31. Всего 11 чисел, средний — шестой: 14.
a.sort()
print(a[len(a) // 2])
Для чётного количества медианой чаще считают полусумму двух средних элементов — внимательно читайте определение в условии. Порядковые статистики (k-й по величине элемент) также берут из отсортированного списка: a[k − 1].
ПримерОценка допустимого алгоритма
В файле 2·10⁵ чисел. Нужно найти количество пар (i, j), i < j, с суммой, равной заданному числу. Допустим ли перебор всех пар? Как ускорить?
Решение
Всего пар ≈ n²/2 = 2·10¹⁰ — это тысячи секунд работы Python, перебор не годится. Решение за O(n log n): отсортировать массив и применить два указателя либо использовать словарь Counter и для каждого x прибавлять cnt[S − x] (с аккуратным учётом x = S − x). Словарь даёт O(n) в среднем.
from collections import Counter
cnt = Counter(a)
pairs = sum(cnt[x] * cnt[S - x] for x in cnt if x < S - x)
if S % 2 == 0:
pairs += cnt[S // 2] * (cnt[S // 2] - 1) // 2
Правило: если n ≥ 10⁵, ищите алгоритм не хуже O(n log n).