[Algorithm] 시간 복잡도 (Time Complexity) 개념 및 Big-O 표기법

알고리즘 문제를 풀거나 효율적인 로직을 짤 때 가장 중요한 개념중 하나인 시간 복잡도에 대해 정리한다.

 

시간 복잡도

시간복잡도(Time Complexity)는 주어진 문제를 해결하기 위해 필요한 연산 횟수를 의미한다. 실제 걸리는

시간(초)를 측정하는 것이 아니라, 입력 데이터의 크기에 따라 연산량이 어떻게 증가하는지를 나타내는 지표다.

 

일반적으로 Problem Solving 환경에서는 1억번의 연산 = 1초 로 예측한다.

 

시간 복잡도 표기법

 - 빅-오메가 (Big-Ω) : 최선(Best Case)의 경우
 - 빅-세타 (Big-θ) : 보통(Average Case)의 경우
 - 빅-오 (Big-O) : 최악(Worst Case)의 경우

 

알고리즘 성능 평가시에는 데이터가 최악으로 주어졌을때도 처리가 가능한지를 판단해야 하므로 빅-오 (Big-O) 표기법이 가장 중요

 

시간 복잡도 도출 기준

1. 상수는 시간 복잡도에서 제외

연산횟수가 N이든 3N이든, N이 무한대로 커지면 상수의 영향력은 미미하므로 똑같이 O(N)으로 취급한다.

 

2. 가장 많이 중첩된 반복문의 횟수가 기준

반복문이 2중으로 중첩되어 있다면 O(N^2), 3중이라면 O(N^3)이 된다. 따라서 가장 깊은 반복문을 찾으면 된다.

 

데이터 크기와 연산 횟수 확인

시간 복잡도를 따질 때는 가장 먼저 데이터의 개수(Input Size)를 확인해야 한다. 전체 연산 횟수는 다음과 같이 계산한다.

 

 연산 횟수 = 알고리즘 시간 복잡도 x 데이터의 크기

 

알고리즘 별 시간 복잡도 예시

 - 버블 정렬(Bubble Sort) : O(N^2)

데이터가 많아질수록 기하급수적으로 속도 저하

 

 - 병합 정렬(Merge Sort) : O(N log N)

N^2 대비 훨씬 효율적

효율적인 알고리즘 적용

1. 문제의 제한 시간 내에 통과할 수 있는 알맞는 알고리즘을 선택하기 위함

2. 코드 내에서 비효율적인 로직을 찾아 계산하기 위함

 

정리

무조건 복잡한 알고리즘을 쓰는 것이 아니라, 데이터의 크기에 맞춰 적절한 시간 복잡도를 가진 알고리즘을 선택하는 것이 핵심