시간복잡도

#it #알고리즘 #자료구조 #시간복잡도 #bigo

기본 정보

명칭: 시간 복잡도
영문명: Time Complexity
분류: 알고리즘 성능 분석
주요 용도: 알고리즘 실행 시간 예측
관련 주제: #알고리즘 #시간복잡도 #BigO #자료구조

개요

시간 복잡도(Time Complexity)는 입력 데이터의 크기(N)가 증가할 때 알고리즘의 실행 시간이 얼마나 증가하는지를 나타내는 척도이다.

실제 실행 시간을 측정하는 것이 아니라, 연산 횟수가 얼마나 증가하는지를 수학적으로 표현한다.

예를 들어 데이터가 10개일 때 1초가 걸리고, 100개일 때 100초가 걸린다면 효율이 좋지 않은 알고리즘일 가능성이 높다.

왜 중요한가?

데이터가 적을 때는 차이가 크지 않지만, 데이터가 많아질수록 성능 차이가 매우 커진다.

예시

N = 1,000,000

O(N)     → 약 1,000,000회

O(N²)    → 약 1,000,000,000,000회

같은 데이터를 처리해도 연산량 차이가 엄청나게 발생한다.

Big-O 표기법

시간 복잡도는 일반적으로 Big-O 표기법을 사용한다.

O(1)

O(log N)

O(N)

O(N log N)

O(N²)

O(2^N)

O(N!)

O(1) - 상수 시간

입력 크기와 상관없이 항상 같은 시간이 걸린다.

const arr = [1,2,3,4,5];

console.log(arr[0]);

배열 첫 번째 요소 접근

N=10

N=1,000,000

모두 동일

가장 이상적인 성능이다.

O(log N) - 로그 시간

데이터를 절반씩 줄여가며 탐색한다.

대표 예시

이진 탐색(Binary Search)

100개

↓

50개

↓

25개

↓

12개

↓

6개

O(N) - 선형 시간

데이터 개수만큼 반복한다.

for(let i=0; i<n; i++){

}

예시

N=10

→ 10번

N=100

→ 100번

O(N log N)

정렬 알고리즘에서 자주 등장한다.

대표 예시

Merge Sort
Quick Sort(평균)
Heap Sort

1,000개 데이터

↓

약 10,000회 연산

O(N²)

이중 반복문

for(let i=0;i<n;i++){

    for(let j=0;j<n;j++){

    }

}

예시

N=100

↓

10,000회

데이터가 커질수록 급격히 느려진다.

O(2^N)

모든 경우를 탐색하는 경우

예시

완전 탐색
백트래킹 일부

N=20

↓

1,048,576

O(N!)

순열(Permutation)

5!

=

120

10!

=

3,628,800

매우 비효율적이다.