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

핫 경로에 집중하기

멤버 확인 최적화 퀴즈

복습