[자료구조&알고리즘]Big O 표기법 (빅오) #2

빅오 표기법의 특징

 

1. 상수항 무시 : 빅오 표기법은 데이터 입력값(n)이 충분히 크다고 가정하고 있고, 알고리즘의 효율성 또한 데이터 입력값(n)의 크기에 따라 영향 받기 때문에 상수항 같은 사소한 부분은 무시한다.

예를들어

 

 와 같이 상수항은 무시하고 표기한다.

 

 

2. 영향력 없는 항 무시 : 빅오 표기법은 데이터 입력값(n)의 크기에 따라 영향을 받기 때문에 가장 영향력이 큰 항에 이외에 영향력이 없는 항들은 무시한다.

예를들어

 

와 같이 영향력이 지배적인

 이외에 영향력이 없는 항들은 무시한다.

 

 

 입력에 따라 알고리즘의 런타임이 어떻게 증가하는지에 대한 것이 바로 Big O이다.

즉 입력과 해당 입력에 따른 상대적인 시간 간의 관계이다.

다양한 기본적인 표기법이 존재한다.

1. 선형함수 f(n) = n
2. 지수함수 f(n) = n^2, f(n) = 2^n etc...
3. 상수함수 f(n) = 1
4. 이외의 다양한 함수

빅오 표기법에서 주로 사용되는 표기법을 시간 복잡도의 성능을 비교하는 그래프로

상수함수가 가장 효율성이 좋고 지수함수가 효율성이 제일 떨어지는 것을 볼 수 있다.

빅오 표기법의 표기법들에 대한 알고리즘의 관련을 보면 다음과 같다.

1. O(1) : 스택에서 Push, Pop
2. O(log n) : 이진트리
3. O(n) : for 문
4. O(n log n) : 퀵 정렬(quick sort), 병합정렬(merge sort), 힙 정렬(heap Sort)
5. O(n^2): 이중 for 문, 삽입정렬(insertion sort), 거품정렬(bubble sort), 선택정렬(selection sort)
6. O(2^n): 피보나치 수열

<빅5표현식의 단순화>

solution2의 함수는 항상 3개의 연산을 수행하여 n 의 입력과 관련없이 항상 고정적인 연산을 수행하므로 O(1) 에 해당하는 상수함수에 해당할 것이다.

solution1의 경우 for 문이 존재하여 n 의 값에 따라 증가한다. 우리는 이를 5n+2 로 정리했었다. 그렇다면 빅오 표기법은 O(5n+2) 로 정의할 수 있을까? 결론은 그렇지 않다.

 

solution1은 for 문을 통한 루프가 존재하며, 우리는 해당 코드에서 일어나는 연산을 5n+2 로 정의했었다. 그럼 빅오 표현식도 동일한가?

정답은 그렇지 않다. n 즉, 입력값에 따라 변동하는 빅오 표현식들( n^2 etc...)은 n 값을 크게 보면 다른 값들과 큰 차이성을 두각하지 않는다.

5n+2 나 10n 이나 n 값에 따라 증가하는 시간효율성의 비례는 다른 n^2 등의 지수함수 등과의 비교에는 큰 차이를 보이나 같은 함수식 끼리에서의 차이는 큰 두각을 보이지 않는다라는 것이다. 특히나 5n+2 뒤에 붙은 +2 는 더더욱

고정적과 유동적을 통해서 쉽게 빅오 표현식을 정의할 수 있다.

n 값에 영향을 받는가와 그렇지 않은가.

• n의 값에 영향을 받는다.
  • 로그 함수( O(log n), O(nlog n) etc...)
  • 선형 함수( O(n) )
  • 지수 함수( O(n^2) etc...)
• n의 값에 영향을 받지 않는다.
  • 상수 함수( O(1) )

즉 쉽게 말해 O(n^3 + n + n^2 + nlog n) 과 같더라도 제일 큰 상승폭을 지닌 것( O(n^3) )이 빅오 표현식이다.