JavaScript CodingStudy - BigO 표기법 시간복잡도

Big-O 표기법은 알고리즘의 성능(시간 혹은 공간 복잡도)을 표현하는 방법이다.

한마디로 정의하면 '최악의 경우가 나올 경우 얼마나 오래걸리는가?' 라고도 할 수 있다.
이는 상한 점근을 뜻하기도 한다.

알고리즘의 성능을 결정하는 요인은 내가 원하는 대로 데이터가 준비되는 경우가 아닌 극단적인 상황을 고려해야한다.

다음은 빅오 표현법 성능 차트인데, 입력 크기에 따른 CPU 사용률을 나타넨다.
비효율적인 알고리즘은 입력크기가 조금만 커져도 CPU 사용률이 금방 높게 향한다.
실제 서비스에서 해당 알고리즘같은 형태로 표현 됐을때 심각한 문제가 발생 할 수 있다.

Trade OFF

시간 복잡도와 공간 복잡도는 서로 독립적인 개념이고, 항상 연관이 있지 않기에 따로 분석하고 고려해야한다.
시간 복잡도가 효율적이라도, 메모리 사용량이 클 수도 작을 수도 있다.
이는 데이터 구조와 구현 방식에 따라 다르기 때문에 알 수 없는 부분이라, 상황에 따라 Trade OFF가 이루어져야 한다.

복잡도 종류	의미	예시
시간 복잡도	연산 횟수	for문, 재귀 호출 횟수 등
공간 복잡도	필요한 메모리 (변수/배열) 크기	배열, 객체, 재귀 호출 스택 등

---

코드로 표기하면 가끔 코딩테스트에도 같은 유형으로 문제들이 많이 나온다.
우선 시간 복잡도에 각 표기법에 관한 코드를 간략하게 구현해보았다.

O(1) 상수시간

// O(1) - 상수 시간
function getFirst(arr) {
    return arr[0]
}

console.log(getFirst([1, 2, 3, 4, 5])) // 1

입력이 10개든 1,000개든 → 한 번만 실행

O(n) 선형시간

// O(n) - 선형 시간
function printAll(arr) {
    for (let i = 0; i < arr.length; i++) {
        console.log(arr[i])
    }
}

console.log(printAll([1, 2, 3, 4, 5])) // 1 2 3 4 5

입력크기에 비례해서 실행횟수가 증가

O(n^2) 이중 루프 (제곱 시간)

function printPairs(arr) {
    for (let i = 0; i < arr.length; i++) {
        for (let j = 0; j < arr.length; j++) {
            console.log(arr[i], arr[j])
        }
    }
}

console.log(printPairs([1, 2, 3, 4, 5]))

중첩 반복문으로 이중으로 탐색을 진행한다.

배열이 3개 → 9번 실행
배열이 100개 → 10,000번 실행

이외에도 O(log n), O(n log n), O(2ⁿ) 등이 있지만, 추후 더 복잡한 로직 알고리즘은 따로 다루려 한다.

시간 복잡도 정리 (Big-O)

시간 복잡도	예시	설명
O(1)	arr[0]	상수 시간
O(n)	for, map	선형 시간
O(n²)	중첩 반복문	제곱 시간
O(log n)	이진 탐색	로그 시간
O(n log n)	정렬 (mergeSort 등)	효율적인 정렬
O(2ⁿ)	피보나치(재귀)	비효율적인 재귀

---

소스코드