⏰ 시간복잡도 완벽 가이드

🤔 시간복잡도가 뭔가요?

간단히 말하면: 데이터가 늘어날 때 실행 시간이 얼마나 늘어나는지 측정하는 방법

예시로 이해하기:

📊 Big O 표기법 (가장 많이 사용)

🥇 자주 보는 시간복잡도 순위 (빠른 순)

순위 Big O 이름 예시 데이터 크기별 실행 시간
🥇 O(1) 상수 시간 배열 인덱스 접근 항상 동일
🥈 O(log n) 로그 시간 이진 탐색 매우 느리게 증가
🥉 O(n) 선형 시간 배열 전체 순회 비례해서 증가
4위 O(n log n) 선형로그 효율적인 정렬 조금씩 빨라지며 증가
5위 O(n²) 제곱 시간 이중 반복문 급격히 증가
6위 O(2ⁿ) 지수 시간 피보나치(재귀) 폭발적 증가

🔍 각 시간복잡도 자세히 알아보기

🥇 O(1) - 상수 시간

특징: 데이터 크기와 상관없이 항상 같은 시간

// 배열에서 특정 인덱스 값 가져오기
function getFirst(arr) {
    return arr[0];  // 배열 크기와 상관없이 항상 똑같은 시간
}

// 배열이 10개든 1000개든 똑같이 빠름!

실생활 예시: 사전에서 페이지 번호로 바로 찾기

🥈 O(log n) - 로그 시간

특징: 데이터가 2배 늘어도 실행 시간은 조금만 증가

// 이진 탐색 (정렬된 배열에서 값 찾기)
function binarySearch(arr, target) {
    let left = 0, right = arr.length - 1;

    while (left <= right) {
        let mid = Math.floor((left + right) / 2);

        if (arr[mid] === target) return mid;
        if (arr[mid] < target) left = mid + 1;
        else right = mid - 1;
    }
    return -1;
}

// 1000개 → 약 10번 비교
// 1000000개 → 약 20번 비교 (2배만 증가!)