들어가기 전에
알고리즘의 효율성은 어떻게 비교할까요? 알고리즘의 효율성을 수학적으로 표시하는 빅 오 표기법에 대해 살펴보도록 하겠습니다.
학습 목표
빅 오 표기법을 이해하고, 표기 내용의 의미를 설명할 수 있습니다.
핵심 단어
- 알고리즘 비교
- 빅 오 표기법
강의 듣기
1-3. 빅 오 표기법
빅 오 표기법
빅 오 표기법은 알고리즘의 효율성을 표시하는 표기법입니다. 빅 오 표기법을 사용하면 어떤 알고리즘을 다른 알고리즘과 비교해서 표현하는 것이 가능합니다.
위 그래프는 복잡도가 nn 인 알고리즘에 빅 오 표기법을 적용한 결과입니다. x축은 복잡도 n, y축은 필요한 일의 양이나 메모리를 의미합니다.
다른 알고리즘이 이 그래프의 어떤 위치에 있는지에 따라 복잡도 nn 인 알고리즘과 다른 알고리즘의 복잡도를 비교할 수 있습니다. 다른 알고리즘이 복잡도 nn 인 알고리즘의 아래에 있다면, 같은 일을 하는 데 시간이 덜 들기 때문에 더 빠른 알고리즘이라 합니다. 반대로, 복잡도 nn 인 알고리즘의 위에 있다면, 더 느린 알고리즘입니다.
빅 오 표기법에서는 이러한 알고리즘 간의 관계를 다음과 같이 표현합니다.
- O (빅 오 복잡도) : 비교 대상인 그래프가 일치 혹은 아래에 있을 때. 비교 대상인 다른 알고리즘과 같거나 더 빠르다.
- θ (세타 복잡도) : 비교 대상인 그래프가 일치할 때. 비교 대상인 다른 알고리즘과 같다.
- Ω (빅 오메가 복잡도) : 비교 대상인 그래프가 일치 혹은 위에 있을 때. 비교 대상인 다른 알고리즘과 같거나 느리다.
- o (리틀 오 복잡도) : 비교 대상인 그래프가 아래에 있을 때. 비교 대상인 다른 알고리즘보다 더 빠르다.
- ω (리틀 오메가 복잡도) : 비교 대상인 그래프가 위에 있을 때. 비교 대상인 다른 알고리즘과 느리다.
생각해보기
1) 빅 오 표기법을 각각 부등호에 대응하면 어떤 것인가요?
2) 빅 오 표기법의 O는 무엇의 약자일까요?
comment
1) 빅 오 표기법을 각각 부등호에 대응하면 어떤 것인가요?
- 세타 = , 빅오: O>=, 리틀 오: o> , 빅오메가 : Ω <=, ω <
2) 빅 오 표기법의 O는 무엇의 약자일까요?
- 동일하게 증가하는 세타 복잡도보다 같거나 더 빠른
1. 빅 오 표기법(Big Oh notaion) 부등호 대응
- O (빅 오 복잡도) : O >=
- o (리틀 오 복잡도) : o >
- θ (세타 복잡도) : =
- Ω (빅 오메가 복잡도) : Ω <=
- ω (리틀 오메가 복잡도) : ω <
2. 빅 오 표기법 O의 약자
- Oh
1) 세타: =, 빅오: >=,작은오: >, 큰오메가: <=, 작은오메가: <
2) O는 Order of Approximation 이라는데...
O : .>=
o : >
세타 : ==
빅 오메가 : <=
리틀 오메가 : <
Order의 약자일 것 같습니다.
1) 빅 오 표기법을 각각 부등호에 대응하면 어떤 것인가요?
O: 비교하고자 하는 알고리즘이 같거나 빠른 속도( N >= )
Θ(세타): 같은 정도로 증가한다 ( N = )
Ω(빅 오메가): 같거나 느리다 ( N <= )
o(little o): 빠르지만 같지는 않다( N > )
2) 빅 오 표기법의 O는 무엇의 약자일까요?
Big - Oh
1) θ(n) 과 비교하여 부등호로 나타내면
O : <=
o : <
θ : =
Ω : >=
ω : >
2) 정확히 어떤 약자임은 찾을 수 없었으나, Order 의 약자로 보는게 합리적인 것 같다...
참조 : https://softwareengineering.stackexchange.com/questions/107976/what-is-o-in-big-o
O (빅 오 복잡도) : <=
θ (세타 복잡도) : =
Ω (빅 오메가 복잡도) : >=
o (리틀 오 복잡도) : <
ω (리틀 오메가 복잡도) : >
O> Order의 약자?
O. 연산 결과를 출력하기 때문에 Output의 머리글자가 아닐지.
O : =<
o : <
Θ : =
Ω : >=
ω : >
입력값에 숫자가 들어간다고 가정할 경우
빅오 <= 다른 알고리즘과 비교했을 때 같거나 빠르다. (숫자가 더 작다)
세타 = 다른 알고리즘과 같다 (숫자가 같다.)
빅 오메가 >= 다른 알고리즘과 비교했을때 같거나 느리다 (숫자가 더 크다.)
리틀 오 복잡도 < 다른 알고리즘보다 빠르다. (숫자가 작다.)
리틀 오메가 복잡도 > 다른 알고리즘보다 느리다. (숫자가 크다.)
1) 빅 오 표기법을 각각 부등호에 대응하면 어떤 것인가요?
O: 비교하고자 하는 알고리즘이 같거나 빠른 속도( N >= )
Θ(세타): 같은 정도로 증가한다 ( N = )
Ω(빅 오메가): 같거나 느리다 ( N <= )
o(little o): 빠르지만 같지는 않다( N > )
2) 빅 오 표기법의 O는 무엇의 약자일까요?
Big - Oh
1) 빅 오 표기법을 각각 부등호에 대응하면 어떤 것인가요?
O : <=, o : <, θ : =, Ω : >=, ω : >
2) 빅 오 표기법의 O는 무엇의 약자일까요?
Big-Oh
ω (리틀 오메가 복잡도) : 비교 대상인 그래프가 위에 있을 때. 비교 대상인 다른 알고리즘과 느리다.
'다른 알고리즘보다 느리다' 인데 오타가 난 것 같습니다.
1) time complexity에 대해서
O : <=
o : <
Θ : =
Ω : >=
ω : >
2) Oh