시간 복잡도

Time Complexity

개요

시간 복잡도는 코드의 실행 시간이 입력값에 따라 어떻게 변하는지를 나타내는 개념입니다. 쉽게 말해, 입력이 커지면 코드가 얼마나 느려지는지를 나타내는 것입니다.

Big-O 표기법

어떤 코드에서 입력값 에 따른 실행 시간이 라고 할 때, 의 증가율이 보다 크지 않다는 것을 수학적으로 나타내기 위해 Big-O 표기법을 사용합니다. 와 같이 씁니다.

간단하게 기억하는 법

에서 최고차항만 남기고 모두 제거하고 계수를 생략한다고 생각하면 됩니다. 예를 들어 이든 이든 둘 다 입니다. 이때 생략한 계수는 상수라는 이름으로 자주 불리며, 같은 시간 복잡도여도 상수가 크면 느립니다.

시간 복잡도를 나타낼 때에는 일반적으로 을 사용하지만 의미를 나타내기 위해 다른 문자를 쓰기도 합니다.

• 에라토스테네스의 체:
• 벨만-포드:

기타 점근 표기법

Big-O 표기법 외에도 여러가지 표기법이 있습니다.

표기법	설명
	는 의 상한
	는 보다 빠르게 증가
	는 의 하한
	는 보다 느리게 증가
	는 와 증가 속도가 같음

— 상수 시간

입력 크기에 관계없이 항상 일정한 시간만 걸리는 경우.

예:

• 배열의 인덱싱
• 해시를 이용한 집합과 맵에서 삽입/제거/검색
• 간단한 사칙연산

— 로그 시간

입력이 커져도 실행 시간이 아주 조금씩 커지는 경우.

예:

• 이분 탐색
• 힙에서 삽입/제거
• 이진 탐색 트리에서 삽입/제거/검색

일반적으로 는 보통 이진 로그를 뜻하지만 에라토스테네스의 체()처럼 아닌 경우도 있습니다.

— 선형 시간

코드의 실행 시간이 입력값에 정비례하는 경우.

예:

• 누적 합
• KMP
• 배열 내에서 원소 검색

— 선형 로그 시간

선형 시간보다 조금 더 느린 경우.

예:

• 병합 정렬, 퀵 정렬
• 볼록 껍질
• 최소 스패닝 트리

— 이차 시간

입력값이 커지면 연산 횟수가 제곱으로 증가하는 경우.

예:

• 버블 정렬, 선택 정렬, 삽입 정렬
• LIS(다이나믹 프로그래밍)

— 삼차 시간

입력값이 커지면 연산 횟수가 세제곱으로 증가하는 경우.

예:

• 플로이드-워셜

— 지수 시간

입력값이 커지면 연산 횟수가 기하급수적으로 증가하는 경우.

예:

• 모든 부분집합 구하기
• 부분 집합 백트래킹

— 계승 시간

코드의 실행 시간이 입력값의 계승에 비례하는 경우.

예:

• 순열, 조합 구하기

실제 시간

시간 복잡도를 알고 있으면 코드의 실제 실행 시간도 대략 예측할 수 있습니다. 보통 시간 복잡도의 변수에 수를 넣었을 때 값의 억당 초 정도로 계산합니다.

예를 들어 시간 복잡도 인 코드에 인 입력이 들어오면 은 약 이므로 초 정도의 시간이 소요될 것이라 예측할 수 있습니다. 만약 시간 복잡도 인 코드에 인 입력이 들어오면 은 이므로 약 초 정도의 시간이 소요될 것이라 예측할 수 있습니다.

백준의 문제들에는 시간 제한이 있으므로 코드의 시간 복잡도를 계산하여 제한 시간 내에 통과할 수 있는지 판단하는 것이 중요합니다.