빅오 표기법 (Big-O notation)

빅오 표기법이란?

빅오 표기법(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

https://stackoverflow.com/questions/1592649/examples-of-algorithms-which-has-o1-on-log-n-and-olog-n-complexities

 

https://en.wikipedia.org/wiki/Big_O_notation