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

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

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

Дан массив целых чисел длины $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 Бинарный поиск

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

arr = [x for x in range(10_000)]
x = 999

%timeit find_element(arr, x)

37.4 µs ± 1.98 µs per loop (mean ± std. dev. of 7 runs, 10,000 loops each)

%timeit binary1.39 µs ± 44 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)1.39 µs ± 44 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)_search(arr, x)

1.39 µs ± 44 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)

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

В О-нотации не учитываются константы и коэффициенты. То есть если в алгоритме совершается $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 [с] $$

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

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

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

# 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;
}

Каждая итерация цикла состоит из трёх действий: прибавить единицу, проверить условие и переместиться обратно к началу цикла. Три миллиарда команд должны занимать приблизительно 1 секунду. Программа на C++ работает почти столько же времени. А вот аналогичная программа на Python выполняется около 100 секунд, то есть в сто раз медленнее. Так происходит, поскольку код на языках низкого уровня почти один к одному транслируется в инструкции процессору.

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

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

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

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

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

Типичная ситуация: мы сохранили вспомогательную информацию, чтобы тратить меньше времени, то есть «обменяли» память на скорость. При решении задач вам порой придётся делать непростой выбор: либо сохранять больше данных, чтобы уменьшить объём вычислений; либо считать медленнее, но сэкономить память. Следует помнить о том, что слишком большой расход памяти может привести к тому, что программа завершится с ошибкой. Или её производительность ухудшится из-за использования файла подкачки.

Как тестировать свою программу

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

Краевые случаи:

Задача

Дана строка (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)

a

Решение 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)

a

Решение 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)

a

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

N - длина строки, К - кол-во различных символов

Зачем программисту алгоритмы

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

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

• Дискретность
• Детерминированность
• "Понятность"
• Завершаемость
• Массовость
• Результативность

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

• Видишь цикл - сложность линейная
• Видишь вложенный цикл - сложность полиномиальная, степень - глубина вложенности
• Видишь деление пополам - сложность логарифмическая
• Видишь полный перебор - сложность экспоненциальная

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

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

• Допустим, что у нас есть алгоритма $A$ и входные данные $N$. Нужен такой алгоритм, который скажет, остановится ли $A$ на входных данных $N$.
• Доказательство: от противного с подачей этого алгоритма на вход самому себе

Ресурсы

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

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

def is_prime(n):
    if n == 1:
        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 == 1:
        return False
    i = 2
    while i * i <= n:
        if n % i == 0:
            return False
        i = i + 1
    return True

C помощью функции 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 пометим значением c чётные числа — 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. Алгоритм можно оптимизировать. Для каждого простого числа pp начнём отмечать числа, начиная с $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] — минимальный простой делитель числа 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])