빅 오 표기법

들어가기 전에

알고리즘의 효율성은 어떻게 비교할까요? 알고리즘의 효율성을 수학적으로 표시하는 빅 오 표기법에 대해 살펴보도록 하겠습니다.

 

학습 목표

빅 오 표기법을 이해하고, 표기 내용의 의미를 설명할 수 있습니다.

 

핵심 단어

• 알고리즘 비교
• 빅 오 표기법

빅 오 표기법

 

빅 오 표기법은 알고리즘의 효율성을 표시하는 표기법입니다. 빅 오 표기법을 사용하면 어떤 알고리즘을 다른 알고리즘과 비교해서 표현하는 것이 가능합니다.

 

 

위 그래프는 복잡도가  nn 인 알고리즘에 빅 오 표기법을 적용한 결과입니다. x축은 복잡도 n, y축은 필요한 일의 양이나 메모리를 의미합니다.

 

다른 알고리즘이 이 그래프의 어떤 위치에 있는지에 따라 복잡도  nn 인 알고리즘과 다른 알고리즘의 복잡도를 비교할 수 있습니다. 다른 알고리즘이 복잡도  nn 인 알고리즘의 아래에 있다면, 같은 일을 하는 데 시간이 덜 들기 때문에 더 빠른 알고리즘이라 합니다. 반대로, 복잡도  nn 인 알고리즘의 위에 있다면, 더 느린 알고리즘입니다.

 

빅 오 표기법에서는 이러한 알고리즘 간의 관계를 다음과 같이 표현합니다.

- O (빅 오 복잡도) : 비교 대상인 그래프가 일치 혹은 아래에 있을 때. 비교 대상인 다른 알고리즘과 같거나 더 빠르다.

- θ (세타 복잡도) : 비교 대상인 그래프가 일치할 때. 비교 대상인 다른 알고리즘과 같다.

- Ω (빅 오메가 복잡도) : 비교 대상인 그래프가 일치 혹은 위에 있을 때. 비교 대상인 다른 알고리즘과 같거나 느리다.

- o (리틀 오 복잡도) : 비교 대상인 그래프가 아래에 있을 때. 비교 대상인 다른 알고리즘보다 더 빠르다.

- ω (리틀 오메가 복잡도) : 비교 대상인 그래프가 위에 있을 때. 비교 대상인 다른 알고리즘과 느리다.

 

---

 

생각해보기

1) 빅 오 표기법을 각각 부등호에 대응하면 어떤 것인가요?
2) 빅 오 표기법의 O는 무엇의 약자일까요? 

 

 

나의 생각 :

1) 

- O (빅 오 복잡도) :  O <= 같거나 숫자가 작거나

- θ (세타 복잡도) :  θ  = 같다

- Ω (빅 오메가 복잡도) : Ω >= 같거나 숫자가 크거나

- o (리틀 오 복잡도) :  o < 숫자가 작다.

- ω (리틀 오메가 복잡도) : . ω > 숫자가 크다. 

2) 비교 대상이랑 같거다 빠르거나 (빅 오 복잡도)

 

 

출처 : https://www.boostcourse.org/cs204/lecture/480381?isDesc=false 네이버커넥트재단