Big-O Notaion 빅 오 표기법 - 알고리즘의 시간 복잡도를 나타내는 표기법

 빠르고 느림은 상대적인 표현이다. 효율성을 중요시하는 알고리즘 세계에서 빠르고 느림을 표현하는 척도는 무엇일까?

 

1. 빅 오 표기법이란?

 Big - O Nation, 즉 '빅 오 표기법'은 알고리즘의 시간 복잡도를 나타내는 표기법이다. 

 이 표기법을 통해 알고리즘의 빠르고 느림을 표현할 수 있고 코드가 얼마나 효율적인지 평가할 수 있다.

 참고로 시간복잡도의 3가지 표현은 다음과 같은데, Big-O(빅-오) 표기법을 사용하는 이유는 최선의 경우를 고려했어도 최악의 경우가 발생할 수 있기에 최악의 시간을 기본적으로 대비하는 것이 바람직하기 때문이다. 이를 전문적으로 표현하면 빅 오표기법은 알고리즘의 효율성을 상한선을 기준으로 표기한다고 한다. (x축이 입력크기, y축이 실행시간일 때, 그래프가 위로 향할수록, 즉 상한선일수록 비효율적이다.)

 

---

 2. 빅 오 표기법의 특징 

- 무한 번 입력했을 때 어떻게 될지 생각해 보자.

 

(1) 상수(Constant)항을 무시한다. 

0(5N) ❌ -> O(N) ⭕️

 입력하는 값의 개수가 n이라고 하였을 때, n이 무한대로 켜졌을 때 상수는 무의미하므로 상수 5는 무시한다. 

 

0(300) ❌ -> O(1) ⭕️ 

 

(2) 최고차항만 표시된다.

O(8n^2 + 4n + 3)❌ -> O(n^2)⭕

 n이 무한대로 커졌을 때, 상수항과 일 차 항보다 이차항의 비중이 훨씬 크므로 무시된다.

 

---

3. ⭐️ 빅 오 표기법의 종류 

시간 복잡도 순위	Big - O Notation
O(1)	상수시간. (입력크기와 상관없이 연산횟수 고정)
O(logN)	로그. (입력크기 증가율 > 연산횟수 증가율)
O(N)	선형. (입력크기 & 연산횟수 비례)
O(NlogN)	로그선형. (입력크기 2배 증가시 연산횟수 2배 조금 넘어서 증가)
O(N²)	이차. (입력크기n 연산횟수n²)
O(N³)	삼차. (두 n Χ n 행렬의 곱)
O(Cⁿ)	지수. (지수적으로 증가/ 여행하는 외판원 문제, 집합 분할 문제)

 

 

(1) O(1)  Constant time (상수 시간 복잡도)

• 입력하는 값의 개수 n이 얼마나 크던 고정된 단계의 횟수로 끝나기 때문에 가장 효율적이다.
• ex) Stack의 Push, pop

 

(2) O(log n) Logarithmic time (로그 시간 복잡도)

• 입력 크기 n이 증가하는 양에 비해 연산 단계 횟수가 비교적 적게 일어난다.
• ex) 이진검색 알고리즘

 

(3) O(n) Linear time (선형 시간 복잡도)

• 입력 크기 n이 증가하면 연산 단계도 n번 증가하여 실행한다.
  • 예를 들어 입력값 1이면 1초, 100배 증가하면 100초가 걸린다.
• ex) for문 

 

(4) O(n logn)

• 입력 크기가 2배 증가하면 연산 횟수 2배 조금 넘게 증가한다.
• ex) 퀵 정렬 (quick sort), 병합 정렬 (merge sort), 힙 정렬 (heap sort)

 

(5) O(n**2) Quadratic time (2차 시간 복잡도)

• 입력 크기 n에 의해 n 제곱수 비율로 증가하여 n**2 번 실행한다
  • 예를 들어 입력값이 1일 때 1초였는데, 입력값이 5라면 25초가 걸린다.
• ex) 이중 for문, 삽입정렬, 버블정렬, 선택정렬과 같은 비효율적인 중첩 정렬 알고리즘이 이에 해당된다.

 

(6) O(2**n) Exponential Time

• 지수의 n제곱만큼 늘어나는 복잡도
  • ex) 피보나치 수열 

 

++ 알고리즘 TIP

• 입력 데이터의 크기 제한과 실행 시간 범위를 고려하면 문제에 대한 감을 잡을 수 있다. ⭐️ 보통 코드 1억 번 수행 시간은 1초이다. 

데이터 크기 제한	예상되는 시간 복잡도
n ≤ 1,000,000	O(n), O (logn)
n ≤ 10,000	O(n**2)
n ≤ 500	O(n**3)