📝Big O 표기법이란?
🔖Big O?
- 알고리즘의 성능을 수학적으로 나타낸 것이다.
- 시간 복잡도 또는 공간 복잡도를 표현할 수 있다.
- 데이터 또는 사용자의 증가율에 따른 알고리즘의 성능을 예측하는 것을 목표로 한다.
🔖Big O를 사용하는 이유?
- 표기법의 뜻을 이해한다면, 복잡도를 빠르게 설명할 수 있다.
다시말해 알고리즘 분석을 빠르게 할 수 있다. - 성능 예측을 통해 코드를 평가할 수도 있다.
🔖Big O 특징
- 상수항을 무시한다.
- 영향력 없는 항을 무시한다.
[예시]
O(2N) → O(N)
: 상수항 무시, O(2N)은 O(N)으로 표시한다.
O(N²+N+1) → O(N²)
: 영향력 없는 항 무시, O(N²+N+1)은 O(N²)으로 표시한다.
🔖시간 복잡도(Time Complexity)란?
- 알고리즘을 수행하는 데 얼마나 많은 단계(연산)로 이루어지는 지를 표현한 것이다.
(※알고리즘을 수행하는 데 걸리는 시간을 계산하는 것이 아님.)
🔖공간 복잡도(Space Complexity)란?
- 알고리즘을 수행하는 데 얼마나 많은 메모리를 사용하는 지를 표현한 것이다.
📝시간 복잡도로 보는 Big O 종류
🔖 O(1), Constant Time
- 입력 데이터의 크기와 상관없이 언제나 일정한 시간이 걸리는 알고리즘을 표현한다.
//예제(java code)
public boolean func(int[] n) {
//배열 n의 크기와 상관없이 n[0]이 0이면 true를, 0이 아니면 false를 반환한다.
return (n[0] == 0)? true : false;
}- O(1)을 그래프로 표현하기
-데이터가 증가해도 시간에 변함이 없다.
-다시 말해, 데이터가 증가해도 성능에 변함이 없다.
🔖O(N), Linear Time
- 입력 데이터 크기에 비례해서 시간이 걸리는 알고리즘을 표현한다.
//예제(java code)
public void func(int[] n) {
for(int i : n) {
System.out.println(i); //배열 n의 크기만큼 출력을 수행한다.
}
}- O(N)을 그래프로 표현하기
🔖O(N²), Quadratic Time
- 입력 데이터 크기의 제곱만큼 시간이 걸리는 알고리즘을 표현한다.
//예제(java code)
public void func(int[] n) {
for(int i : n) {
for(int j : n) {
System.out.println(i+j); //배열 n의 제곱 크기만큼 출력을 수행한다.
}
}
}- O(N²)을 그래프로 표현하기
🔖O(NM)
- 입력 데이터 크기의 곱만큼 시간이 걸리는 알고리즘을 표현한다.
//예제(java code)
public void func(int[] n, int[] m) {
for(int i : n) {
for(int j : m) {
System.out.println(i+j); //배열 n과 m 크기의 곱만큼 출력을 수행한다.
}
}
}- O(NM)을 그래프로 표현하기
🔖O(N³), Polynominal Time
- 입력 데이터 크기의 세제곱만큼 시간이 걸리는 알고리즘을 표현한다.
//예제(java code)
public void func(int[] n) {
for(int i : n) {
for(int j : n) {
for(int k : n) {
System.out.println(i+j); //배열 n의 크기 세제곱만큼 출력을 수행한다.
}
}
}
}- O(N³)을 그래프로 표현하기
-데이터가 증가함에 따라 O(N²)의 그래프보다 더 급격하게 처리 시간이 증가한다.
🔖O(2ⁿ), Exponential Time
- 2의 입력 데이터 크기 제곱만큼 시간이 걸리는 알고리즘을 표현한다.
- 피보나치 수열을 예시로 생각하면 이 복잡도를 이해하기 쉽다.
//예제(java code) - 피보나치 수열을 구하는 재귀함수
public int func(int n) {
if(n <= 0) { return 0; }
else if(n == 1) { return 1; }
return func(n-1) + func(n-2);
}- O(2ⁿ)을 그래프로 표현하기
-데이터가 증가함에 따라 O(N²), O(N³)의 그래프보다 더 급격하게 처리 시간이 증가한다.
🔖O(log n), Logarithmic Time
- log 입력 데이터의 크기만큼 시간이 걸리는 알고리즘을 표현한다.
- 이진 탐색을 예시로 생각하면 이 복잡도를 이해하기 쉽다.
//예제(java code) - Binary Search Tree
public void func(int key, int[] arr, int start, int end) {
if(start > end) { return -1; }
int mid = (start + end) / 2;
if(arr[mid] == key) { return mid; }
else if(arr[mid] > key) { return func(key, arr, start, mid-1); }
else { return func(key, arr, mid+1, end); }
}- O(log n)을 그래프로 표현하기
-O(N)의 그래프보다 처리 시간이 적게 든다.
-O(log n)의 그래프를 보면 데이터가 증가해도 성능에 차이가 크지 않다.
📌Reference
참고 영상1 - Big O 표기법 완전정복
참고 영상2 - Big O 10분컷 설명
참고 영상3 - Array 기초 (+복잡도 설명)
참고 블로그 - 공간 복잡도
📌마치며
Big O Cheat Sheet에서 데이터 구조에 따른 복잡도의 Big O 표기를 확인할 수 있다.
