시간복잡도 분석과 성능 비교

🚀 시간복잡도 분석과 성능 비교

💡 시간복잡도란?

시간복잡도(Time Complexity)는 알고리즘이 입력 크기에 따라 실행 시간이 어떻게 증가하는지를 나타내는 지표입니다.

• O(1): 상수 시간 - 입력 크기와 무관하게 일정한 시간
• O(n): 선형 시간 - 입력 크기에 비례하여 시간 증가
• O(n²): 제곱 시간 - 입력 크기의 제곱에 비례하여 시간 증가
• O(log n): 로그 시간 - 입력 크기가 증가해도 천천히 시간 증가

📊 성능 비교 차트

 

💻 코드 비교

O(n)

✅ 효율적인 방법 (현재 코드)

const qaGroups = qaResponses.reduce((groups, response) => {
  const { timestamp, question } = response;
  if (!groups[timestamp]) {  // O(1) 접근
    groups[timestamp] = {
      timestamp,
      question,
      responses: [],
    };
  }
  groups[timestamp].responses.push(response);
  return groups;
}, {});

// O(g log g) - g는 그룹 수
const sortedQAGroups = Object.values(qaGroups)
  .sort((a, b) => a.timestamp - b.timestamp);

O(n²)

❌ 비효율적인 방법

const qaGroups = qaResponses.reduce((groups, response) => {
  // O(g) - 매번 배열을 순회해서 찾기
  const existingGroup = groups.find(g => 
    g.timestamp === response.timestamp
  );
  
  if (existingGroup) {
    existingGroup.responses.push(response);
  } else {
    groups.push({
      timestamp: response.timestamp,
      question: response.question,
      responses: [response]
    });
  }
  return groups;
}, []);

🔑 핵심 차이점

객체의 키 접근은 O(1) 시간에 가능하지만, 배열에서 특정 조건의 요소 찾기는 O(n) 시간이 필요합니다!

📈 성능 분석

응답 100개, 그룹 10개

110 vs 5,050

연산 횟수 비교

응답 1,000개, 그룹 50개

1,087 vs 500,500

연산 횟수 비교

성능 향상

460배

더 빠른 처리 속도

📋 상세 성능 비교표

응답 수 (n)	그룹 수 (g)	효율적 방법 O(n + g log g)	비효율적 방법 O(n²)	성능 차이
100	10	110	5,050	46배 빠름
500	25	625	125,250	200배 빠름
1,000	50	1,087	500,500	460배 빠름
5,000	100	5,200	12,502,500	2,404배 빠름

🎯 왜 reduce를 사용해서 객체로 그룹화하는가?

1. 해시 테이블의 활용: JavaScript 객체는 해시 테이블로 구현되어 키 접근이 O(1)
2. 중복 검색 제거: 같은 타임스탬프를 가진 그룹을 찾기 위해 매번 배열을 순회할 필요 없음
3. 메모리 효율성: 각 타임스탬프마다 하나의 그룹만 생성
4. 확장성: 데이터가 많아져도 성능 저하가 완만함

⚡ 성능 최적화 포인트

• 그룹화 단계: reduce + 객체 키 접근으로 O(n) 시간에 완료
• 정렬 단계: Object.values()로 배열 변환 후 그룹 수만큼만 정렬 (O(g log g))
• 전체 복잡도: O(n + g log g) ≈ O(n) (일반적으로 g << n)

📊 실행 시간 비교 그래프