자료구조와 알고리즘발행일 2026. 8. 28.

Big O 표기법을 코드로 이해하기

입력 크기가 증가할 때 실행 시간과 메모리가 어떻게 변하는지 실제 코드로 비교합니다.

#Algorithm#Big O#Complexity

증가율을 비교한다#

Big O는 정확한 실행 시간을 재는 도구가 아니라 입력 크기 n이 커질 때 비용의 증가율을 설명하는 표기입니다.

c++ 코드 예제

bool contains(const std::vector<int>& values, int target) {
  for (const int value : values) {
    if (value == target) return true;
  }
  return false;
}

위 선형 검색은 최악의 경우 모든 원소를 확인하므로 O(n)입니다.

자주 만나는 복잡도#

표기	대표 사례	입력이 두 배일 때
O(1)	해시 키 조회 평균	거의 동일
O(log n)	이진 검색	한 단계 증가
O(n)	선형 순회	약 두 배
O(n²)	이중 반복문	약 네 배

공간 복잡도#

실행 시간만 보지 말고 추가로 할당하는 메모리도 기록합니다. 원본 배열과 같은 크기의 배열을 만들면 추가 공간은 O(n)입니다.

정리#

복잡도는 구현 선택을 설명하는 공통 언어이며, 실제 성능 측정을 대체하지는 않습니다.