Yoora's Lab

시간 복잡도는 입력 크기(n)가 커질수록 알고리즘이 수행하는 연산량이 어떤 성장률로 증가하는지를 나타낸다.

실제 실행시간(ms)이 아니라, 입력 증가에 따른 "성장 추세"로 알고리즘 효율을 비교한다.

왜 실제 시간(ms) 대신 수학적으로 표현할까?

• 같은 코드라도 하드웨어/OS/런타임/백그라운드 작업 등에 따라 실제 시간은 달라져 비교가 어렵다.
• 따라서, 입력 크기 n에 따른 성장률로 추상화하여 점근적 표기로 비교한다.

즉, 시간 복잡도는 "얼마나 오래걸리는지"가 아니라 "입력이 커질 때 얼마나 빨리 느려지는지"를 보는 지표이다.

1. 빅오(Big-O) 표기법이란

빅오(Big-O) 표기법은 알고리즘의 실행 시간이 입력 크기 n에 따라 어느 정도로 증가하는지(성장률)를 표현하는 방식이다.

보통 최악의 경우(Worst Case)를 기준으로 "아무리 운이 나빠도 이 정도 시간 안에는 끝난다"는 상한선(Upper Bound)를 나타낸다.

2. Big-O 표기법의 수학적 규칙

1) 가장 큰 항만 남긴다.

입력 n이 충분히 커질수록, 가장 빨리 커지는 항이 전체 성능을 지배한다.

예: f(n) = 3n² + 10n + 500

• n이 커지면 n² 항이 압도적으로 커짐
  -> 따라서 O(n²)로 표현

2) 상수는 무시한다 (증가 "비율"만 중요)
성장률을 볼 떄는 상수 배수나 상수 시간은 복잡도에 큰 영향을 주지 않으므로 제거한다.

• O(5n) -> O(n)
• O(1000) -> O(1)

3. 자주 쓰는 Big-O 종류

1) O(1) 상수 시간

• 입력 크기 n과 상관없이 항상 일정한 시간
• 예: 배열 특정 인덱스 접근 arr[5]

2) O(log n) 로그 시간

• 데이터가 커져도 시간이 조금씩만 증가
• 예: 이진 탐색(범위를 절반씩 줄이는 Up/Down 방식)

3) O(n) 선형 시간

• 입력 크기 n에 비례해서 실행 시간이 증가
• 예: for로 배열 전체를 한 번 순회

4) O(n²) 제곱 시간

• 입력이 늘어나면 시간이 제곱으로 급격히 증가
• 예: 이중 for문(구구단처럼 중첩 반복)

4. 실행속도를 숫자로 확인해보기

입력 크기 n = 1,000 일 때,

시간 복잡도는 버그가 아니라 구조적인 성능 문제이므로, 프로그래밍에서 중요하다.

1. 단순하지만 가장 중요한 기준: "몇 번 도는가?"

• O(1): 한 번에 접근 (상수 시간)

  JavaScriptJavaScriptfunction accessArray(arr) {
    return arr[2];
  }

  • 배열 길이와 상관없이 항상 한 번 접근
    -> 따라서 O(1)
• O(n): 한 번 돌기 (선형 시간)

  JavaScriptJavaScriptfunction sum(arr){
    let total = 0;
    for (let i = 0; i < arr.length; i++){
      total += arr[i];
    }
    return total;
  }

  • 배열 길이가 n일 때 반복문이 n번
    -> 따라서 O(n)
• O(n²): 중첩 반복 (제곱 시간)

  JavaScriptJavaScriptfunction countPairs(arr) {
    let count = 0;
    for(let i = 0; i < arr.length; i++){
      for(let j = 0; j < arr.length; j++){
        count++;
      }
    }
    return count;
  }

  • 바깥 루프 n번 x 안쪽 루프 n번
    -> 따라서 O(n²)
  • 입력이 10배면 실행량은 100배가 되기 쉽다.

2. 프론트엔드에서 "O(n²)"가 자주 생기는 경우

"배열을 한 번 돌면서, 그 안에서 또 배열을 탐색하는 방식"

특히 includes, find, filter 같은 메서드는 내부적으로 앞에서부터 순차 탐색(선형 탐색) 형태가 되기 쉬워서, 중첩되면 O(n²)이 된다.

• 문제가 될 수 있는 중첩 코드 #1 : map + includes 조합

  JavaScriptJavaScriptfunction selectComponent(items, selectedIds) {
    return items.map(item => ({
      ...item,
      selected: selectedIds.includes(item.id)
    }));
  }

  💡 느려지는 이유
  • items.map: n번 반복
  • selectedIds.includes(...): 매번 m개를 선형 탐색
  • 결과적으로 O(nm)
  • 보통 n≈m이면 체감상 O(n²)
  🍀 개선 : Set으로 최적화

  JavaScriptJavaScriptfunction selectComponent(items, selectedIds) {
    const selectedSet = new Set(selectedIds)
    return items.map(item => ({
      ...item,
      selected: selectedSet.has(item.id)
    }));
  }

  개선 포인트
  • Set.has()는 평균적으로 빠른 체크가 가능하도록 설계된다.
  • 전처리 new Set(selectedIds) : O(m)
  • 전체 map 검사 : O(n)
  • 총합 O(n + m)로 개선
• 문제가 될 수 있는 중첩 코드 #2 : some + includes 조합

  JavaScriptJavaScript// 두 배열에 공통 값이 있는지 확인
  function hasAnyCommon(a, b) {
    return a.some(x => b.includes(x));
  }

  💡 느려지는 이유
  • some: 최악 n번
  • includes: 최악 m번
  • 최악 O(nm)
  🍀 개선 : Set으로 최적화

  JavaScriptJavaScriptfunction hasAnyCommon(a, b) {
    const setB = new Set(b);
    return a.some(x => setB.has(x));
  }

  • 전처리 O(m) + 검사 O(n)
    -> O(n + m)
• 문제가 될 수 있는 중첩 코드 #3 : filter 중첩

  JavaScriptJavaScript// ex. 카테고리 목록 : products: n개, categories: m개
    const ui = categories.map(cat => ({
      ...cat,
      items: products.filter(p => p.categoryId === cate.id)
    }));

  💡 느려지는 이유
  • categories.map: m번
  • 내부 products.filter: 매번 n번
  • 총합 O(nm)
  🍀 개선 : 1회 그룹핑 인덱스 만들기

  JavaScriptJavaScriptfunction groupByCategory(products){
    const bucket = new Map();
  
    for(const p of products){
      if(!bucket.has(p.categoryId)) bucket.set(p.categoryId, []);
      bucket.get(p.categoryId).push(p);
    }
    return bucket;      
  }
  const bucket = groupByCategory(products);
  const ui = categories.map(cat => ({
    ...cat,
    items: bucket.get(cat.id) ?? []
  }));
  

  • 그룹핑: O(n)
  • UI 구성: O(m)
  • 총합: O(n + m)
• 문제가 될 수 있는 중첩 코드 #4 : 루프 안에서 매번 querySelector 호출

  JavaScriptJavaScriptfunction updateBad(rows){
    for (const row of rows) {
      const el = document.querySelector(`[data-id="${row.id}"]`);
      if(el) el.textContent = row.value;
    }                  
  }

  💡 느려지는 이유
  • querySelector 자체가 DOM 트리에서 탐색 비용이 있고, DOM이 큰 페이지일수록 탐색/스타일/레이아웃 비용이 커져서 반복시 체감 성능이 급격히 무너질 수 있기 때문이다.
  🍀 개선 접근: DOM을 한 번만 수집하고 Map으로 캐싱

  JavaScriptJavaScriptfunction updateBetter(rows){
    const map = new Map();
    
    document.querySelectorAll("[data-id]").forEach(el => {
      map.set(el.dataset.id, el);
    });
    for(const row of rows){
      const el = map.get(String(row.id));
      if(el) el.textContent = row.value;
    }
  }

  • "DOM 탐색"을 반복문 안에서 하지 않고 한번만 수집
    -> "빠른 조회 구조(Map)"로 변경