Введение в алгоритмы

Одна из основных задач, возникающих при работе с алгоритмами, состоит в оценке эффективности написанной программы и в поиске наиболее экономичного подхода. Самое простое и поверхностное решение заключается в том, чтобы написать программу, измерить время её выполнения, а недостаточно быструю переписать.

Линейный поиск

Дан массив целых чисел длины $N$. Требуется найти в нём заданное число $x$ и вернуть его индекс. Если $x$ в массиве не встречается, необходимо вернуть -1.

def find_element(numbers, x):
    for i in range(len(numbers)):
        if numbers[i] == x:
            return i
    return -1

Можно утверждать, что скорость работы алгоритма в худшем случае пропорциональна размеру массива. На математическом языке это формулируется так: «Вычислительная сложность алгоритма линейно зависит от размера входных данных».

Вычислительная сложность представляет собой количество элементарных операций, совершаемых алгоритмом. Под входными данными понимается всё, поданное алгоритму на вход; в рассматриваемой задаче это массив numbers и число x, а размер входа примерно равен N. Линейная зависимость описывается формулой $y = kx+b$.

Бинарный поиск

В массиве, упорядоченном по возрастанию, нужное число находится гораздо быстрее.

Допустим, что поиск ведётся по словарю из 100 страниц. Объём рассматриваемой части книги будет каждый раз уменьшаться вдвое до тех пор, пока не останется всего одна страница. Делить словарь из 100 страниц пополам можно не более 7 раз, а значит, для нахождения нужного слова достаточно просмотреть не более 7 страниц.

Этот алгоритм называется бинарным поиском, а также: двоичный поиск, метод деления пополам, дихотомия. Скорость его работы имеет логарифмическую зависимость от размера входных данных.

def binary_search(arr, x):
    mid, low, high = 0, 0, len(arr) - 1

    while low <= high:
        mid = (high + low) // 2

        if arr[mid] < x:
            low = mid + 1
        elif arr[mid] > x:
            high = mid - 1
        else:
            return mid

    return -1

Линейный vs Бинарный поиск

Запустим оба поиска на одних и тех же данных и рассмотрим, как меняется измеренное время работы с ростом массива.

Будем искать элемент, стоящий в самом конце, что даёт худший случай для линейного поиска:

Размер массива	Линейный поиск	Бинарный поиск
10	0.2 мкс	0.14 мкс
100	0.9 мкс	0.23 мкс
1 000	11.2 мкс	0.37 мкс
10 000	122.1 мкс	0.50 мкс
100 000	1281.6 мкс	0.59 мкс
1 000 000	12340.3 мкс	0.69 мкс

При увеличении массива в 10 раз линейный поиск замедляется также примерно вдесятеро: 11 мкс, 122 мкс, 1.3 мс, 12 мс. Бинарный же поиск за пять порядков роста замедлился всего впятеро, с 0.14 до 0.69 мкс.

Именно так выглядит разница между $O(n)$ и $O(\log n)$ на практике. На миллионе элементов бинарный поиск быстрее линейного почти в восемнадцать тысяч раз, и чем больше накопленных данных, тем этот разрыв шире.

Измерение может быть воспроизведено самостоятельно:

from timeit import timeit

n = 1_000_000
setup = f"from __main__ import find_element, binary_search; arr = list(range({n})); x = {n} - 1"
print(timeit("find_element(arr, x)", setup=setup, number=1000) / 1000)
print(timeit("binary_search(arr, x)", setup=setup, number=1000) / 1000)

Сложность алгоритма. O-нотация

Для того чтобы говорить о скорости алгоритма, не привязываясь к конкретной машине, была введена O-нотация — запись, показывающая, как растёт число операций с ростом входных данных. В ней не учитываются константы и коэффициенты, то есть если в алгоритме совершается $5\cdot n+3$ операций, его сложность будет $O(n)$. В асимптотической оценке отброшены и значения констант при $n$. Отброшенные константы также имеют значение, однако изменить применимость алгоритма на практике они не могут.

Кроме линейной и логарифмической, при оценке времени работы алгоритмов часто встречаются следующие зависимости:

Квадратичная зависимость $O(n^2)$.
Кубическая зависимость $O(n^3)$.
Экспоненциальная зависимость $O(2^n)$.
Константная зависимость $O(1)$. Встречаются и случаи, когда время работы алгоритма не зависит от размера входных данных, а число выполняемых операций остаётся постоянным.

Оценка времени исполнения

Современный процессор выполняет около 2.5 миллиардов действий, называемых «инструкциями», в секунду, или, иначе говоря, «тактовая частота процессора = 2.5 ГГц».

Точнее, за секунду проходит 2.5 миллиарда тактов. Подобно тому как метроном задаёт ритм музыки, специальный генератор тактовой частоты задаёт ритм, в котором работают процессор и микросхемы компьютера. В первом приближении можно считать, что один такт соответствует одной инструкции.

Предположим, что обработка каждой итерации цикла занимает один такт процессора. Возьмём $10^9$ итераций, тогда:

$$ t = \frac{10^9 [итер] \cdot 1 [\frac{такт}{итер}]}{2.5 \cdot 10^9 [\frac{такт}{с}]} = 0.4 [с] $$

Количество инструкций в программе может немного отличаться в зависимости от процессора или от использованного компилятора. Существуют команды, которым требуется несколько тактов, а другие инструкции, напротив, выполняются за доли такта.

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

Чтобы оценить, во сколько раз ошибается такая оценка, измерим, сколько секунд займёт пустой цикл, выполненный миллиард раз.

# Python
import time

time_start = time.time()
i = 0
while i < 1000000000:
    # Do nothing
    i += 1

time_finish = time.time()
time_span = time_finish - time_start
print(time_span, 'seconds')

97.01491403579712 seconds

// CPP
#include <chrono>
#include <iostream>

int main() {
    using namespace std::chrono;
    auto time_start = high_resolution_clock::now();
    int i = 0;
    while (i < 1000000000) {
        // Do nothing
        ++i;
    }
    auto time_finish = high_resolution_clock::now();
    auto time_span = duration_cast<duration<double>>(time_finish - time_start);

    std::cout << time_span.count() << " seconds\n";
  return 0;
}

Каждая итерация цикла состоит из трёх действий: прибавить единицу, проверить условие и переместиться обратно к началу цикла. Три миллиарда команд должны занимать приблизительно секунду, и опыт это подтверждает, но только при оговорённых условиях. При сборке без оптимизации (c++ -O0 loop.cpp) получается примерно секунда. С -O2 компилятор обнаруживает, что i далее нигде не используется, удаляет цикл целиком и печатает почти ноль; чтобы этого не происходило, счётчик объявляют volatile. Это классическая ловушка микробенчмарков на компилируемых языках. Аналогичная программа на Python выполняется около 100 секунд, то есть в сто раз медленнее. Так происходит, поскольку код, написанный на языках низкого уровня, почти один к одному транслируется в инструкции процессору.

Пространственная сложность алгоритма

Вычислительная (или временнáя) сложность показывает, насколько экономно алгоритм расходует процессорное время. Второй характеристикой является объём оперативной памяти. Программы, не помещающиеся в неё, зависают и мешают работе остальных, а часто и не доводят вычисление до конца.

Если программе не хватает оперативной памяти, она пытается использовать файл подкачки, или swap-раздел (от англ. swap, «подкачивать»), расположенный во внешней памяти (на жёстком диске или на SSD-диске). При недостатке оперативной памяти программа начинает перекладывать данные из небольшой, но быстрой оперативной памяти на большой, но медленный диск и по мере необходимости возвращать требуемые данные с диска в память. Это очень медленный процесс. Из-за него программы, вышедшие за пределы оперативной памяти, начинают тратить много процессорного времени и зависать, даже если у них небольшая временна́я сложность. Более того, они могут вытеснять из памяти другие программы, зависающие следом. Если запущенные на компьютере программы заняли не только всю оперативную память, но и файл подкачки, то какая-то из программ завершится аварийно.

Каждый объект в программе занимает некоторый объём памяти, а для хранения всех созданных объектов может потребоваться значительное пространство. Особого внимания требуют массивы, строки и прочие контейнеры, размер которых не фиксирован и зависит от входных данных. Пространственной сложностью алгоритма называется зависимость объёма потребляемой памяти от входных данных. Как и в случае с временной сложностью, в первую очередь представляет интерес не точный объём занятой памяти, а асимптотика, то есть скорость роста без учёта констант и коэффициентов.

Взаимосвязь пространственной и временной сложности алгоритма

Сохранённая вспомогательная информация позволяет тратить меньше времени: память обменивается на скорость. Этот выбор бывает непростым: либо хранить больше данных и меньше вычислять, либо вычислять медленнее, зато уложиться в отведённую память.

Тестирование программы

Код, разделённый на функции, удобно тестировать: для каждой выделенной функции пишутся юнит-тесты.

Необходимо продумать краевые случаи — входные данные, на которых программы отказывают чаще всего:

тип теста	строки	числа	набор данных/массивы
самый маленький тест	пустая строка	0 или минимальное отрицательное число для задачи	пустой набор данных
самый большой тест	самая длинная строка по условию	самое большое положительное число для задачи	набор данных максимального размера
особые случаи	строки со строчными и заглавными буквами строки с кириллицей и латиницей	положительное/отрицательное число ноль четное/нечет число вещественное число	набор с одинаковыми элементами отсортированные наборы неотсортированные наборы

Задача

Дана строка (UTF-8). Требуется найти самый часто встречающийся в ней символ.

Решение 1

Переберём все позиции в строке, для каждой из них ещё раз пройдём по всей строке и на каждом совпадении прибавим к счётчику единицу. Останется найти максимальное из накопленных значений счётчика.

s = 'ababa'
ans = ''
anscnt = 0
for i in range(len(s)):
    nowcnt = 0
    for j in range(len(s)):
        if s[i] == s[j]:
            nowcnt += 1
    if nowcnt > anscnt:
        ans = s[i]
        anscnt = nowcnt
print(ans)

Решение 2

Переберём символы, встречающиеся в строке, для каждого пройдём по всем позициям и на каждом совпадении прибавим к счётчику единицу. Снова найдём максимальное из полученных значений счётчика.

s = 'ababa'
ans = ''
anscnt = 0
for now in set(s):
    nowcnt = 0
    for j in range(len(s)):
        if now == s[j]:
            nowcnt += 1
    if nowcnt > anscnt:
        ans = now
        anscnt = nowcnt
print(ans)

Решение 3

Заведём словарь, в котором ключом служит символ, а значением — число его вхождений. Если символ встретился впервые, для него создаётся элемент словаря со значением ноль, после чего к созданному элементу прибавляется единица.

s = 'ababa'
ans = ''
anscnt = 0
symcnt = {}
for now in s:
    if now not in symcnt:
        symcnt[now] = 0
    symcnt[now] += 1
    if symcnt[now] > anscnt:
        ans = now
        anscnt = symcnt[now]
print(ans)

Сравнение сложности

Обозначим через $N$ длину строки, а через $K$ количество различных символов.

Решение	Время	Дополнительная память
1	$O(N^2)$	$O(1)$
2	$O(NK)$	$O(K)$
3	$O(N)$	$O(K)$

Память здесь учитывается дополнительная, сверх самого входного массива: в противном случае все три решения одинаково требовали бы $O(N)$, и сравнивать было бы нечего. Первое не хранит ничего, кроме счётчиков; второе строит множество различных значений, встреченных в строке, а третье — словарь тех же значений, вследствие чего оба и требуют $O(K)$.

Значение алгоритмов для программиста

Знание алгоритмов способствует эффективному решению задач, встречающихся в работе
Дополнительная готовность к собеседованию
Общая когнитивная тренировка

Свойства алгоритмов

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

Дискретность означает, что алгоритм распадается на отдельные шаги, выполняемые по одному и в определённом порядке, а не сливается в одно неделимое действие. Детерминированность — что на одних и тех же входных данных получается один и тот же результат при любом числе запусков алгоритма. Понятность — что каждый шаг посилен исполнителю и не допускает двоякого толкования, вследствие чего инструкция «посолить по вкусу» в алгоритм не годится. Завершаемость — что работа заканчивается за конечное число шагов, а не продолжается бесконечно. Массовость — что алгоритм написан для целого класса входных данных, а не для единственного набора, ради которого он составлялся. Результативность — что на выходе получается ответ, пусть даже им окажется сообщение о том, что решения нет.

Лайфхаки. Оценка сложности

Чаще всего сложность видна в структуре кода, и несколько признаков покрывают большинство случаев:

Цикл, проходящий по всему массиву, означает линейную сложность
При вложенном цикле необходимо считать суммарное число итераций внутреннего цикла, а не глубину вложенности. Часто получается произведение длин, но не всегда: у решета Эратосфена два вложенных цикла, а работает оно за $ O(n \log\log n) $
Деление пополам, повторяющееся на каждом шаге, означает логарифмическую сложность
Полный перебор, охватывающий все комбинации, означает экспоненциальную сложность

Алгоритмически неразрешимые проблемы

Проблема останова

Существуют задачи, для которых доказано, что решающего их алгоритма не существует; самая известная из них формулируется следующим образом. Пусть даны алгоритм $A$ и входные данные $N$; требуется алгоритм, который по этой паре определяет, остановится ли $A$ на входе $N$ или будет работать бесконечно. Такого алгоритма не существует, и доказывается это от противного, подачей предполагаемого распознавателя на вход ему же самому.

Ресурсы

https://tproger.ru/digest/competitive-programming-practice/
Введение в анализ сложности: https://habr.com/ru/post/196560/
Гейл Макдауэлл «Карьера программиста»

Бонус. Задача. Поиск простых чисел

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

def is_prime(n):
    if n < 2:
        return False
    i = 2
    while i < n:
        if n % i == 0:
            return False
        i = i + 1
    return True

Эту задачу можно решить быстрее, поскольку делители, превышающие $\sqrt n$, проверять необязательно.

def is_prime(n):
    if n < 2:
        return False
    i = 2
    while i * i <= n:
        if n % i == 0:
            return False
        i = i + 1
    return True

С помощью функции is_prime(n) можно найти все простые числа, не превосходящие $n$. Для этого заведём пустой массив smaller_primes и будем проверять на простоту все числа, не превышающие $n$. Если число простое, добавим его в массив smaller_primes, где в конце работы алгоритма и будет содержаться искомый ответ.

def get_smaller_primes(n):
    smaller_primes = []
    for num in range(2, n + 1):
        if is_prime(num):
            smaller_primes.append(num)
    return smaller_primes

Для практики этот способ слишком медленный: делители для каждого числа перебираются заново. Гораздо быстрее работает решето Эратосфена, известное ещё с древности.

Алгоритм состоит в следующем:

Выписываются все целые числа от 0 до $n$. Сразу отмечается, что 0 и 1 не простые (на соответствующих позициях записывается False).
Заводится переменная $\mathrm{num}$, равная первому не рассмотренному простому числу. Изначально она равна 2.
Числа в списке от $2 \cdot \mathrm{num}$ до $n$ с шагом, равным $\mathrm{num}$, помечаются составными. Например, для 2 значением False помечаются чётные числа 4, 6, 8 и так далее.
Далее переменной $\mathrm{num}$ присваивается следующее простое число, то есть следующее не рассмотренное число в списке. Для этого достаточно увеличивать $\mathrm{num}$ с шагом 1, пропуская числа, отмеченные как составные. На первом найденном простом числе достаточно остановиться.
Два предыдущих шага повторяются, пока это возможно.

В коде это выглядит следующим образом:

def eratosthenes(n):
    numbers = list(range(n + 1))
    numbers[0] = numbers[1] = False
    for num in range(2, n):
        if numbers[num]:
            for j in range(2 * num, n + 1, num):
                numbers[j] = False
    return numbers

eratosthenes(9)

[False, False, 2, 3, False, 5, False, 7, False, False]

Простые числа остались на своих местах, а на позициях, занятых составными числами, стоит False. Алгоритм можно ускорить. Для каждого простого числа $p$ начнём отмечать составными числа начиная с $p^2$: всё, лежащее ниже, к этому моменту уже рассмотрено. Получится следующий код:

def eratosthenes_effective(n):
    numbers = list(range(n + 1))
    numbers[0] = numbers[1] = False
    for num in range(2, n):
        if numbers[num]:
            for j in range(num * num, n + 1, num):
                numbers[j] = False
    return numbers

Рассмотрим подробно пример работы алгоритма для $n = 15$.

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 # Запишем числа от 0 до 15

False False 2 3 4 5 6 7 8 9 10 11 12 13 14 15 # Отметим, что 0 и 1 не простые

num = 2 # Пометим все числа, кратные 2, начиная с 4, значением False

False False 2 3 False 5 False 7 False 9 False 11 False 13 False 15

num = 3 # Пометим все числа, кратные 3, начиная с 9, значением False

False False 2 3 False 5 False 7 False False False 11 False 13 False False

num = 5 # Алгоритм можно завершить, так как num**2 больше 15.
              # Все числа, кратные 5 и меньшие 15, уже рассмотрены.

Решето Эратосфена работает за $O(n \log(\log n))$. Доказательство опирается на нетривиальные факты из теории чисел.

Существует метод решения задачи нахождения всех простых чисел, не превосходящих $n$, требующий $O(n)$ операций. Он называется линейным решетом и помечает каждое число как составное только один раз.

Как и прежде, числа перебираются в порядке возрастания, только в отличие от классического решета Эратосфена найденные составные числа не вычёркиваются. Вместо этого для каждого числа $x$ записывается наименьший простой делитель $p$. В программе записанный делитель помещается в ячейку массива $\mathrm{lp}[x]$ (от англ. least prime). Если число простое, его наименьшим простым делителем служит оно само, а если составное, его наименьший простой делитель $p$ уже встречался раньше. Более того, ранее встречалось и число $i$, такое, что $x = i \cdot p$. На шаге $i$ необходимо пометить число $x$ как составное и указать его наименьший простой делитель. Каждое число будет помечено только один раз, на шаге $i = x/p$. Число $i$ может быть выбрано только одним способом, поскольку у любого числа существует только один наименьший простой делитель $p$.

Алгоритм состоит в следующем:

Для каждого числа i в lp[i] хранится минимальный простой делитель этого числа. Заводится массив lp длины n + 1, а также массив primes, в который складываются найденные простые числа.
Числа i перебираются по возрастанию.
Если lp[i] = 0, значит, число i простое, и его необходимо добавить в массив primes.
Рассматриваются все простые числа p, не превосходящие lp[i]. Обновляется lp[p * i] = p.

def get_least_primes_linear(n):
    lp = [0] * (n + 1)
    primes = []
    for i in range(2, n + 1):
        if lp[i] == 0:
            lp[i] = i
            primes.append(i)
        for p in primes:
            x = p * i
            if (p > lp[i]) or (x > n):
                break
            lp[x] = p
    return primes, lp

get_least_primes_linear(8)

([2, 3, 5, 7], [0, 0, 2, 3, 2, 5, 2, 7, 2])

Резюме

От алгоритма требуется шесть свойств: дискретность, детерминированность, понятность, завершаемость, массовость и результативность.
O-нотация описывает, как растёт время работы с ростом объёма данных, отбрасывая константы. Отброшенные множители зависят от процессора и компилятора, характер роста — нет.
На миллионе элементов $O(n)$ обходится в двенадцать миллисекунд, тогда как $O(\log n)$ — меньше чем в микросекунду. На больших данных выбранный алгоритм значит больше, чем любая микрооптимизация.
Пространственная сложность оценивается аналогично, и между временем и занятой памятью почти всегда приходится выбирать.
Прежде чем оптимизировать, необходимо измерить. Оценка сложности показывает, чего следует ожидать, но реальное время определяется измерением.

Задание. Требуется решить задачи и оценить сложность полученных решений: «Решение задач на Python и анализ сложности».

Решение	Время	Дополнительная память
1	\(O(N^2)\)	\(O(1)\)
2	\(O(NK)\)	\(O(K)\)
3	\(O(N)\)	\(O(K)\)

Разработка и применение программного обеспечения в физических исследованиях