빅오 표기법이란?
빅오 표기법(Big-O notation)은 알고리즘의 소요시간(시간 복잡도) 또는 메모리의 상관관계(공간 복잡도)를 나타내줍니다.
항을 무시할 수 있는 경우
$$O(N+1000) -> O(N)$$
$$O(100N) -> O(N)$$
$$O(100N+1000) -> O(N)$$
위의 그래프에서 O(n)와 비교하면 O(1)은 영향력이 없다고 볼 수 있습니다. 그러므로 계수, 상수 항은 무시됩니다.
$$O(n!+nlogn) -> O(n!)$$
$$O(n!*nlogn) -> O(n!)$$
위의 그래프에서 O(n!)와 비교하면 O(nlogn)은 영향력이 없다고 볼 수 있습니다. 그러므로 비교적 증가율이 낮은 로그항은 무시됩니다.
그래프에는 보이지 않지만 O(n!)보다 복잡도가 높은 것이 하나 더 있습니다. O(n^n)입니다. 사실 O(n!)부터는 복잡도가 심각해지기 때문에 거의 사용하지 않습니다.
O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ) < O(n!) < O(nⁿ)
빅오 표기법 예제
O(1) 예제 : 스택에서 Push, Pop 할 때, 배열 인덱스에 접근할 때,
//예제 1
public String test(){
return "안녕";
}
//예제 2
public void test2(int[] arr){
System.out.println(arr[0]);
}
//예제 3
public void test3(int n){
int cnt = n;
}위의 예제 3개 전부 O(1)입니다.
O(log n) 예제 : 추후 알고리즘 포스팅 때 설명하겠습니다.
O(n) 예제 : for 문을 실행할 때
public int test(int n){
int sum = 0; // O(1) 입니다.
for(int i=0; i<n; i++) { // O(N)+1 입니다.(i<n인 부분도 확인해야 하기때문에 +1이 붙습니다.)
sum += i; //O(N) 입니다.
}
return sum; //O(1) 입니다.
}O(n log n) : 추후 알고리즘 포스팅 때 설명하겠습니다.
O(n^2) : 이중 for 문
public void test(int n){
int sum = 0; // O(1)
for(int i =0; i<n; i++){ //O(N)+1
for(int j =0; j<n ; j++){ //O(N)*(O(N)+1)+1
sum += i + j; // O(N)*(O(N)+1)
}
}
return sum; //O(1)
}전부 더해보면 $$O(1)+ O(N)+1+O(N^2)+O(N)+1+O(N^2)+O(N)+O(1)$$ =
$$2O(N^2)+3O(N)+2O(1)+2$$
위에서 배운 생략을 적용 시키면 $$O(N^2)$$가 됩니다.
O(2^n) : 추후 알고리즘 포스팅 때 설명하겠습니다.
※ 빅오 표기법 예시 정리
O(1)
-
배열 인덱스에 접근 할 때(int a = ARR[5];)
-
링크 리스트에서 노드를 삽입 할 때
-
스택에서 Push를 하거나 Pop을 할 때
-
큐에서 요소를 삽입하거나 제거 할 때
-
배열을 이용한 트리(ex: 이진트리)에서 부모 노드또는 자식 노드(왼쪽 노드, 오른쪽 노드)를 찾을 때
-
더블 링크드 리스트에서 이전이나 다음 요소로 넘어갈 때
O(n)
선형 성을 (linearity)을 필요로 하는 모든 알고리즘에 적용됩니다.
-
배열을 탐색 할 때
-
링크드-리스트를 탐색 할 때
-
선형 검색(Linear Search)
-
링크드-리스트의 특정 요소를 제거할 때(정렬되지 않은 상태)
-
Comparing two strings 두개의 문자열을 비교 할 때
-
Palindrome 체크 할 때 ( Palindrome이란 거꾸로 해도 원래의 문자열과 같은 문자열 특징을 가지고 있는 문자열 입니다.) (예: 리효리는 거꾸로 해도 리효리)
-
카운팅(Counting), 버킷(Bucket) 정렬
O(log n)
-
이진 검색(Binary Search)
-
이진 검색트리에서 최대 / 최소 수를 찾을 때
-
선형 기능을 기반으로 하는 특정 분할 / 정복 알고리즘
-
개선된 피보나치 정렬
O(n log n)
'log n' 은 Divide and Conquer를 고려하여 도입되었습니다. 이 알고리즘들은 최적화된 것들이므로 자주 사용됩니다.
-
병합 정렬(Merge Sort)
-
히프 정렬(Heap Sort)
-
퀵 정렬(Quick Sort)
-
특정 O(n^2) 기반의 분할 정복(Divide and Conquer)알고리즘
O(n^2)
-
버블 정렬(Bubble Sort)
-
삽입 정렬 (Insertion Sort)
-
선택 정렬 (Selection Sort)
-
간단한 2D 배열을 탐색 할 때
글에 오류가 있으면 알려주세요. 감사합니다.
REFERENCES