Основы Big-O, горячие и холодные участки (полезные приёмы для начинающих)

Общая картина

Вложенный поиск обходится дорого

// Bad pattern: nested scan for membership (can be ~O(n^2))
const haystack = ["a","b","c","d","e"];
const needles = ["b","e","x"];
const foundSlow = [];

for (const n of needles) {
  // includes scans the array each time
  if (haystack.includes(n)) {
    foundSlow.push(n);
  }
}
console.log("slow found:", foundSlow);

Set для проверки принадлежности

// Better: build a Set once, then O(1)-ish checks (~O(n) overall)
const fastSet = new Set(haystack);
const foundFast = [];
for (const n of needles) {
  if (fastSet.has(n)) {
    foundFast.push(n);
  }
}
console.log("fast found:", foundFast);

Map для подсчёта

// Build a frequency map once instead of scanning many times
const words = ["a","b","a","a","c","b"];
const freq = new Map();

for (const w of words) {
  const old = freq.get(w) || 0;
  freq.set(w, old + 1);
}

console.log("count a:", freq.get("a"));
console.log("count b:", freq.get("b"));

Выполните один раз (кэширование)

// Do work once and reuse (tiny cache)
function heavy(x) {
  // pretend heavy math
  return x * x + 1;
}

const cache = new Map();

function heavyCached(x) {
  if (cache.has(x)) return cache.get(x);
  const val = heavy(x);
  cache.set(x, val);
  return val;
}

console.log("first:", heavyCached(5));
console.log("second:", heavyCached(5)); // cached

Сосредоточьтесь на горячих путях

Викторина об оптимизации проверки принадлежности

Итоги