Задание 27
тема 8 из 9

Сложность алгоритма

Сложность алгоритма показывает, как растёт число его действий при росте размера входных данных N. Один проход по данным имеет сложность O(N), перебор всех пар — O(N²), перебор всех выборов из N пар — O(2N)O(2^N). Для файла A с сотней чисел годится любой алгоритм, а файл B с миллионами чисел за разумное время обрабатывает только программа сложности O(N) или O(N log N).

Реже в задании27На карте навыков

Как оценить сложность

Сложность алгоритма — зависимость числа его действий (времени работы) или занятой памяти от размера входных данных NN. Записывают только порядок роста: O(N)O(N), O(N2)O(N^2).

  • Отбросьте постоянные множители и младшие слагаемые: 3N+53N + 5 — это O(N)O(N), N(N−1)2\dfrac{N(N - 1)}{2} — это O(N2)O(N^2).
  • Один цикл по данным — O(N)O(N). Два вложенных цикла по данным — O(N2)O(N^2). Перебор всех выборов из NN пар — O(2N)O(2^N).
  • Сортировка sorted — O(Nlog⁡N)O(N \log N), двоичный поиск — O(log⁡N)O(\log N), проверка x in для списка — O(N)O(N), для множества — O(1)O(1).
  • Цикл Python проходит порядка 10710^7 простых шагов в секунду. При N=106N = 10^6 и больше нужна сложность O(N)O(N) или O(Nlog⁡N)O(N \log N).

Число действий и порядок роста

Чтобы оценить алгоритм, посчитайте, сколько раз выполняется самое частое действие, и выразите это число через NN. Цикл for i in range(n) с простым телом делает NN шагов. Два вложенных цикла по парам ii, jj при ii меньше jj делают N(N−1)2\dfrac{N(N - 1)}{2} шагов.

Порядок роста — главная часть этого числа без множителя. Его записывают через букву OO: O(N2)O(N^2) значит, что при росте NN в 10 раз время растёт примерно в 100 раз. Постоянный множитель зависит от компьютера и языка, а порядок роста — нет, поэтому алгоритмы сравнивают по нему.

Пример

Программа перебирает все пары чисел с ii меньше jj. Сколько пар при N=1000N = 1000 и при N=106N = 10^6? Успеет ли она обработать 10610^6 чисел?

  1. 1.При N=1000N = 1000: 1000⋅9992=499 500\dfrac{1000 \cdot 999}{2} = 499\,500 пар, это доли секунды.
  2. 2.При N=106N = 10^6: около 5⋅10115 \cdot 10^{11} пар.
  3. 3.При 10710^7 шагов в секунду это 5⋅1045 \cdot 10^4 секунд, больше 13 часов.

Ответ: 499 500499\,500 и около 5⋅10115 \cdot 10^{11}; не успеет

Порядок роста и число шагов при N = 1 000 000

СложностьПример алгоритмаШагов
O(1)O(1)элемент списка по индексу, x in для множества1
O(log⁡N)O(\log N)двоичный поиск в упорядоченном списке20
O(N)O(N)сумма, максимум, один проход по файлу10610^6
O(Nlog⁡N)O(N \log N)сортировка слиянием, sorted2⋅1072 \cdot 10^7
O(N2)O(N^2)перебор пар, сортировка пузырьком101210^{12}
O(2N)O(2^N)перебор всех выборов из NN парбольше 1030000010^{300000}

Один проход вместо перебора пар

Многие задачи о парах решают одним проходом: вместо того чтобы для каждого числа заново смотреть все предыдущие, храните о них сводку. Для пар с суммой, кратной kk, сводка — сколько уже прочитано чисел с каждым остатком. Число xx с остатком rr образует подходящую пару с каждым прочитанным числом с остатком (k−r) mod k(k - r) \bmod k. Так сложность падает с O(N2)O(N^2) до O(N)O(N).

Тот же приём лежит в основе префиксных сумм и таблицы остатков.

Пример

Дана последовательность 5, 7, 4, 2, 9, 1. Сколько пар чисел (порядок не важен) имеют сумму, кратную 3?

  1. 1.Остатки от деления на 3: 2, 1, 1, 2, 0, 1.
  2. 2.Пару дают остатки 1 и 2 или 0 и 0. Чисел с остатком 1 — три, с остатком 2 — два, с остатком 0 — одно.
  3. 3.Пар: 3⋅2=63 \cdot 2 = 6, пар из двух нулевых остатков нет.
  4. 4.Программа считает ответ двумя способами: двойным циклом за O(N2)O(N^2) и одним проходом за O(N)O(N). Она печатает 6 6.

Ответ: 66

Сортировка и двоичный поиск

Простые сортировки (пузырьком, выбором, вставками) сравнивают элементы попарно и работают за O(N2)O(N^2). Сортировка слиянием и быстрая сортировка работают за O(Nlog⁡N)O(N \log N). Встроенные sorted и list.sort в Python тоже имеют сложность O(Nlog⁡N)O(N \log N), поэтому сортировку пишут ими, а не своим циклом.

Двоичный поиск ищет значение в упорядоченном списке: сравнивает его с серединой и отбрасывает половину списка. После каждого шага список вдвое короче, поэтому шагов не больше ⌊log⁡2N⌋+1\lfloor \log_2 N \rfloor + 1. Проверка x in a для списка смотрит все элементы, это O(N)O(N). Для множества set та же проверка в среднем стоит O(1)O(1).

Пример

Сколько сравнений в худшем случае делает двоичный поиск в упорядоченном списке из 1000 чисел? А из 10610^6 чисел?

  1. 1.После каждого сравнения остаётся не больше половины списка: 1000, 500, 250, 125, 62, 31, 15, 7, 3, 1.
  2. 2.Это 10 сравнений: ⌊log⁡21000⌋+1=9+1=10\lfloor \log_2 1000 \rfloor + 1 = 9 + 1 = 10.
  3. 3.Для 10610^6: 2192^{19} меньше 10610^6, а 2202^{20} больше, поэтому 19+1=2019 + 1 = 20 сравнений.

Ответ: 10 и 20

Переборные алгоритмы

Переборный алгоритм проверяет все возможные варианты. Если из каждой из NN пар выбирают одно число, вариантов 2N2^N. Перебор годится, пока вариантов не больше нескольких миллионов: 220≈1062^{20} \approx 10^6. Уже при N=40N = 40 вариантов больше 101210^{12}.

Варианты удобно перебирать через itertools.product: product([0, 1], repeat=n) выдаёт все наборы из nn нулей и единиц. На малых данных перебор даёт точный ответ, и им проверяют быструю программу.

Пример

Даны пары (1, 3), (5, 12), (6, 9). Перебором найдите наибольшую сумму чисел, по одному из каждой пары, которая не делится на 3.

  1. 1.Вариантов 23=82^3 = 8. Набор из нулей и единиц говорит, какое число пары взять.
  2. 2.Наибольшая сумма 3+12+9=243 + 12 + 9 = 24 делится на 3.
  3. 3.Следующая по величине — 1+12+9=221 + 12 + 9 = 22, она не делится на 3. Программа печатает 22.

Ответ: 2222

Файл A и файл B

В заданиях 26 и 27 файл A обычно маленький, а файл B большой, и в условии сказано: переборный алгоритм для файла B выполняется слишком долго. Оцените сложность до того, как писать программу: подставьте размер файла B в число шагов и разделите на 10710^7 шагов в секунду.

Простая программа за O(N2)O(N^2) на файле A даёт верный ответ. Этой программой проверяют быструю: обе запускают на файле A или на случайных малых данных, и ответы должны совпасть.

Память тоже растёт с NN. Целое число в списке Python занимает около 36 байт, поэтому список из 10710^7 чисел занимает порядка 360 Мбайт. Если числа нужны по одному, читайте файл в цикле и не храните их в списке: тогда память O(1)O(1).

Пример

Проверьте подсчёт пар с суммой, кратной 3, одним проходом: сравните его с двойным циклом на 1000 случайных наборов.

  1. 1.Каждый набор — до 10 случайных чисел от 1 до 100.
  2. 2.Для каждого набора считаем ответ двойным циклом и одним проходом, как в примере про один проход.
  3. 3.Если ответы разные, программа печатает набор. Она печатает только ok, значит, быстрая программа верна на всех наборах.

Ответ: ok

Потренируйте навык

Все задания на этот навык

Решать