Към съдържанието
wannacode

Времева сложност: броене на стъпки

Накратко: Времевата сложност казва как расте броят на основните операции с размера на входа: вложеният цикъл прави n(n − 1) / 2 стъпки, а едно минаване с множество прави n.

Проблем

Отчетът, който не свършва

Всеки месец онлайн магазинът пуска отчет за продажбите. Една от проверките в него търси двойни плащания: едно и също плащане, минало два пъти заради повторно натиснат бутон. Функцията сравнява всяко плащане с всяко след него:

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;
}
const ids = [100231, 100232, 100233, 100232, 100234];
console.log("Двойни плащания: " + doublePayments(ids));
Изход
Двойни плащания: 1

Преди година поръчките бяха 1 000 на месец и отчетът беше готов за 2 секунди. Днес са 100 000. Отчетът тръгва вечерта и сутринта още не е свършил. Кодът не е пипан. Данните са 100 пъти повече, а времето не е 100 пъти повече, а много повече.

Защо? И как можеше да се знае предварително, без да чакаш цяла нощ?

Идеята

Секундите лъжат, стъпките не

Колко секунди трае една програма, зависи от много неща извън нея:

  • машината: лаптопът и сървърът дават различни числа;
  • натоварването: същият отчет е по-бавен, докато сървърът обслужва и клиентите;
  • езика: една и съща сметка е няколко пъти по-бавна на Python, отколкото на Java или C#.

Затова се мери друго: колко пъти програмата прави своята основна операция. Тук това е едно сравнение на два номера. Броят им не зависи нито от машината, нито от езика, а само от алгоритъма и от входа. Това се казва брой операции (или брой стъпки).

Броят операции не казва секундите. Казва нещо по-полезно: колко пъти повече работа идва, когато данните растат.

Виж го

Броим стъпките

Слагаш брояч до сравнението. Всяко сравнение е една стъпка:

let steps = 0;


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

Отчетът се пуска върху 10, 1 000 и 2 000 плащания с различни номера:

for (const n of [10, 1000, 2000]) {
  const ids = Array.from({ length: n }, (_, k) => 100000 + k);
  steps = 0;
  doublePayments(ids);
  console.log(`n = ${n}: ${steps} стъпки`);
}
Изход
n = 10: 45 стъпки
n = 1000: 499500 стъпки
n = 2000: 1999000 стъпки

Първото плащане се сравнява с n − 1 други, второто с n − 2 и така до последното, което няма с кого. Сборът е

n(n − 1) / 2

При 1 000 плащания това са 499 500 стъпки. При 100 000 са 4 999 950 000: 10 010 пъти повече за 100 пъти повече данни. Ако двете секунди отиваха почти изцяло за сравненията, сега отиват над пет часа и половина. Отговорът беше в кода още преди година: трябваше да преброиш.

Виж го

Защо почти ×4

let steps = 0;


function doublePayments(ids) {
  let found = 0;
  for (let i = 0; i < ids.length; i++) {
    for (let j = i + 1; j < ids.length; j++) {
      steps++;
      if (ids[i] === ids[j]) {
        found++;
      }
    }
  }
  return found;
}
Стъпка по стъпка, с думи
  1. Четири плащания. Външният цикъл взима първото, i = 0: то ще се сравни с всяко плащане след него.
  2. j минава плащанията след i. Всяко сравнение е една стъпка и клетката на двойката светва: steps = 1, 2, 3.
  3. i се мести напред, а j тръгва пак от i + 1. Двойките са 3 + 2 + 1 = 6: триъгълник.
  4. Двойно повече плащания: 8. Стъпките не са 12, а 28.
  5. 28 = 6 стари двойки + 6 двойки от новите + 16 двойки ново със старо. Почти ×4: при 1 000 → 2 000 плащания стъпките са 499 500 → 1 999 000.
  6. Поправката минава веднъж и помни номерата в seen: 8 плащания, 8 стъпки. Тук двойно повече плащания значи двойно повече стъпки.

Удвояването не е само „още толкова плащания“. Старите 6 двойки остават. Идват 6 двойки между новите плащания. И още 16: всяко от 4-те нови с всяко от 4-те стари. Общо 28. Частта „ново със старо“ е квадрат и тя расте най-бързо. Затова при голямо n удвояването дава почти точно ×4.

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

Сметката за всяко n: при 2n плащания двойките са 2n(2n − 1) / 2 = 4 · n(n − 1) / 2 + n. Тоест четири пъти старите двойки и още n. При n = 4 това е 4 · 6 + 4 = 28, а при n = 1 000 е 4 · 499 500 + 1 000 = 1 999 000. Добавката n е малка пред останалото, и колкото по-голямо е n, толкова по-малка.

Пробвай

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

Два вложени цикъла. Първият минава 4 склада и за всеки 3 часа за доставка. Вторият минава всяка двойка от 4 склада. Какво печата програмата?

let full = 0;
for (let i = 0; i < 4; i++) {
  for (let j = 0; j < 3; j++) {
    full++;
  }
}
let pairs = 0;
for (let i = 0; i < 4; i++) {
  for (let j = i + 1; j < 4; j++) {
    pairs++;
  }
}
console.log(full + " " + pairs);
Отговор

Пробвай

Попълни

Отчетът трябва да сравни всяка двойка точно веднъж и да не сравнява плащане със самото себе си. Откъде тръгва вътрешният цикъл?

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

Виж го

Поправката: едно минаване

Не е нужно всяко плащане да се сравнява с всяко. Достатъчно е да помниш номерата, които вече си видял. Множеството (set) пази тези номера и казва дали даден номер е в него, без да ги минава един по един.

let steps = 0;


function doublePayments(ids) {
  const seen = new Set();
  let found = 0;
  for (const id of ids) {
    steps++;
    if (seen.has(id)) {
      found++;
    } else {
      seen.add(id);
    }
  }
  return found;
}
seen.has(id) пита множеството дали номерът е в него, а seen.add(id) го записва.
for (const n of [10, 1000, 2000]) {
  const ids = Array.from({ length: n }, (_, k) => 100000 + k);
  steps = 0;
  doublePayments(ids);
  console.log(`n = ${n}: ${steps} стъпки`);
}
Изход
n = 10: 10 стъпки
n = 1000: 1000 стъпки
n = 2000: 2000 стъпки

Стъпките са колкото плащанията. Двойно повече плащания значи двойно повече стъпки. Пусни двата отчета един до друг:

  • Всяка двойка поръчки O(n²)
  • Отчетът с множество (set) O(n)
Алгоритъмn = 10n = 1000n = 2000n = 4000n = 100 000
Всяка двойка поръчки45499 5001 999 0007 998 000≈ 4 998 750 000
Отчетът с множество (set)10100020004000100 000
Кодът се пуска в твоя браузър на JavaScript. Броят операции е същият на всеки език, защото алгоритъмът е същият. Времето зависи от машината, затова е само за сравнение. „≈“ е оценка по кривата: толкова голямо n не пускаме, за да не замръзне страницата.
По-точно, за любопитните

Коя е основната операция? Тази, която се повтаря най-много и от която зависи времето. В бавния отчет това е сравнението във вътрешния цикъл. Увеличаването на i и j и проверката дали цикълът е свършил също се повтарят, но колкото сравненията, не повече. Затова броят им не сменя картината и не се брои отделно.

Проверката в множеството една стъпка ли е? Не съвсем: зад множеството стои hash таблица, която смята hash на номера и гледа в една кофа. Средно това е една и съща малка работа, колкото и номера да има вътре. Как става, ще видиш в модула „Структури от данни“. Тук я броим за една стъпка, както я брои и Bench.

Секундите на различните езици. Броят стъпки е еднакъв, а времето не е. V8 компилира горещия цикъл до машинен код по време на работа, затова първото пускане е по-бавно от следващите. Bench на тази страница пуска точно този JavaScript, затова неговите секунди са най-близо до твоите.

Упражнение

Продажбите по продукт

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

Колко стъпки. Отчетът за продажбите брои колко пъти е поръчан всеки от 50-те продукта. Поръчката е номерът на продукта (от 0 до 49):

function salesByProduct(orders, products) {
  const sales = new Array(products).fill(0);
  for (let p = 0; p < products; p++) {
    for (const product of orders) {
      if (product === p) {
        sales[p]++;
      }
    }
  }
  return sales;
}

Добави брояч steps пред сравнението. Пусни функцията с 1 000 и с 2 000 поръчки, в които продуктът на поръчка k е k % 50, и изпечатай стъпките:

Изход
n = 1000: 50000 стъпки
n = 2000: 100000 стъпки

Цикълът е вложен, а стъпките растат само двойно. Защо?

Още задачи

  • Едно минаване. Направи отчета за продажбите с едно минаване по поръчките: sales[product] расте с едно за всяка поръчка. Колко стъпки са при 1 000 поръчки?
  • Отчетът на годината. Колко стъпки прави бавният отчет за двойни плащания за цяла година с по 100 000 плащания на месец? Сметни с n(n − 1) / 2, без да го пускаш.
  • Твоят код. Намери в свой код вложен цикъл и преброй стъпките за два размера на входа. Какво става, когато входът се удвои?

Тест

Провери се

1. Защо броим операции, а не секунди?
2. Отчетът сравнява всяко плащане с всяко след него. Плащанията стават двойно повече. Колко пъти повече са стъпките?
3. Отчетът за продажбите минава всичките 50 продукта, а за всеки продукт минава всички поръчки. Поръчките стават двойно повече. Колко пъти повече са стъпките?
4. Колко стъпки прави поправката с множеството при 100 000 плащания?

Създаден от Иво Гергов като част от кампанията на Evo Tech за достъпно обучение по програмиране ·