[알고리즘] 시간 복잡도와 공간 복잡도 + Big O 표기법

시간 복잡도

• 입력 크기에 대해 어떤 알고리즘이 실행되는 데 걸리는 시간
• 입력 데이터 개수(n)가 늘어날수록 컴퓨터가 그 작업을 처리하는데는 얼마나 실행 시간이 늘어날까?
  • 실제 시간을 재는 게 아니라 연산 횟수를 기준으로 측정

---

공간 복잡도

• 프로그램을 실행시켰을 때 필요로 하는 메모리 공간의 양
• 입력 데이터 개수(n)가 늘어날수록 얼마나 많은 양의 데이터가 메모리에 저장되어야 할까?

---

Big O 표기법

• Big O 표기법은 입력 n이 충분히 커졌을 때 함수로 나타내는, 알고리즘의 복잡도를 표현하는 방법으로, 최악의 경우(워스트 케이스)를 기준으로 합니다.
• 이때 최악의 경우는 데이터 입력 상태 중 알고리즘이 가장 오래 걸리는 경우를 말합니다.
• 최악의 경우의 성능을 나타내기 때문에 알고리즘의 안정적인 최소 성능을 보장할 수 있습니다.

 

예를 들어,

• `f(n)=3n²+2n`이면 f(n)의 Big O는 `g(n)= n²`이다.
• `f(n)=4n³+n+5`이면 f(n)의 Big O는 `g(n)= n³`이다.

이처럼 Big O 표기법에서는 아래 두 원리를 지키면 됩니다.

• 최고차항의 차수만 본다.
• 상수항은 무시한다.

 

 

이 그래프는 Big O 표기법에서 주로 사용되는 표기들의 입력 개수에 따른 성능 차이를 나타낸 것입니다.

알고리즘의 복잡도가 빨간 영역(`O(n²)`, `O(2n)`, `O(n!)`)에 속한다면 알고리즘 수정이 필요하다는 뜻입니다.

 

자주 사용되는 Big O 예시

 

• O(1) - 상수 시간: 입력 크기에 상관없이 일정함.
• O(logn) - 로그 시간: 입력 크기가 커져도 시간이 매우 느리게 증가 (예: 이진 탐색).
• O(n) - 선형 시간: 입력 크기에 비례하여 증가 (예: 배열 순차 탐색, 반복문).
• O(nlogn) - 선형 로그 시간: 효율적인 정렬 알고리즘에서 흔히 나타남 (예: 퀵 정렬, 병합 정렬).
• O(n2) - 2차 시간: 입력 크기의 제곱에 비례하여 증가 (예: 이중 반복, 버블 정렬).
• O(2n) - 지수 시간: 입력이 조금만 커져도 시간이 기하급수적으로 증가 (매우 비효율적).

 

---

참고자료

빅오 표기법 (big-O notation) 이란