Algorithm - 점근적 표기법(Asymptotic notation)

https://www.freepik.com/

우리는 프로그래밍을 하면서 코드를 효율적으로 구현해야하는 숙제를 가지고 있습니다.

코드를 실행할 자원은 한정되어 있고 그렇기 때문에 우리는 같은 코드라면 빠른 시간내에 동작 가능한 쪽을 선택하는 것이 좋죠.

 

이렇게 알고리즘이 얼마나 걸리는지를 나타내는 방법으로 점근적 표기법이라는 것이 있습니다.

오늘은 이 점근적 표기법에 대해 알아보려고 합니다!

 

---

 

✅ 빅 오(O) 표기법

빅오 표기법은 제일 보편적으로 사용되는 표기법으로 가장 높은 차수 보다 같거나 높은 식을 뜻합니다.

이거보단 최소한 빠르다 라는 의미죠.

빅오 표기법은 알고리즘 최악의 실행시간을 나타냅니다.

 

예를들어,  f(n) = n^3 + 3n + 1 인 경우 가장 높은 차수는 n^3이므로 O(n^5), O(n^7), O(n^10) 모두 맞는 말입니다.

 

f(n)의 실행속도가 빅오 내부의 값들보다는 최소한 빠르다 라고 해석하면 이해가 쉬울 것 같습니다.

 

✅ 빅 오메가(Ω) 표기법

빅 오메가 표기법은 가장 높은 차수보다 같거나 낮은 식을 뜻합니다.

이거보단 더 걸린다 라는 의미죠.

빅 오메가 표기법은 알고리즘 최상의 실행시간을 나타냅니다.

 

예를들어, 아까와 같이 f(n) = n^3 + 3n + 1 인 경우 가장 높은 차수는 n^3이므로 Ω(n), Ω(n^2), Ω(n^3) 등이 가능합니다.

 

f(n)의 실행속도가 빅오메가 내부의 값들보다는 더 걸린다 라고 이해하면 될 것같습니다.

 

✅ 빅 세타(⍬) 표기법

마지막으로 빅 세타 표기법은 최고차항을 뜻합니다.

이 정도의 속도를 가지고 있다 는 의미죠.

빅 세타 표기법은 알고리즘의 평균 실행시간을 나타냅니다.

 

위 예시의 f(n)의 경우 빅 세타 표기법으로는 ⍬(n^3) 으로 표현될 수 있습니다.

 

 

점근적 표기법은 결국 n이 무한정 커졌을 때에 관심을 가지고 있기 때문에 식 앞에 있는 상수 값은 항상 무시합니다.

예를 들어 3n^3 과 100n^3은 동일하게 n^3으로 표현되는 방식이죠.

 

 

또 보통의 For문이 1억번 도는데 걸리는 시간은 1초 정도 입니다.

그리고 아래 내용들을 확인하면 N의 범위에 따른 대략적인 시간을 확인할 수 있습니다.

 

N≤10 : O(N!), O(2N), O(3N)

N≤20 : O(2N)

N≤100 : O(N4)

N≤500 : O(N3)

N≤1,000 : O(N2), O(N2logN)

N≤100,000 : O(N), O(NlogN), O(logN), O(1)

 

오늘은 이렇게 점근적 표기법에 알아보았습니다.