Как растёт стоимость (Big-O) — Примеры

Пример 1 — От вложенного цикла к одному проходу

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

function sharesAny(a: number[], b: number[]): boolean {
  for (const x of a) {
    for (const y of b) {
      if (x === y) return true;
    }
  }
  return false;
}

Решение

function sharesAny(a: number[], b: number[]): boolean {
  const seen = new Set(a);
  for (const y of b) {
    if (seen.has(y)) return true;
  }
  return false;
}

//    100 элементов:    10 000 вложенных  ->    100 с множеством
//  1 000 элементов: 1 000 000            ->  1 000
// 10 000 элементов: 100 000 000          -> 10 000

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

Пример 2 — Вход, превращающий среднее в худший случай

Сортировка разбивает список вокруг первого элемента, и замеры ниже сделаны на случайном входе и на уже отсортированном. Скажите, в каком классе каждый запуск и в чём исправление.

function quickSort(xs: number[]): number[] {
  if (xs.length < 2) return xs;
  const [pivot, ...rest] = xs;
  const lower = rest.filter((x) => x < pivot);
  const higher = rest.filter((x) => x >= pivot);
  return [...quickSort(lower), pivot, ...quickSort(higher)];
}

// случайный вход, 10 000 элементов:    12 мс
// отсортированный вход, 10 000:       480 мс
// отсортированный вход, 20 000:     1 900 мс

Решение

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

исправление: выбирать опорный элемент не по позиции — середину или случайный

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