Сложность алгоритма
Сложность алгоритма показывает, как растёт число его действий при росте размера входных данных N. Один проход по данным имеет сложность O(N), перебор всех пар — O(N²), перебор всех выборов из N пар — . Для файла A с сотней чисел годится любой алгоритм, а файл B с миллионами чисел за разумное время обрабатывает только программа сложности O(N) или O(N log N).
Как оценить сложность
Сложность алгоритма — зависимость числа его действий (времени работы) или занятой памяти от размера входных данных . Записывают только порядок роста: , .
- Отбросьте постоянные множители и младшие слагаемые: — это , — это .
- Один цикл по данным — . Два вложенных цикла по данным — . Перебор всех выборов из пар — .
- Сортировка
sorted— , двоичный поиск — , проверкаx inдля списка — , для множества — . - Цикл Python проходит порядка простых шагов в секунду. При и больше нужна сложность или .
Число действий и порядок роста
Чтобы оценить алгоритм, посчитайте, сколько раз выполняется самое частое действие, и выразите это число через . Цикл for i in range(n) с простым телом делает шагов. Два вложенных цикла по парам , при меньше делают шагов.
Порядок роста — главная часть этого числа без множителя. Его записывают через букву : значит, что при росте в 10 раз время растёт примерно в 100 раз. Постоянный множитель зависит от компьютера и языка, а порядок роста — нет, поэтому алгоритмы сравнивают по нему.
Пример
Программа перебирает все пары чисел с меньше . Сколько пар при и при ? Успеет ли она обработать чисел?
- 1.При : пар, это доли секунды.
- 2.При : около пар.
- 3.При шагов в секунду это секунд, больше 13 часов.
Ответ: и около ; не успеет
Порядок роста и число шагов при N = 1 000 000
| Сложность | Пример алгоритма | Шагов |
|---|---|---|
элемент списка по индексу, x in для множества | 1 | |
| двоичный поиск в упорядоченном списке | 20 | |
| сумма, максимум, один проход по файлу | ||
сортировка слиянием, sorted | ||
| перебор пар, сортировка пузырьком | ||
| перебор всех выборов из пар | больше |
Один проход вместо перебора пар
Многие задачи о парах решают одним проходом: вместо того чтобы для каждого числа заново смотреть все предыдущие, храните о них сводку. Для пар с суммой, кратной , сводка — сколько уже прочитано чисел с каждым остатком. Число с остатком образует подходящую пару с каждым прочитанным числом с остатком . Так сложность падает с до .
Тот же приём лежит в основе префиксных сумм и таблицы остатков.
Пример
Дана последовательность 5, 7, 4, 2, 9, 1. Сколько пар чисел (порядок не важен) имеют сумму, кратную 3?
- 1.Остатки от деления на 3: 2, 1, 1, 2, 0, 1.
- 2.Пару дают остатки 1 и 2 или 0 и 0. Чисел с остатком 1 — три, с остатком 2 — два, с остатком 0 — одно.
- 3.Пар: , пар из двух нулевых остатков нет.
- 4.Программа считает ответ двумя способами: двойным циклом за и одним проходом за . Она печатает 6 6.
Ответ:
Сортировка и двоичный поиск
Простые сортировки (пузырьком, выбором, вставками) сравнивают элементы попарно и работают за . Сортировка слиянием и быстрая сортировка работают за . Встроенные sorted и list.sort в Python тоже имеют сложность , поэтому сортировку пишут ими, а не своим циклом.
Двоичный поиск ищет значение в упорядоченном списке: сравнивает его с серединой и отбрасывает половину списка. После каждого шага список вдвое короче, поэтому шагов не больше . Проверка x in a для списка смотрит все элементы, это . Для множества set та же проверка в среднем стоит .
Пример
Сколько сравнений в худшем случае делает двоичный поиск в упорядоченном списке из 1000 чисел? А из чисел?
- 1.После каждого сравнения остаётся не больше половины списка: 1000, 500, 250, 125, 62, 31, 15, 7, 3, 1.
- 2.Это 10 сравнений: .
- 3.Для : меньше , а больше, поэтому сравнений.
Ответ: 10 и 20
Переборные алгоритмы
Переборный алгоритм проверяет все возможные варианты. Если из каждой из пар выбирают одно число, вариантов . Перебор годится, пока вариантов не больше нескольких миллионов: . Уже при вариантов больше .
Варианты удобно перебирать через itertools.product: product([0, 1], repeat=n) выдаёт все наборы из нулей и единиц. На малых данных перебор даёт точный ответ, и им проверяют быструю программу.
Пример
Даны пары (1, 3), (5, 12), (6, 9). Перебором найдите наибольшую сумму чисел, по одному из каждой пары, которая не делится на 3.
- 1.Вариантов . Набор из нулей и единиц говорит, какое число пары взять.
- 2.Наибольшая сумма делится на 3.
- 3.Следующая по величине — , она не делится на 3. Программа печатает 22.
Ответ:
Файл A и файл B
В заданиях 26 и 27 файл A обычно маленький, а файл B большой, и в условии сказано: переборный алгоритм для файла B выполняется слишком долго. Оцените сложность до того, как писать программу: подставьте размер файла B в число шагов и разделите на шагов в секунду.
Простая программа за на файле A даёт верный ответ. Этой программой проверяют быструю: обе запускают на файле A или на случайных малых данных, и ответы должны совпасть.
Память тоже растёт с . Целое число в списке Python занимает около 36 байт, поэтому список из чисел занимает порядка 360 Мбайт. Если числа нужны по одному, читайте файл в цикле и не храните их в списке: тогда память .
Пример
Проверьте подсчёт пар с суммой, кратной 3, одним проходом: сравните его с двойным циклом на 1000 случайных наборов.
- 1.Каждый набор — до 10 случайных чисел от 1 до 100.
- 2.Для каждого набора считаем ответ двойным циклом и одним проходом, как в примере про один проход.
- 3.Если ответы разные, программа печатает набор. Она печатает только ok, значит, быстрая программа верна на всех наборах.
Ответ: ok