빅오 (Big O) 표기법

빅오(Big O) 표기법은 알고리즘의 성능을 분석시 사용하는 수학적 표현이다. 알고리즘 처리 할 데이터의 양이 증가할 때 알고리즘이 얼마나 빠르게 실행되는지 나타내게 된다.
빅오 표기법으로 인한 데이터 양의 증가에 따른 성능 변화 추세를 이해할 수 있다.

빅오 표기법

연산수
+     O(n**2) O(n log n) O(n)
|       |       /       /
|       |      |      /
|       |      /    /
|       |     /   /
|       |    /  /
|       /     /
|      /    /          _____ O(log n)
|      /  /        /
|     / /  ________
|   / /   /
| +--------------------------O(1)
| |/
| +
+---------------------------- 데이터 크기

• 빅O 의 차트이다.

빅오 표기법 예시

• O(1)
  • 상수 시간 차트. 입력 데이터 크기와 관계 없이 실행 시간이 일정하다.
  • 가장 빠름
• O(n)
  • 선형 시간 차트. 알고리즘 실행 시간이 입력 데이터 크기와 비례해서 증가한다.
  • for 문에서 배열의 값을 검색한 상황이 O(n) 이다.
• O(n**2)
  • 제곱 시간 차트. 알고리즘 실행 시간이 입력 데이터 크기와 제곱으로 비례해서 증가한다.
  • 데이터 크기가 100인 경우 1000000 번을 검색한다.
  • 이중 for문에서 발생한다.
• O(log n)
  • 로그 시간 차트. 알고리즘 실행 시간이 입력 데이터 크기 로그에 비례해 증가한다.
  • 이진 탐색 알고리즘
• O(n log n)
  • 선형 로그 시간 차트.
  • 데이터 크기가 적은 경우 빠르지만 양이 늘어날수록 로그에 비례해 증가한다.
  • 효율적인 정렬 알고리즘들에서 자주 사용한다.

빅오 표기법은 알고리즘이 데이터 크기에 따라 성능 변화 추세를 알아보는데 사용한다.
정확한 성능이 아닌 크기가 큰 데이터가 들어온 경우 알고리즘 추세를 보고 비교하는 것이다. 데이터가 많이 온 경우 추세의 상수가 의미 없어지므로 제거된다.

• 빅오 표기법은 입력 데이터 크기에 따른 성능 변화 추세
• 매우 큰 데이터인 경우 상수의 의미가 없어서 제거
  • 상수 제거 예시. O(n+2), O(n/2) 표기에서 숫자를 제거하고 O(n) 로 통일

알고리즘의 상황

빅오 표기법은 최악의 상황을 가정해서 말하고, 상황을 최적, 보통, 최악으로 나누어 성능의 비교로 사용한다.

배열의 순차 검색의 상황

• 최적의 경우
  • 배열의 첫 번째 항목에서 값을 찾아낸 경우 O(1) 속도가 된다.
• 최악의 경우
  • 마지막 항목에 값을 찾아낸 경우 모든 배열을 탐색하였으므로 O(n) 속도가 된다.
• 보통의 경우
  • 탐색 중간에 찾을 찾아낸 경우 평균적으로 탐색하였으므로 O(n/2) 표기하나, 상수를 제외하고 O(n) 이 된다.
  • 상수를 제거하면 최악의 경우와 같아지므로 비교를 위해 O(n/2) 표기하기도 하다.

배열의 인덱스 사용으로 양과 관계 없이 결과를 즉시 찾아낸 경우 항상 O(1)이 될 것이다.

배열의 성능 정리

• 배열의 인덱스를 알고 있으며 사용한 경우 O(1) 속도가 된다.
• 배열의 인덱스를 모르므로 순차적으로 검색한 경우 O(n) 속도가 된다.