우리는 알고리즘의 속도를 예측할 수 있어야 합니다. 그래야 무엇이 더 빠른 알고리즘인지 감별할 수 있기 때문입니다.
만약, 제가 만든 알고리즘의 시간 복잡도가 n^2/2 * e + 1.345n + 32이라면 n이 증가함에 따라 시간 복잡도가 어떻게 증가할지를 한눈에 파악하는 것은 매우 어렵습니다. 게다가 100000000n + 12345의 시간 복잡도를 갖는 또 다른 알고리즘과 속도 비교를 하기란 더더욱 어렵습니다. 그러나 위 두 식이 n^2과 n처럼 단순화된 형태라면 각각의 증가량과 두 식 간의 차이를 단숨에 파악할 수 있을 것입니다. 이를 가능하게 해주는 것이 바로 점근 표기법입니다. 우리는 점근 표기법을 사용하여 식을 단순화할 수 있습니다.
점근 표기법은 최고차 항의 차수만 남기고 다른 모든 항과 최고차 항의 계수를 무시합니다. 다른 모든 항과 최고차 항의 계수를 무시할 수 있는 이유는 미지수가 커지면 커질수록 최고차 항의 차수를 제외한 나머지 것들의 영향은 작아지기 때문입니다.
예를 들어, n^2 + 2n + 1을 점근 표기법으로 표현하면 n^2입니다.
n^2 + 2n + 1과 n^2의 차이는 2n+1입니다. 2n+1이 전체 식에서 차지하는 비율을 구하려면 2n+1 / n^2+2n+1을 계산하면 됩니다.
n = 2일 때 2n + 1이 전체 식에서 차지하는 비율은 55%나 되지만 ( 2*2+1 / 2^2+2*2+1 = 0.555555555555556 )
n = 10000이 되면 2n+1은 전체의 0.02%밖에 되지 않습니다. ( 10000*2+1 / 10000^2+10000*2+1 = 0.000199970004 )
따라서 n값이 커지면 커질수록 n^2 + 2n + 1로 계산하나 n^2로 계산하나 비슷해집니다. 프로그래밍 세계에서의 입력(서버에 대한 요청이라던지 이미 저장되어 있는 수많은 정보라던지)은 10개 20개 정도가 아니라 몇 만, 몇 억 혹은 그보다 큰 경우가 많습니다. 그러므로, 점근 표기법을 사용하여 알고리즘의 속도를 예측하는 것은 프로그래밍 세계에 아주 알맞은 도구라 볼 수 있습니다.
n값이 커질수록 두 식 간의 차이의 비는 작아지므로 둘은 점차 근접해 간다 볼 수 있다. 그래서 이를 점근 표기법이라 합니다. 다만 2n+1이 차지하는 비율이 매우 작아질 수는 있어도 아예 0%가 될 순 없으므로 둘이 같아지는 경우는 없습니다.
점근 표기법은 다음 5가지 대표적인 표기법이 있습니다.
- 대문자 O 표기법
- 소문자 o 표기법
- 대문자 오메가(Ω) 표기법
- 소문자 오메가(ω) 표기법
- 대문자 세타(𝛩) 표기법
이 중 대문자 O 표기법과 대문자 오메가(Ω) 표기법, 대문자 세타 표기법(𝛩)에 대해 알아봅시다.
대문자 O 표기법 ( big-O )
big-O는 시간의 상한을 나타냅니다. 예를 들어, 소요 시간이 n^2 + 2n + 1인 알고리즘의 경우 빅오 표기법으로 O(N^2)으로 나타낼 수도 있지만, O(N^3), O(2^n)으로 나타내는 것도 가능합니다. 알고리즘의 수행 시간은 이것들보다 빠르거나 같으면 됩니다. 다시 말해 O(g(n))이 f(n) 이상이기만 하면 됩니다. 이때 g(n)을 점근 상한 이라 합니다.
대문자 오메가(Ω) 표기법
big-Ω는 시간의 하한을 나타냅니다. 예를 들어, 소요 시간이 n^2 + 2n + 1인 알고리즘의 경우 빅 오메가 표기법으로 Ω(N^2)으로 나타낼 수도 있지만, Ω(N), Ω(1)으로 나타내는 것도 가능합니다. 알고리즘의 수행 시간은 이것들보다 느리거나 같으면 됩니다. 다시 말해 Ω(g(n))이 f(n) 이하이기만 하면 됩니다. 이때 g(n)을 점근 하한이라 합니다.
대문자 세타(𝛩) 표기법
big-𝛩는 big-O 이하면서 big-Ω 이상인 것을 나타냅니다. 따라서 𝛩는 O, Ω 둘 중 아무거나 될 수 있습니다. 소요 시간이 n^2 + 2n + 1인 알고리즘이 O(N^2), Ω(N^2)으로 나타낼 수 있었습니다. 따라서 𝛩(N^2)으로 나타낼 수도 있습니다. 또, Ω(1)로 나타낼 수 있었으므로 𝛩(1)로도 나타낼 수 있고 O(N^3)으로 나타낼 수 있었으므로 𝛩(N^3)으로 나타낼 수도 있습니다.
정리
시간 복잡도 식이 복잡하면 그게 얼마나 걸린다는 건지 그리고 다른 시간 복잡도와 비교할 때 무엇이 빠르다는 건지 알기 쉽지 않습니다. 따라서 식을 단순화 하고 싶은데, 그때 사용할 수 있는 것이 점근 표기법입니다. 우리는 점근 표기법을 사용하여 식을 단순화할 수 있습니다.
접근 표기법은 빅 오, 빅 오메가, 빅 세타 등이 있습니다.
- 빅 오 - 실제 걸리는 시간 이상을 나타냅니다.
- 빅 오메가 - 실제 걸리는 시간 이하를 나타냅니다.
- 빅 세타 - 빅 오, 빅 오메가 둘 중 아무거나 될 수 있습니다.
https://ratsgo.github.io/data%20structure&algorithm/2017/09/13/asymptotic/
점근 표기법(asymptotic notation) · ratsgo's blog
이번 글에서는 내가 만든 알고리즘이 얼마나 효율적인지를 따져보기 위한 도구인 점근 표기법(asymptotic notation)에 대해 살펴보도록 하겠습니다. 이 글은 고려대 김황남 교수님과 역시 같은 대학
ratsgo.github.io
모두의 알고리즘 - 1. 어떤 알고리즘이 효율적인가?
modoocode.com
'알고리즘, 자료구조' 카테고리의 다른 글
| 최장 증가 부분 수열 (Longest Increasing Subsequence, LIS) (0) | 2023.04.24 |
|---|---|
| 가장 긴 부분 회문 찾기 palindrome (2) | 2022.10.07 |
| 해시 (0) | 2022.07.06 |
| 완주하지 못한 선수 (0) | 2022.07.04 |
| ArrayList,LinkedList 비교 (0) | 2022.07.01 |