빅오 표기법 (big-O notation) 이란

 컴퓨터 과학(Computer Science) 에서 알고리즘은 어떠한 문제를 해결하기 위한 방법이고,

어떠한 문제를 해결 하기 위한 방법은 다양하기 때문에 방법(알고리즘) 간에 효율성을 비교하기 위해

빅오(big-O) 표기법을 보통 가장 많이 사용한다.

(결국은 알고리즘 공부를 하려면 배워야한다는..)

빅오 표기법 (big-O notation) 이란?

 

 빅오 표기법은 알고리즘의 효율성을 표기해주는 표기법이다. 

쉽게 생각하면 알고리즘 스카우터라 생각하면 된다 :)

알고리즘의 효율성은 데이터 개수(n)가 주어졌을 때 덧셈, 뺄셈, 곱셈 같은 기본 연산의 횟수를 의미한다.

빅오 표기법은 보통 알고리즘의 시간 복잡도와 공간 복잡도를 나타내는데 주로 사용 된다.

(시간 복잡도는 알고리즘의 시간 효율성을 의미하고, 공간 복잡도는 알고리즘의 공간(메모리) 효율성을 의미한다.)

그런데 시간과 공간 복잡도를 나타내는 방법으로는 점근 표기법이라고 해서 

빅오(Big-O), 빅오메가(big-Ω),빅세타(big-Θ) 표기법이 있다.

 

 

그렇다면 세 가지 중 왜 빅오 표기법을 사용할까?

 

 결론부터 말하자면 빅오 표기법은 알고리즘 효율성을 상한선 기준으로 표기하기 때문이다. (알고리즘 효율성은 값이 클수록 즉, 그래프가 위로 향할수록 비효율적임을 의미한다.)

빅오메가는 하한선을 기준으로하고, 빅세타는 상한선과 하한선의 사이를 기준으로 표기한다.

일상의 대화에서 비유하자면 법정 최고이자율이 24% 인데 친구가 사채대출의 이자율을 물어본다.
(이자율이 높을수록 최악의 경우이다.)

하지만 정확한 법정 최고이자율이 생각나지 않는다.

이때 친구에게 빅오 표기법으로 말하자면 사채대출을 받으면 이자율이 30% 안에서 책정 될거야 라고 말하는 것과 같다.

(실제로 정확하진 않지만 대략 30%를 넘지 않을 것을 알고 모든 경우의 수를 포함하도록 말하는 것이다.)

빅오메가 표기법으로 말하자면 이자율이 0% 이상 일거야 라고 말하는 것과 같다. (사실상 의미가 없다.)

빅세타 표기법으로 말하자면 이자율이 0%(하한) 와 30%(상한) 의 사이쯤 이라고 말하는 것과 같다.

(빅세타는 하한과 상한 사이 평균정도의 의미로 쓰인다.)

 여기서 주의할 점은 빅오 표기법이 상한선만 지정했을 뿐 상한선이 꼭 알고리즘 효율성의 최악의 경우는 아니라는 것이다.

예를들어 법정 최고이자율이 24% 라서 사채의 이자율은 24%를 넘을 수 없다. 내가 30% 안이라고 해서 친구가 사채의 이자가 최대 30%까지 될 수도 있겠다고 생각할 필요는 없는 것이다. 이자율이 최악으로 가장 높은 경우인 24% 가 이자율 30% 안에 포함된다는 말일 뿐이다.

 

 

빅오 표기법의 수학적 정의

 

 빅오 표기법이 나타내는 의미는 수학적 정의를 통해 알 수 있다. 점근 표기법 중 빅오 표기법을 보통 가장 많이 사용하기 때문에 빅오 표기법의 수학적 정의 정도만 보고 넘어가자.

빅오 표기법의 수학적 정의는

 

   

 

간단하게 예를들자면

 

은 내가 만든 알고리즘의 시간 효율성(running time) 을 의미하고 충분히 큰 값인 n과 상수 k에 대해

 

 

이라고 가정하면

 

   (  ) 가 성립하는 k 값이 존재하기 때문에 내가 만든 알고리즘  은 빅오 표기법을 사용하여 로 나타낼 수 있다.

 

 

추가적인 이해를 돕기 위해 아래 그래프를 보자.

 

 

 

내가만든 알고리즘의 시간 효율성(running time)을 보여주는 그래프가 이다.

이때  보다 충분히 큰 입력값 n 을 넣었을 때 내가만든 알고리즘 의 running time이 최악인 경우에도 점근 상한선인  을 넘을수가 없다.

이때를 빅오 표기법을 사용하여  이라고 나타내는 것이다.

(위의 예시에서는  )

 

 

 

빅오 표기법의 특징

 

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

예를들어

 

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

 

 

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

예를들어

 

와 같이 영향력이 지배적인  이외에 영향력이 없는 항들은 무시한다.

 

 

 

빅오 표기법 성능비교

 

 빅오 표기법에서 주로 사용되는 표기법은 아래 그래프와 같다.

 

 

그래프에 나와 있는 시간 복잡도의 성능을 비교하면 다음과 같다.

(왼쪽에서 오른쪽으로 갈수록 효율성이 떨어진다.)

                                                           

faster    slower

 

( 상수함수 < 로그함수 < 선형함수 < 다항함수 < 지수함수 )

 

 

 

빅오 표기법 예제

 

 빅오 표기법의 예제는 어떤 것들이 있는지 정도만 외워두고 알고리즘 공부를 해보면서 이해해 나가면 될 것 같다.

 

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(): 이중 for 문, 삽입정렬(insertion sort), 거품정렬(bubble sort), 선택정렬(selection sort)

6. O() : 피보나치 수열