Перед тем, как перейти к оцениванию алгоритмов, давайте немного подумаем о том, что это вообще такое и какими свойствами алгоритмы обладают.

Алгоритм — это набор формальных инструкций для решения какой-то задачи. Алгоритмы не могут существовать без чего-то или кого-то, кто будет их исполнять, то есть исполнителя. Исполнителем алгоритмов может быть, например, ваш ПК, а некоторые алгоритмы можете выполнять и вы сами. У алгоритма также есть несколько свойств:

Универсальность

Алгоритм можно применять к различным входным данным, если они однородны. Например, если мы имеем алгоритм сложения чисел, то мы можем применять его не только к числам «2», «6» и «9», но вообще к любым.

Раздельность (дискретность)

Это свойство характеризует структуру алгоритма: каждый алгоритм должен быть представлен как решение задачи за последовательное выполнение заранее определённых простых шагов. Каждый из этих шагов выполняется строго после завершения предыдущего. Например, если мы имеем алгоритм «заварить чай», то не можем во время наливания в чайник воды закрыть крышку. Точнее можем, но тогда останемся не очень довольны результатом его выполнения.

Определённость

Каждый из шагов алгоритма формально описан, а любые разночтения исключены. Это свойство критично для того, чтобы разные исполнители точно делали то, что от них хотят, особо не задумываясь. В примере того же алгоритма заваривания чая нам стоит чётко указать, какой конкретно чай нужно заваривать, потому что исполнитель «Игорь» может заварить зелёный, а «Олег» — чёрный.

Результативность

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

Если рассматривать примеры из жизни, то можно заметить, что количество шагов, нужных для выполнения некоторых алгоритмов, меняется вместе со входными данными. Тот же алгоритм «заварить чай» всегда занимает одно и то же количество времени, а вот алгоритм «помыть посуду» напрямую зависит от количества предметов, которые нужно помыть. Чем их больше, тем больше времени на это уйдёт, притом каждая новая тарелка удлиняет процесс на какое-то определённое одинаковое количество времени. А значит, каждые n тарелок будут увеличивать количество шагов на n. Если мы имеем дело с алгоритмом «Выбрать два цвета для ремонта»... То мы, скорее всего, будем брать каждый цвет и прикладывать его к каждому другому цвету, пока не подберем то, что ищем. Тогда каждый раз, когда мы добавляем в подборку цветов новый, количество шагов в нашем алгоритме увеличивается на n — количество цветов, которые уже были в подборке. Тогда добавление n цветов даст нам общий прирост в n*n или n² шагов.

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

Правила оценивания алгоритмов с помощью O-нотации

1. Самое важное: при оценке сложности алгоритма мы всегда берём худший случай из всех возможных. В примере с подбором цветов мы будем оценивать алгоритм так, как будто цвета, которые нам подходят — это два последних цвета в списке.

2. Мы считаем только зависимость количества операций от количества входных данных, при этом если мы делаем несколько операций над каждым входным предметом, то количество этих операций мы не учитываем. Например, чтобы помыть тарелку, нам нужно её взять, намылить, прополоскать и положить в чистое — всего 4 операции. При оценивании нам неважно, что при добавлении двух грязных тарелок количество операций увеличится на 8. Нам важно, что количество операций возрастает линейно, то есть каждая тарелка добавляет одинаковое количество операций.

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

Держа в уме эти правила, мы можем оценить наши алгоритмы из примеров:

1. Асимптотика «Заварить чай» — О(1) (вот так и выглядит O-нотация — просто большая буква «О» и асимптотика в скобках за ней). Почему именно так? Потому что в этой задаче нет зависимости от входных данных — мы всегда выполняем одинаковое, константное количество шагов.

2. Асимптотика «Помыть посуду» — O(n), так как время выполнения алгоритма линейно возрастает в зависимости от количества входных данных — n тарелок будет занимать в n раз больше времени, чем одна. А ещё из примера во втором правиле видно, что хоть мы и можем записать сложность как O(4n), это не совсем верно. Ведь эта четвёрка действий постоянна и не влияет на рост количества операций, хотя и влияет на количество операций в целом.

3. Асимптотика «Выбрать два цвета для ремонта» — O(n²). Из первого и самого важного правила видим, что апеллировать к «Да мне и первые два цвета подойдут, тут O(1) будет!» нельзя, потому что мы смотрим на худшие из всех возможных случаев.

Пример из фронтенда

Допустим, дизайнер нарисовал интересный макет, согласно которому мы должны показывать пользователю два рекламных баннера в сетке, состоящей из колонок по 20 пикселей каждая. Нам нужно всего лишь выбирать два разных по ширине баннера, которые идеально вписываются в сетку на экране браузера пользователя, и их выводить. Возможных баннеров разных размеров — сотни, а различных экранов у пользователей — тысячи!

Самое наивное решение — поочерёдно брать пару баннеров из всех возможных и смотреть на сумму их ширины. Берём их, если они подходят. А если не подходят — идём дальше и сравниваем следующие

function findBanners(banners, userWidth) {
  for (let i = 0; i < banners.length; i++) {
    for (let j = 0; j < banners.length; j++) {
      if (banners[i].width + banners[j].width === userWidth) {
        return [banners[i], banners[j]];
      }
    }
  }
}

Это решение по сложности будет таким же, как и в «Выбрать два цвета для ремонта», O(n²), потому что каждый новый баннер заставит нас делать по n новых итераций, чтобы сравнить его с предыдущими. Попробуем упростить решение этой задачи.

Для нового решения нам нужно хранить все баннеры в строго отсортированном по возрастанию массиве. Допустим, у нас есть массив из баннеров с шириной [40, 50, 100, 300, 700], а у пользователя вмещается сетка шириной 150 пикселей. Тогда возьмём два самых крайних элемента — 700 и 40. В сумме они дают 740, что значительно больше ширины пользовательского экрана. Возьмём следующий с конца элемент — 300, а новая сумма будет равна 340 — всё ещё больше, чем нужно. Посмотрим на элемент левее — 100. Теперь новая сумма меньше той, что нам нужна — 140. Чтобы её увеличить, возьмём следующий после 40 элемент — 50 и получим, наконец, нужные нам баннеры!

При добавлении одного баннера в отсортированный массив нам в худшем случае придётся сделать на одну итерацию больше, чем без него. А значит, мы пришли к линейному алгоритму, который работает за O(n)!

function findBanners(banners, userWidth) {
  let leftPointer = 0;
  let rightPointer = banners.length - 1;

  while (leftPointer < rightPointer) {
    const bannersWidth = banners[leftPointer].width + banners[rightPointer].width;

    if (bannersWidth === userWidth) {
      return [banners[leftPointer], banners[rightPointer]];
    }

    if (bannersWidth > userWidth) {
      rightPointer--;
    } else {
      leftPointer++;
    }
  }
}

Задача о коммивояжёре

Конечно, O(n²) — далеко не худшая сложность из тех, которые мы можем получить. В теории вычислений есть очень известная своей алгоритмической сложностью задача — задача коммивояжёра. В самой простой её постановке нам нужно найти минимальный по длине путь между n городами. Для примера возьмём четыре города. В наивной её реализации нам нужно поискать все возможные длины маршрутов (взять один из четырёх городов, потом соединить его с тремя оставшимися, продлить маршрут в какой-то из двух городов и заехать в оставшийся один город — всего 4 * 3 * 2 * 1 = 24 возможных маршрута) и выбрать из них минимальный. А если нам нужно посчитать длину маршрута между 10 городами, потребуется уже 10 * 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1 = 3628800 операций! Можно заметить, что формулу поиска перестановок можно сложить в факториал — получится 10!. Сложность такого алгоритма оценивается в O(n!), так как каждый новый город добавит нам n * предыдущее решение операций. Если коммивояжёр вдруг захочет оптимально посетить 15 городов, скорее всего, ему это не удастся: либо его уволят раньше, либо какой-то из этих городов уже перестанет существовать.

Казалось бы, если оптимизировать алгоритмы так просто, как на предыдущем примере, неужели коммивояжёр не может считать свой маршрут быстрее? В теории вычислений на этот вопрос нет ответа — задача всё ещё является нерешённой.

Конечно, есть и другие оценки, которые мы не рассмотрели в этой главе, но про них мы поговорим в следующих главах.