[CS] 복잡도

복잡도란?

• 입력 데이터의 크기(N)가 커질 때, 알고리즘이 얼마나 오래 걸리고(시간), 얼마나 많은 메모리를 쓰는지(공간)를 수치로 표현한 것
  → “이 코드, 데이터 많아지면 버틸 수 있어?”를 판단하는 기준

 

1. 시간복잡도

• 입력 크기 N에 따라 어떠한 알고리즘이 실행되는 데 걸리는 시간
• 주요 로직의 반복 횟수를 중점으로 측정
• 컴퓨터 성능과 무관하게 알고리즘 자체의 효율을 비교 가능 → 효율적은 코드로 개선하는데 쓰이는 척도
• 서버, 대용량 데이터, 실시간 처리에서 필수
• Big-O 표기법 코드
• 보통 Big-O 표기법으로 나타냄
  

  표기	의미	예시
  O(1)	항상 일정	배열 첫 값 접근 / 엘리베이터 버튼 한 번 누르기
  O(log N)	절반씩 줄어듦	이진 탐색
  O(N)	N에 비례	한 번 순회 / 사람 한 명씩 줄 세우기
  O(N log N)	효율적 정렬	merge sort
  O(n²)	이중 반복	이중 for문 / 모든 사람끼리 악수시키기
  O(2ⁿ)	폭발적 증가	재귀적 조합

  • Big-O표기법에서 “상수 무시”는 이런 의미:
    • O(2N) → O(N)
    • O(N + 1000) → O(N)
      (입력이 아주 커지면, 상수/작은 항은 영향이 작아짐
  • O(n²)보다는 O(n), O(n)보다는 O(1)을 지향

🚨 “무조건 O(1)이 최고”인가?
O(1)이라도 상수 비용이 큰 작업(예: 무거운 JSON 파싱, DOM 대량 조작)이면 느릴 수 있음.
그래서 “Big-O”는 확장성 판단, “실측 성능”은 프로파일링으로 확인하는 게 안전함.  

• • Big-O 표기법 코드

    // O(N)
    for (let i = 0; i < N; i++) {
      console.log(i);
    }
    
    // O(N²)
    for (let i = 0; i < N; i++) {
      for (let j = 0; j < N; j++) {
        console.log(i, j);
      }
    }

    • 실무에서 O(N²) 예시: 
      • map 안에서 find / includes / filter를 또 돌리는 경우
      • “리스트 렌더링 중에 매번 검색” 같은 코드

 

 

Big-O 표기법

---

2. 공간복잡도

• 프로그램을 실행시켰을 때 필요로 하는 자원 공간의 양
• 메모리 제한 환경 (모바일, 임베디드, 서버)
• 대규모 데이터 처리 시 메모리 폭주 방지
• 공간복잡도도 보통 입력 공간 vs 추가 공간을 구분함
  • 입력 데이터 자체(이미 주어진 배열/객체)는 보통 제외하고
  • 알고리즘이 추가로 만든 배열/객체/재귀 스택 같은 걸 봄
• JS에서는 특히 이런 게 공간에 영향 큼
  • map/filter/sort/spread 같은 새 배열 생성
  • 깊은 복사(structuredClone, JSON.parse(JSON.stringify(...)))
  • 재귀 호출(콜스택 사용)
• 대표적인 공간복잡도

  표기	의미	예시
  O(1)	추가 메모리 거의 없음	변수 몇 개
  O(N)	입력 크기만큼 메모리 사용	배열 복사
  O(N²)	2차원 배열	행렬

• 공간복잡도 코드

  // O(1)
  let sum = 0;
  
  // O(N)
  let arr = [];
  for (let i = 0; i < N; i++) {
    arr.push(i);
  }

• 공간 최적화의 대표 전략(프론트에서도 자주 씀)
  • “결과 배열을 만들지 말고 바로 누적/집계하기” (O(1)로)
  • “필요한 순간에만 계산하기(지연 계산)”
  • “큰 리스트는 가상 스크롤(virtualization)*로 렌더링 비용/메모리 줄이기”
•