시간 복잡도 기초

시간 복잡도 규칙

• 입력값 n 은 항상 0 보다 크다.
• 모든 상수를 제거한다.
  • 예) 3n, 5n, 200n은 모두 n 이다.
• 낮은 차수의 항은 무시한다.
  • 예) n^3+n^2+n+5 ====> n^3
• log함수 일 때 밑을 무시한다.

 

빅 오 표기법(Big-Oh Notation)

• 알고리즘의 효율성을 표시하는 표기법

 

 

1. O (빅 오 복잡도)

• 비교 대상인 그래프가 일치 혹은 아래에 있을 때
• 비교 대상인 다른 알고리즘과 같거나 더 빠름.

2. o (리틀 오 복잡도)

• 비교 대상인 그래프가 아래에 있을 때
• 비교 대상인 다른 알고리즘보다 더 빠름.

3. θ (세타 복잡도)

• 비교 대상인 그래프가 일치할 때
• 비교 대상인 다른 알고리즘과 같음.

4. Ω (빅 오메가 복잡도)

• 비교 대상인 그래프가 일치 혹은 위에 있을 때
• 비교 대상인 다른 알고리즘과 같거나 느림.

5. ω (리틀 오메가 복잡도)

• 비교 대상인 그래프가 위에 있을 때
• 비교 대상인 다른 알고리즘과 느림.

 

부등호로 표현한 복잡도

O (빅 오 복잡도)	o (리틀 오 복잡도)	θ (세타 복잡도)	Ω (빅 오메가 복잡도)	ω (리틀 오메가 복잡도)
≥	>	=	≤	<

 

---

Quiz - True or False

 

• 가능한 큰 수를 대입해서 생각해봐라.
• 1000^(4/3) = 10 ^ (3 * (4/3)) = 10^4 = 10,000
• 1000 log(1000) = 1000 log 10^3 = 1000 * 3 = 3,000
• 아래 그림을 보면 False 인 것을 확인할 수 있다.

• 작은 차수는 무시한다는 규칙 적용
  • 3n^3만 남음
• 상수 제거
  • n^3 만 남음 → 따라서 세타 n^3에 속함.
• 정답은 True

 

• 작은 차수 제거 규칙 적용
  • n^2/2 만 남음
• 상수 제거
  • n^2만 남음 → 따라서 O(n^2)에 속함.
• 정답은 True

 

• 큰 수를 적용해보자
• 2^1000 = 1*10^103
• 1000
• 아래 그림을 보면 답은 True임을 알 수 있다.

• 정답은 False

 

• 정답은 True

 

---

• 참고

자바로 구현하고 배우는 자료구조