Big-O нотация и сложност на алгоритмите в JavaScript

Проблем

Ще издържи ли при милион?

Магазинът подписа договор с голям доставчик. След месец каталогът става от 1 000 на 1 000 000 продукта. В кода има шест функции, през които минава всеки продукт или всяко плащане:

първата цена в списъка (за банера на началната страница);
търсене на цена в подредения ценоразпис;
сумата на цените (за отчета);
подреждане на цените (за страницата „от най-евтиното“);
проверката за двойни плащания от предишния урок;
всички комбинации от продукти, които се побират в бюджета на клиента.

Кои ще издържат? Данни с милион продукта още няма, а секундите на твоя лаптоп и без това лъжат. Трябва да познаеш от кода. Да броиш точно всяка стъпка, както с n(n − 1) / 2, е бавно. А и подробностите не са важни: важно е как расте работата.

Идеята

Big-O: какво прави удвояването

Big-O е кратко име за това как расте броят операции, когато расте n (колко са данните). Не казва секунди, а форма: какво става с работата, когато данните се удвоят.

Клас	Име	Пример от магазина	n се удвоява → работата
O(1)	константа	първата цена	не се сменя
O(log n)	логаритъм	търсене в подредения ценоразпис	една стъпка повече
O(n)	линейна	сумата на цените	×2
O(n log n)	„n лог n“	подреждане	малко над ×2
O(n²)	квадратна	двойните плащания	×4
O(2ⁿ)	експоненциална	всички комбинации в бюджета	на квадрат

Ето и шестте функции. Цените са в евроцентове, за да са цели числа:

function firstPrice(prices) {
  return prices[0];
}

function total(prices) {
  let sum = 0;
  for (const p of prices) {
    sum += p;
  }
  return sum;
}

function doublePayments(ids) {
  let found = 0;
  for (let i = 0; i < ids.length; i++) {
    for (let j = i + 1; j < ids.length; j++) {
      if (ids[i] === ids[j]) {
        found++;
      }
    }
  }
  return found;
}

firstPrice прави една стъпка, колкото и цени да има. total прави по една на цена. doublePayments прави по една на двойка.

Виж го

O(log n): колко пъти делиш на две

Търсенето в подредения ценоразпис гледа средата. Ако търсената цена е по-голяма, лявата половина изобщо не трябва и се изхвърля. Иначе се изхвърля дясната. Така на всяка проверка остава половината:

function indexOf(sorted, price) {
  let lo = 0;
  let hi = sorted.length - 1;
  while (lo <= hi) {
    const mid = Math.floor((lo + hi) / 2);
    if (sorted[mid] === price) {
      return mid;
    } else if (sorted[mid] < price) {
      lo = mid + 1;
    } else {
      hi = mid - 1;
    }
  }
  return -1;
}

Колко проверки, ако цената я няма? Колкото пъти можеш да разделиш n на две, докато не остане нищо. Това е логаритъмът: log₂ n е „колко пъти делиш на две“.

for (const n of [1000, 100000, 1000000, 1000000000]) {
  let halvings = 0;
  for (let left = n; left > 0; left = Math.floor(left / 2)) {
    halvings++;
  }
  console.log(n + " → " + halvings);
}

1000 → 10
100000 → 17
1000000 → 20
1000000000 → 30

Хиляда пъти повече цени (от 1 000 на 1 000 000) е само 10 проверки повече. Удвояването добавя една. Затова O(log n) почти не расте.

Повече за границите на двоичното търсене (и къде се бърка с единица) ще видиш в урока „Двоично търсене“.

Виж го

O(n log n) и O(2ⁿ)

Подреждането ползва вградения sort:

function sortedPrices(prices) {
  return [...prices].sort((a, b) => a - b);
}

Сравнението (a, b) => a - b е задължително. Без него sort подрежда числата като текст: [1299, 450, 3999].sort() дава [1299, 3999, 450], защото „1“ е преди „4“.

Добрите алгоритми за подреждане разделят масива на половини (log n нива) и на всяко ниво минават всичко веднъж (n стъпки). Затова са O(n log n). Как точно, ще видиш в урока за merge sort.

Комбинациите в бюджета: за всеки продукт има два избора, „взимам“ или „не взимам“. Затова combos вика себе си два пъти:

function combos(prices, i, sum, budget) {
  if (i === prices.length) {
    return sum <= budget ? 1 : 0;
  }
  return combos(prices, i + 1, sum, budget)
    + combos(prices, i + 1, sum + prices[i], budget);
}

С 1 продукт комбинациите са 2, с 2 са 4, с 3 са 8. Всеки нов продукт удвоява всичко, което е имало досега. Това е O(2ⁿ).

Всичките шест, пуснати върху пет цени и пет плащания:

const prices = [1299, 450, 3999, 899, 2450];
const sorted = sortedPrices(prices);
const payments = [100231, 100232, 100233, 100232, 100234];
console.log("Първата цена: " + firstPrice(prices));
console.log("2450 е на място " + indexOf(sorted, 2450));
console.log("Сумата: " + total(prices));
console.log("Най-евтина: " + sorted[0] + ", най-скъпа: " + sorted[4]);
console.log("Двойни плащания: " + doublePayments(payments));
console.log("Комбинации до 5000: " + combos(prices, 0, 0, 5000));

Първата цена: 1299
2450 е на място 3
Сумата: 9097
Най-евтина: 450, най-скъпа: 3999
Двойни плащания: 1
Комбинации до 5000: 18

Виж го

Какво прави удвояването

function combos(prices, i, sum, budget) {
  if (i === prices.length) {
    return sum <= budget ? 1 : 0;
  }
  return combos(prices, i + 1, sum, budget)
    + combos(prices, i + 1, sum + prices[i], budget);
}

function indexOf(sorted, price) {
  let lo = 0;
  let hi = sorted.length - 1;
  while (lo <= hi) {
    const mid = Math.floor((lo + hi) / 2);
    if (sorted[mid] === price) {
      return mid;
    } else if (sorted[mid] < price) {
      lo = mid + 1;
    } else {
      hi = mid - 1;
    }
  }
  return -1;
}

function doublePayments(ids) {
  let found = 0;
  for (let i = 0; i < ids.length; i++) {
    for (let j = i + 1; j < ids.length; j++) {
      if (ids[i] === ids[j]) {
        found++;
      }
    }
  }
  return found;
}

Стъпка по стъпка, с думи

Първата цена: една стъпка при 4 цени и при 8. Работата не зависи от n: O(1).
Двоичното търсене гледа средата и изхвърля половината. 4 → 2 → 1 са 3 проверки, 8 → 4 → 2 → 1 са 4. Двойно повече цени, една проверка повече: O(log n).
Сумата минава всяка цена по веднъж: 4 и 8 стъпки. Двойно повече цени, двойно повече работа: O(n).
Подреждането слива на нива (тук merge sort, както в Bench). Нивата са log n, на всяко най-много n сравнения: 5 → 16. O(n log n).
Двойните плащания: всяко с всяко след него. 6 → 28: триъгълникът расте в две посоки. O(n²).
Комбинациите в бюджета: всеки продукт е „взимам“ или „не“, и всеки нов ги удвоява. 16 → 256: с 8 продукта работата е тази за 4, на квадрат. O(2ⁿ).

Шестте класа при 4 и при 8 цени. Всяко кубче е една стъпка, точно колкото брои Bench. O(1) не мърда. O(log n) добавя една лента. O(n) се удвоява. O(n log n) се удвоява и получава още едно ниво. O(n²) расте в две посоки. O(2ⁿ) от квадрат 4 × 4 става квадрат 16 × 16.

Идеята

Константите и малките членове падат

Отчетът за двойните плащания прави n(n − 1) / 2 = n²/2 − n/2 стъпки. Защо е O(n²), а не O(n²/2 − n/2)?

По-малкият член изчезва, когато n расте:

n	n²/2	n/2	колко е n/2 от всичко
10	50	5	10%
1 000	500 000	500	0,1%
100 000	5 000 000 000	50 000	0,001%

Константата не сменя формата. n²/2 и n² растат еднакво: двойно повече данни, четири пъти повече работа. Константата е като по-бавна машина: сменя секундите, но не и това какво става при удвояване. А секундите вече знаеш, че лъжат.

Затова Big-O пази само най-бързо растящия член, без числото пред него: 3n + 5 е O(n), n²/2 − n/2 е O(n²), 2n log n + 7n е O(n log n).

По-точно, за любопитните

Точното определение: f(n) е O(g(n)), ако има константа c и праг n₀, такива че f(n) ≤ c · g(n) за всяко n ≥ n₀. Тоест от някое n нататък f не расте по-бързо от g, с точност до константа. Затова O(n) е и O(n²) (горна граница е), но казваме най-тясната. Има и Θ (точно толкова) и Ω (поне толкова). В разговори и на интервюта „O(n)“ обикновено значи Θ(n).

Основата на логаритъма също не се пише: log₂ n и log₁₀ n се различават с константа (log₂ n ≈ 3,32 · log₁₀ n).

Виж го

Шестте криви в браузъра

Пусни шестте функции на Bench. Оста е логаритмична: всяка черта е ×10. O(n) е права линия, O(n²) е два пъти по-стръмна, а O(2ⁿ) излита веднага.

Първата цена O(1)
Двоично търсене O(log n)
Сумата на цените O(n)
Подреждане (merge sort) O(n log n)
Всяка двойка поръчки O(n²)
Всички комбинации в бюджета O(2ⁿ)

Алгоритъм	n = 10	n = 1000	n = 100 000
Първата цена	1	1	1
Двоично търсене	4	10	17
Сумата на цените	10	1000	100 000
Подреждане (merge sort)	21	8709	1 536 371
Всяка двойка поръчки	45	499 500	≈ 4 995 000 000
Всички комбинации в бюджета	1024	≈ 10³⁰¹	≈ 10³⁰¹⁰²

Кодът се пуска в твоя браузър на JavaScript. Броят операции е същият на всеки език, защото алгоритъмът е същият. Времето зависи от машината, затова е само за сравнение. „≈“ е оценка по кривата: толкова голямо n не пускаме, за да не замръзне страницата.

Отговорът за милиона продукта: първата цена, търсенето, сумата и подреждането ще издържат. Двойните плащания стават 500 милиарда стъпки и трябва да минат към множеството от предишния урок. А всички комбинации на милион продукта не може да се изброят на никой компютър: 2 на степен милион е число с 301 030 цифри.

По-точно, за любопитните

Какво ползва вграденото подреждане на всеки език. Array.prototype.sort във V8 (Chrome, Node) е TimSort от 2018 г. Стандартът не казва кой алгоритъм, само че от ES2019 подреждането е стабилно. Bench брои сравненията на merge sort, защото вграденото не може да се преброи отвън. Класът е същият.

Пробвай

Предвиди изхода

Външният цикъл минава n = 8 пъти. Вътрешният дели на две, докато не остане нищо. Какво печата програмата?

const n = 8;
let steps = 0;
for (let i = 0; i < n; i++) {
  for (let left = n; left > 0; left = Math.floor(left / 2)) {
    steps++;
  }
}
console.log(steps);

Отговор

Пробвай

Намери скрития цикъл

Функцията брои различните клиенти в поръчките на месеца. Има само един цикъл, а при 100 000 поръчки е бавна като отчета за двойните плащания:

function uniqueCustomers(orders) {
  const seen = [];
  for (const customer of orders) {
    if (!seen.includes(customer)) {
      seen.push(customer);
    }
  }
  return seen.length;
}

const orders = [7, 3, 7, 12, 3, 7];
console.log(uniqueCustomers(orders));

На кой ред се крие вторият цикъл?

Избери реда с грешката.

Упражнение

Колко комбинации

Реши задачата в редактора си.

Стъпките на комбинациите. Добави брояч steps в combos: една стъпка за всяка готова комбинация (когато i стигне края). Пусни я с 10, 11 и 12 продукта с цени 500 + 100 · k цента и бюджет 5000 и изпечатай стъпките:

10 продукта: 1024 стъпки
11 продукта: 2048 стъпки
12 продукта: 4096 стъпки

Всеки продукт удвоява стъпките. Колко са при 20 продукта? А при 40? Сметни, преди да пуснеш.

Още задачи

Класът на всяка функция. Напиши Big-O на всяка от функциите от урока „Времева сложност: броене на стъпки“, включително продажбите по продукт (50 продукта × n поръчки).
Двоично търсене с брояч. Добави брояч в indexOf и потърси цена, която я няма, в 1 000 и в 100 000 подредени цени. Сравни с програмата, която дели на две.
Пак множество. Поправи броенето на различните клиенти с множество и сравни стъпките при 1 000 различни клиенти.

Тест

Провери се

1. Функция прави 3n + 5 стъпки. Каква е сложността ѝ?O(1)O(3n + 5)O(n)

2. Алгоритъм е O(n²). Данните стават 10 пъти повече. Колко пъти повече работа да очакваш?10 пътиОколо 20 пътиОколо 100 пъти

3. Колко проверки прави двоичното търсене в подреден списък от 1 000 000 цени, когато цената я няма?Около 1 000Около 20Около 500 000

4. Комбинациите в бюджета са O(2ⁿ). Колко са при 30 продукта?Над милиардОколо 90060

5. Два алгоритъма за едно и също: единият е O(n log n), другият е O(n²). При 10 елемента вторият е по-бърз. Кой избираш за 1 000 000 поръчки?Все едноO(n log n): при голямо n кривата решава, а не константитеO(n²), щом е по-бърз

Big-O: как расте работата

Бисквитки