[CS기초] 알고리즘 복잡도(Big-O Notation)

Big-O 표기법

알고리즘의 성능을 분석할 때에는 시간 복잡도와 공간 복잡도를 고려해야 하는데요. 이를 표현하는 대표적인 방법이 Big-O 표기법입니다.

• 알고리즘의 실행 시간 또는 메모리 사용량이 입력 크기(n)에 따라 어떻게 변하는지 나타내는 표기법
• 보통 최악의 경우(Worst Case)를 기준으로 성능을 분석
• 가장 큰 차수만 나타내고, 계수는 무시 ( 예) O(3N + 5) → O(N) )

 

시간 복잡도 (Time Complexity)

알고리즘이 실행되는 데 걸리는 연산 횟수의 증가율을 나타냅니다.

주요 시간 복잡도 유형

시간 복잡도	설명	예제
O(1)	상수 시간. 입력 크기에 관계없이 실행 시간이 일정	배열 인덱싱, 스택 push / pop
O(logN)	로그 시간. 입력 크기가 2배가 되어도 실행 시간은 조금만 증가	이진 탐색
O(N)	선형 시간. 입력 크기에 비례해 실행 시간 증가	배열 순회
O(NlogN)	선형 로그 시간. 대부분의 정렬 알고리즘이 여기에 속함	퀵 정렬(평균), 병합 정렬
O(N2)	이차 시간. 입력 크기 증가에 따라 실행 시간이 급격히 증가	버블 정렬, 삽입 정렬
O(2n)	지수 시간. 입력 크기 증가에 따라 실행 시간이 매우 급격히 증가	피보나치 재귀
O(N!)	팩토리얼 시간. 입력 크기 증가에 따라 실행 시간이 매우매우 급격히 증가	순열 생성

 

 

공간 복잡도 (Space Complexity)

알고리즘이 사용하는 메모리 공간의 증가율을 나타냅니다. 다만, 컴퓨터 성능이 좋아짐에 따라 시간 복잡도에 비해 중요도가 점점 낮아지고 있습니다.

• 변수 사용 → O(1) (상수 공간)
  • 단순한 변수 저장 (O(1))
• 배열, 리스트 등 사용 → O(N)
  • N개의 원소를 저장하는 배열 (O(N))
• 배열 등의 차원이 늘어날 때마다 → O(N2), O(N3) 증가
  • N x N 행렬 (O(N²))