알고리즘 효율 분석 | 시간 복잡도, 빅오 표기법

1. 시간 복잡도 (Time Complexity)

• 알고리즘의 성능을 나타내는 지표
• 입력 크기 n에 따라 연산 횟수가 어떻게 증가하는지를 나타낸다
  즉, 입력 크기가 커질수록 성능이 어떻게 변하는지를 수학적으로 분석하는 것 
• 시간 복잡도는 낮을 수록 좋다
• 주로 빅오 표기법(Big-O Notation)을 사용해서 표현

 

2. 빅오 표기법 

2-1. 빅오 표기법

• 최악의 경우 시간 복잡도를 표현하는 방법 
• 시간 복잡도의 점근적 상한 (상한선: 빅오, 하한선: 빅오메가)
• 어떤 프로그램의 연산 횟수가 f(x)라고 할 때, f(x)에서 가장 영향이 큰 항만 남기고 상수와 낮은 차수는 제거하는 방식으로 표현한다. 예: f(x)=2x² + 3x + 5 → O(x²)

2-2. 빅오 시간 복잡도 구하기 (빅오 상한의 정의)

• 다음을 만족하는 g(x)가 있으면 f(x)의 시간 복잡도는 O(g(x))이다.
  →  특정 x 시점 이후부터 항상 f(x) <= C * g(x)를 만족 (C는 상수, x가 충분히 클 때를 기준으로 본다)
• 쉽게 말해, C*g(x)가 특정 시점부터 f(x)를 넘어서는지 여부를 보면 된다. 
• 단, 다시 역전당해서는 안되고 C*g(x)가 계속해서 특정 시점 이후로 계속 f(x)를 넘어서야 한다. 

2-3. 가장 작은 차수의 점근적 상한만이 의미가 있다. 

• 빅오는 시간 복잡도의 점근적 상한으로서 빅오 상한의 정의 (위의 공식)를 만족하는 시간 복잡도 함수들의 집합으로 해석할 수 있다. 예를 들어 f(x) = x²이면, x³, 5x! 등 모두 점근적 상한 조건을 만족하므로 빅오 상한에 만족하는 함수 집합에 속한다. 
• 그러나, 우리가 보통 빅오 표법을 쓸 때는 최대한 정확한, 빡빡한(타이트한) 상한을 찾는다. 실제로 f(x)=x² 인데, "최악의 경우 x³ 이하"라고 표현하는 건 너무 과장된 정보이기 때문이다. 그래서 보통 "가장 작은 차수의 점근적 상한"을 빅오 표기법으로 사용한다. 
• 예: f(x)=x²+x
  • O(x²) → 가장 작은 차수의 상한 (타이트한 상한)
  • O(x³) → 너무 큰 상한 (사용하지 않음)

2-4. 최고차항만 남기는 이유 

• 빅오는 "정확한 실행 횟수"가 아니라 "성장률"을 나타낸다.
• 즉, 빅오 표기법은 정확한 실행 횟수를 구하는 게 아니라, n이 충분히 클 때 대략적으로 얼마나 빨리 증가하는지를 표현하는 방법이다.
• 그렇기 때문에 입력이 커질 때, 가장 영향력이 큰 항이 무엇인지를 파악해야한다.
• 최고차항 우선순위 : 지수 함수 > 다항함수 > 로그함수 
• 예시: f(x)=x²+3x+5
  • 작은 x일 때는 3x나 5가 영향을 줄 수도 있지만, x가 커질수록 제일 높은 차수의 항이 지배적이 된다.
  • x²항이 압도적으로 커지고, 3x나 5는 무시할 수 있는 수준이 되므로  O(x²)로 표현

x	x²	3x	5	f(x)
1	1	3	5	9
10	100	30	5	135
100	10,000	300	5	10,305
1,000	1,000,000	3,000	5	1,003,005

 

3. 알고리즘 문제에서 시간 복잡도 계산하기 

1) 문제에서 입력 크기 (n) 확인

• 보통 입력 크기의 제한 조건에 따라 현실적으로 풀 수 있는 알고리즘이 정해져 있다.
• 입력 크기에 따라 시간 복잡도가 정해져 있으므로 이 문제의 풀이에 어떤 알고리즘이 사용 가능한지 대략적으로 파악 가능하다.  
• 입력 크기에 따른 허용 시간 복잡도

n 크기 범위	적절한 알고리즘 시간 복잡도
n≤10	O(n!) 가능
n≤20~25	O(2ⁿ)
n≤200~300	O(n³)
n≤3000~5000	O(n²)
n≤100만	O(n log n)
n≤1000~2000만	O(n)
n≤10억	O(log n)

 

2) 내 알고리즘 풀이의 시간 복잡도 생각해보기 

• 반복문, 재귀 호출, 탐색, 정렬 같은 핵심 연산이 몇 번 실행되는지 따져본다. 
• 보통 가장 많이 중첩된 루프를 보면 판단하기 좋다. 
• 기본적인 시간 복잡도 패턴

코드 패턴	시간 복잡도	알고리즘
단일 반복문	O(n)	배열에서 최댓값 찾기
중첩 반복문	O(n²)	버블 정렬
이진 탐색	O(log n)	이진 탐색
분할 정복	O(n log n)	병합 정렬, 퀵 정렬(평균)
모든 경우 탐색	O(2ⁿ)	부분집합, 재귀적 백트래킹
순열/조합 생성	O(n!)	외판원 문제(TSP)

• 시간 복잡도 계산 예시 
  • 별찍기 문제: 이중 반복문 → O(n²) 
  • 박테리아 수명 문제: 계속 반으로 나눔 → O(logN)

출처: 코딩 테스트 합격자 되기 자바 편