Продолжаем говорить о производительности и оптимизации кода. Сегодня поговорим о том, как и зачем оценивать сложность алгоритмов, а также наглядно покажем, как эта сложность влияет на производительность кода.
В прошлой статье мы разбирались, что такое бенчмаркинг кода и как с его помощью оценивать производительность кода в .NET. В этой – поговорим про оценку сложности алгоритмов. А чтобы все было наглядно, вместе попробуем оценить алгоритмы, которые используются для решения задачки на собеседовании в Google.
Задач такого плана полным-полно на платформах типа LeetCode, CodeWars и других. И их ценность не в том, чтобы заучить различные алгоритмы сортировок, которые вы никогда не будете на практике писать самостоятельно, а в том, чтоб увидеть типичные проблемы, с которыми вы можете столкнуться в практических задачах при разработке.
Оценка сложности алгоритмов
Зачем вообще оценивать сложность алгоритмов и какие способы оценки бывают?
Понимать сложность алгоритмов важно по следующим причинам:
без этих знаний вы не сможете отличить суб-оптимальный код от оптимального и оптимизировать его;
каждый средний или большой проект рано или поздно будет оперировать большим объемом данных. Важно, чтоб ваши алгоритмы это предусматривали и не стали бомбой замедленного действия;
если вы не понимаете концепции оценки сложности алгоритмов, есть вероятность, что вы будете писать низкопроизводительный код.
Чаще говорят про оценку алгоритма по времени (time complexity) — сколько времени понадобится для его выполнения. Время выполнения зависит от количества элементарных операций, которые выполняет компьютер.
Для каждого алгоритма можно сделать несколько оценок сложности:
O большое (O(f)) — позволяет оценить верхнюю границу сложности алгоритмов. Это отношение количества входных данных для алгоритма ко времени, за которое алгоритм сможет их обработать. Простыми словами – это максимальное время работы алгоритма при работе с большими объемами данных.
Омега (Ω(f)) — позволяет оценить нижнюю границу сложности — сколько времени займет работа алгоритма в лучшем случае.
Тета (Θ(f)) — позволяет получить “плотную” оценку сложности, то есть такую, при которой скорость работы в худшем и лучшем случае будет пропорциональна одной функции. Применимо не ко всем алгоритмам.
В IT компаниях зачастую обращают внимание на большое O (Big-O notation), поскольку чаще всего достаточно представлять, как быстро будет расти количество операций при увеличении входных данных в худшем случае. Остальные типы оценок используются редко.
В скобках после О указывают функцию, которая ограничивает сложность. При этом n — это размер входных данных. Например, O(n) означает, что сложность алгоритма растёт линейно. В таком случае время выполнения алгоритма увеличивается прямо пропорционально размеру входных данных.
Если представить график распространенных сложностей алгоритмов, они будут выглядеть вот так:
Если условно разделить сложности на зоны, то сложности вида O(log n), O(1) или O(C) можно будет отнести к зоне «Отлично». Такие алгоритмы вне зависимости от объемов данных будут выполняться очень быстро — практически мгновенно.
Алгоритмы сложности O(n) можно отнести к зоне «Средне» — алгоритмам, сложность которых растет предсказуемо и линейно. Например, если 100 элементов ваш алгоритм обрабатывает за 10 секунд, то 1000 он обработает примерно за 100 секунд. Не лучший результат, но предсказуемый.
Алгоритмы из красной зоны со сложностями 
и выше трудно отнести к высокопроизводительным. НО! тут все сильно зависит от объемов входных данных. Если вы уверены, что у вас всегда будет небольшой объем данных (например, 100 элементов), и обрабатываться он будет в приемлемое для вас время, то все в порядке, такие алгоритмы тоже можно использовать. Но если же вы не уверены в постоянности объемов данных (может прийти и 10 000 элементов вместо 100) — лучше все-таки задуматься над оптимизацией алгоритмов.
Добавим, что оценка сложности по времени — это теоретическая оценка. Она не учитывает внутренние оптимизации и кеш процессора, в реальности картина может отличаться.
Оценка сложности по памяти
Оценку сложности алгоритмов следует проводить не только по времени выполнения, но и по потребляемой памяти — часто про это забывают во время изучения темы.
Например, для ускорения вычислений можно создать какую-нибудь промежуточную структуру данных типа массива или стека для ускорения алгоритма и кеширования результатов. Это приведет к дополнительным затратам памяти, но при этом может существенно ускорить вычисления.
Сложность по памяти также называют пространственной сложностью (space complexity) и для оценки используют такую же нотацию как для времени — большое O. Например, сложность по памяти
, означает что в худшем случае для алгоритма не понадобится больше памяти, чем пропорционально
.
Важно отметить, что при оценке сложности алгоритмов по памяти используют упрощенную модель работы с памятью, так называемою RAM-машину. Это означает, что мы можем читать и записывать любую ячейку памяти за время одной операции. Таким образом, время вычислительных операций и операций с памятью становится одинаковым, что упрощает анализ. Это ближе всего к работе с оперативной памятью, и, например, не учитывает регистры процессора, работу с диском, garbage collector и много чего еще.
Немного практики: правила расчета сложности на пальцах
Мы приводим примеры на C#, хотя здесь можно было бы обойтись и псевдокодом. Надеемся, что они будут понятны.
Пример 1:
Возьмем для начала простой алгоритм присвоения переменной:
private void Alg1(int[] data, int target)
{
var a = data[target];
}Какова его сложность по времени и по памяти?
С одной стороны, нас может ввести в заблуждение массив данных data неизвестной размерности. Но брать его в расчет при оценке сложности внутреннего алгоритма будет некорректно.
Правило 1: внешние данные не учитываются в сложности алгоритма.
Получается, наш алгоритм состоит только из одной строчки:
var a = data[target];
Доступ к элементу массива по индексу — известная операция со сложностью O(1) или O(C). Соответственно, и весь алгоритм по времени у нас займет O(1).
Дополнительная же память выделяется только под одну переменную. А значит, объем данных, которые мы будем передавать (хоть 1 000, хоть 10 000), не скажется на финальном результате. Соответственно, сложность по памяти у нас так же — O(1) или O(C). Такие алгоритмы называются алгоритмами на месте (in-place). Они могут использовать дополнительную память, но её размер не зависит от количества входных данных.
Для упрощения записи дальше я везде буду писать O(C) вместо O(1), C в этом случае — это константа. Она может равняться 1, 2 или даже 100 — для современных компьютеров это число не принципиально, поскольку и 1, и 100 операций выполняются практически за одно и то же время.
Пример 2:
Рассмотрим второй алгоритм, очень похожий на первый:
private void Alg2(int[] data, int target)
{
var a = data[target];
var b = data[target + 1];
}Влияет ли размерность входного массива data на количество операций в нем? Нет.
А на выделенную память? - Тоже нет.
Сложность этого алгоритма по времени выполнения можно было бы оценить как O(2*C) — поскольку у нас выполняется в два раза больше операций, чем в предыдущем примере, 2 присваивания вместо 1. Но у нас и на этот счет есть правило:
Правило 2: опускать константные множители, если они не влияют на результат кардинальным образом.
Если принять это правило в расчет, сложность этого алгоритма будет такой же, как и в первом примере — O(C) по времени и O(C) по памяти.
Пример 3:
В третьем примере добавим в наш алгоритм цикл для обработки данных:
private int Alg3(int[] data)
{
var sum = 0;
for (int i = 0; i < data.Length; i++)
{
sum += data[i];
}
return sum;
}Как мы видим, количество операций, которые будет выполнять цикл, напрямую зависит от количества входных данных: больше элементов в data — больше циклов обработки потребуется для получения финального результата.
Казалось бы, если взять в учет каждую строчку кода нашего алгоритма, то получилось бы что-то такое:
private int Alg3(int[] data)
{
var sum = 0; // O(C)
for (i=0; i < data.Length; i++) // O(n)
{
sum += data[i]; // O(C)
}
return sum;
}И тогда финальная сложность алгоритма получится O(C)+O(n). Но тут опять вмешивается новое правило:
Правило 3: опускать элементы оценки, которые меньше максимальной сложности алгоритма.
Поясню: если у вас O(C)+O(n), результирующая сложность будет O(n), поскольку. O(n) будет расти всегда быстрее, чем O(C).
Еще один пример — 
. При такой сложности у нас n2 всегда растет быстрее, чем N, а значит O(n) мы отбрасываем и остается только 
.
Итак, сложность нашего третьего примера — O(n). По памяти без изменений — О(С).
Пример 4:
В четвертом примере посчитаем сумму всех возможных пар значений из массива:
private int Alg4(int[] data)
{
var sum = 0;
for (int i = 0; i ‹ data.Length; i++)
{
for (int j = 0; j ‹ data.Length; j++)
{
sum += data[i]*data[j];
}
}
return sum;
}И для его обработки нам теперь нужно два цикла. Оба этих цикла будут зависеть от размерности входных данных data.
Правило 4: вложенные сложности перемножаются.
Сложность внешнего цикла в нашем примере — O(n), сложность внутреннего цикла — O(n). Согласно правилу, две эти сложности должны быть умножены. В результате максимальная сложность всего алгоритма выйдет равной 
. По памяти без изменений — О(С).
Пример с подвохом:
Подадим на вход двумерный массив и посчитаем сумму значений.
private int Alg4_tricky_case(int[][] data)
{
var sum = 0;
for (int i = 0; i < data.Length; i++)
{
for (int j = 0; j < data.Length; j++)
{
sum += data[i][j];
}
}
return sum;
}Снова видим вложенные циклы — и если во входном массиве N x M элементов, то есть сложность O(N * M), и кажется, что это эквивалентно 
. Но на самом деле, нет — в данном случае на вход просто подается N * M элементов и время пропорционально N * M, то линейное O(n).
Пример 5:
А что мы видим тут? Цикл — уже известная нам сложность – O(n). Но внутри вызывается функция Alg4() из предыдущего примера:
private int Alg5(int[] data)
{
var sum = 0;
for (int i = 0; i ‹ data.Length; i++)
{
sum += Alg4(data);
}
return sum;
}Если мы вспомним ее сложность 
, а также правило 4, то получим, что сложность этого алгоритма — 
при всей его визуальной минималистичности. Со сложностью по времени без изменений.
Правило 5: включайте в оценку общей сложности алгоритма оценки всех вложенных вызовов функций.
Именно поэтому важно понимать сложность методов синтаксического сахара вроде LINQ, базовых коллекций и типов данных — чтоб была возможность оценить, как метод будет вести себя при увеличении объемов данных. При использовании их в коде без понимания внутреннего устройства, вы рискуете получить очень высокую сложность алгоритма, который будет захлебываться при увеличении входящих данных.
Приведу пример минималистичного алгоритма, который выглядит хорошо и компактно (ни в коем случае не претендует на эталонный код), но станет бомбой замедленного действия при работе с большими объемами данных:
private List<int> Alg6(int[] data)
{
List<int> dups = new List<int>();
for (var i = 0; i < data.Length; i++)
{
var currentItem = data[i];
var newArr = data.Skip(i + 1).ToArray();
var duplicates = newArr.Where(x => newArr.Contains(currentItem));
dups.AddRange(duplicates);
}
return dups;
}Что мы тут видим? Цикл = O(n), Where = O(n), Contains = O(n), так как newArr – это массив.
Итого сложность такого алгоритма будет от 
по времени выполнения.
ToArray() будет выделять на каждой итерации дополнительную память под копию массива, а значит сложность по памяти составит O(n).
Задачка от Google
Возьмем для нашего финального оценивания задачку, которую дают на собеседовании в Google.
Подробный разбор задачи и алгоритмы решения можно посмотреть вот в этом видео от Саши Лукина. Рекомендую посмотреть его перед продолжением чтения этой статьи.
Вкратце, цель алгоритма — найти в отсортированном массиве два любых числа, которые в сумме дали бы нам искомое число target.
Решение 1: полный проход по массиву
public static int[] FindPairWithFullWalkthrough(int[] data, int target)
{
for (int i = 0; i < data.Length; i++)
{
for (int j=i+1; j < data.Length; j++)
{
if (data[i] + data[j] == target)
return new[] { data[i], data[j] };
}
}
return new int[0];
}Сложность по времени: 
O(n2)
Сложность по памяти: O(С)
Это решение в лоб. Не самое оптимальное, поскольку время быстро растет при увеличении количества элементов, но зато дополнительную память мы особо не потребляем.
Решение 2: используем HashSet
public static int[] FindPairUsingHashSet(int[] data, int target)
{
HashSet<int> set = new HashSet<int>();
for (int i = 0; i < data.Length; i++)
{
int numberToFind = target - data[i];
if (set.Contains(numberToFind))
return new [] { data[i], numberToFind };
set.Add(data[i]);
}
return new int[0]
}Проходимся по массиву и элементы, которые мы уже проверили добавляем, в HashSet. Если HashSet содержит недостающий для суммы элемент, значит все хорошо , мы закончили и можем возвращать результат. Добавление и поиск в HashSet делается за время O(C).
Сложность по времени: O(n)
Сложность по памяти: O(n)
Это как раз пример того, как можно выиграть в производительности, выделив дополнительную память для промежуточных структур.
Решение 3: используем бинарный поиск
public static int[] FindPairUsingBinarySearch(int[] data, int target)
{
for (int i = 0; i < data.Length; i++)
{
int numberToFind = target - data[i];
int left = i + 1;
in right = data.Length - 1;
while (left <= right)
{
int mid = left + (right - left) / 2;
if (data[mid] == numberToFind)
{
return new[] { data[i], data[mid] };
}
if (numberToFind < data[mid])
{
right = mid - 1;
}
else
{
left = mid + 1;
}
}
}
return new int[0];
}Алгоритм бинарного поиска имеет известную сложность — O(log(n)). O(n) нам добавилась от внешнего цикла for, а все, что внутри цикла while — это и есть алгоритм бинарного поиска. Согласно Правилу 4 сложности перемножаются.
Сложность по времени: O(n*log(n))
Сложность по памяти: O(С)
Решение 4: используем метод двух указателей
public static int[] FindPairUsingTwoPointersMethod(int[] data, int target)
{
int left = 0;
int right = data.Length - 1;
while (left < right)
{
int sum = data[left] + data[right];
if (sum == target) return new[] { data[left], data[right] };
if (sum < target)
{
left++;
}
else
{
right--;
}
}
return new int[0];
}Двигаем левый и правый указатели к центру, пока они не сойдутся или не найдется пара подходящих нам значений.
Сложность по времени: O(n)
Сложность по памяти: O(С)
И это — самый оптимальный из всех вариантов решения, не использующий дополнительной памяти и совершающий наименьшее количество операций.
Бенчмаркинг решений
Теперь, зная сложности всех четырех вариантов решения, попробуем провести бенчмаркинг этого кода и посмотреть, как алгоритмы будут вести себя на различных наборах данных. В этом поможет информация из предыдущей нашей статьи.
Результаты будут следующими:
Что мы тут видим?
За baseline решения мы берем прямой проход массиву FindPairWithFullWalkthrough. На 10 объектах он отрабатывает в среднем за 20 наносекунд и занимает второе место по производительности.
Быстрее на малом объеме данных выполняется только наш самый оптимальный вариант решения — FindPairUsingTwoPointersMethod.
Вариант же с HashSet занял в 8 раз больше времени для работы с малым объемом данных и потребовал выделения дополнительной памяти, которую потом нужно будет собрать Garbage Collector-у.
На 1 000 же элементов вариант с полным проходом по циклу (FindPairWithFullWalkthrough) начал заметно отставать от остальных алгоритмов. Причиной этому — его сложность O(n^2), которая растет заметно быстрее всех остальных сложностей.
На 10 000 элементах алгоритму с полным проходом потребовалось и вовсе 9,7 секунды для завершения расчетов, в то время как остальные справлялись за 0.1 секунды и меньше. А самый оптимальный вариант решения и вовсе нашел решение за 3 миллисекунды.
Почему же бинарный поиск обогнал HashSet? Ведь в теории O(n * log(n)) должен быть медленнее O(n)? Дело в том, что на реальных, а не теоретических компьютерах выделение и освобождение работает не за одинаковое время – то и дело включается Garbage collector. Это подтверждают значения стандартного отклонения (StdDev) в бенчмарке HashSet.
Заключение
Мы разобрались, как оценивать сложность алгоритмов, а также узнали, как с помощью BenchmarkDotNet проследить связь между сложностью алгоритмов и временем выполнения кода. Это позволит еще до выполнения бенчмаркинга приблизительно оценить — хороший код вы написали или нет.
