시간 복잡도 표기 - 점근적 표기법 (Big-O, Big-Θ, Big-Ω)

 

시간 복잡도 개념을 알았으니..

이제 시간 복잡도를 어떻게 표기하는 지 알아봅시다 !!

 

(아직도 시간 복잡도가 뭔지 모르신다면.. 아래 확인해보세요 😆)

시간 복잡도 (Time Complexity), 그리고 공간 복잡도 (Space Complexity)

 

---

다시 기억을 되살려보면,

우리는 시간 복잡도를 측정할 때

최악의 상황을 가정하고, 수행시간을 측정한다고 했습니다.

 

그렇다면 데이터 n개가 들어왔을 때 최악의 상황을 가정한다면,

n개의 입력에 대한 기본 연산 수행 횟수를  n의 관한 식으로 나타낼 수 있겠죠 ?!

 

(무슨 말인지 모르시겠다고요..?  아래 예시를 보면 이해가실 거에요! )

---

저번에 봤던 코드로 예를 들어보겠습니다 !

아래 함수는 배열에서 제일 큰 원소를 구하는 함수입니다.

// Swift
func findMaxValue(numbers: [Int]) -> Int {
    // 배열의 첫 번째 원소를 초기 최대값으로 설정
    var maxValue = numbers[0]

    // 나머지 원소들과 비교하여 최대값 갱신
    for number in numbers {
        if number > maxValue {
            maxValue = number
        }
    }

    return maxValue
}

 

분명, 이전 글에서는

정확한 시간 복잡도를 구할 수 없다고 넘어 갔지만, 

만약, 최악의 상황을 가정한다면 구할 수 있지 않을까요?

 

한 번 구해봅시다 !

 

위에 함수에서 최악의 상황은 무엇일까요?

 

numbers 배열에서 가장 큰 요소가 제일 끝에 위치한다면 

모든 경우의 연산을 해야지만 최대 값을 찾을 수 있을 겁니다.

 

(if문 내의 연산이 많이 일어나는 경우가 최악의 상황이겠죠!)

 

그렇다면 배열의 요소 개수를 n이라 하고, n을 이용하여 시간 복잡도 T(n)식 표현해봅시다 !

(반복문의 number의 대입 연산은 카운트하지 않습니다 !)

 

함수가 실행이 되면,

 maxValue에 원소를 저장하는데 연산이 1번 실행

 

 for문에서 배열의 길이가 n이기 때문에, 반복문 내의 if문 연산이 n번 실행

 

if문 내의 대입 연산은 첫 번째 경우를 제외하고, 매 번 실행이 되기 때문에 n-1번 실행

(첫 번째 상황에서 if문의 조건이 false가 나오니까 넘어가요!)

 

따라서, 총 2n의 시간 복잡도가 나오게 됩니다!

 

다시 말해, 배열의 요소 개수가 200이라면

최악의 경우에 400번의 연산이 발생한다는 말이죠!

---

 

하지만, 이렇게 매 번최악의 입력에 대한 기본 연산의 횟수를

정확시 구하는 건 일반적으로 귀찮고 까다롭습니다.

 

그렇다면..

다시 처음으로 돌아가서, 시간 복잡도를 왜 구하는 지 생각 해봅시다!

 

우리는 시간복잡도를 함수가 정확히 몇 번 연산을 하는 지를 구하기 보다는,

해당 알고리즘이 얼마나 빠르고, 느린지를 비교하기 위해 구하는 것입니다.

 

다시 말해, 데이터의 크기 n이 커질 때,

수행 시간의 증가하는 정도를 훨씬 중요하게 생각한다는 것 입니다.

 

그래서 우리는 입력 값의 크기에 따른 함수의 증가량,

즉 성장률 (rate of growth)만을 집중해서 보기 위해, 중요하지 않은 부분을 식에서 제거하여 보기로 했습니다.

 

이것을 바로 점근적 표기법(asymptotic notation)이라고 하고,

점근적 표기법에는 다음 3가지 형태가 있습니다.

 

바로 Big-Θ표기법, Big-O 표기법, 그리고 Big-Ω표기법입니다.

하나씩 차례대로 보겠습니다.

---

 

빅오 표기법 (Big O)

 

빅오 표기법은 주로 점근적 상한만을 고려하여 실행 시간을 표기하는 방법입니다. 

 

간단히 말하면, 

이 기준은 최악의 경우에도 특정 함수를 넘지 않는다는 것을 의미합니다. 

 

위의 그래프를 살펴보면 n이 충분히 큰 값일 때,

running time이 k·f(n)의 그래프를 넘지 않는 것을 확인할 수 있습니다. 

 

이 때, 우리는 실행 시간을 f(n)의 빅오(O)로 나타낸다고 말합니다. 

여기서 우리는 k와 같은 상수를 제외하고 함수 f(n)에 집중합니다. 

---

좀 더 쉽게 설명하면...! 

 

친구가 은행 이자율에 대해 물어봤을 때, 현재 정확한 이자율은 모르지만 

법정 최고 이자율은 알고 있다고 가정해 봅시다. 

 

현재 법정 최고 이자율이 연 20%이라면, 

이자율이 20%는 넘지 않을 것이라고 대답할 수 있을 것입니다.😅

 

 

---

 

빅 오메가 표기법 (Big-Ω)

 

빅 오메가 표기법은 주로 점근적 하한만을 고려하여 실행 시간을 표기하는 방법입니다. 

 

간단히 말하면, 

이는 최소한의 실행 시간을 표현하는 것으로, 최소 어느 정도 걸리는지를 나타냅니다. 

 

위의 그래프를 살펴보면 

n이 충분히 큰 값일 때, running time이 k·f(n)의 그래프를 항상 넘는 것을 확인할 수 있습니다. 

 

이 때, 우리는 실행 시간을 f(n)의 빅오메가(Ω)로 나타낸다고 합니다. 

빅오와 마찬가지로 상수 k는 제외하고 봅니다. 

---

이것도 쉽게 설명해보면...! 

 

이번에는 버스비를 생각해봅시다! 

어떤 사람이 요즘 버스비가 얼마인지 물어보았다고 가정해 봅시다. 

 

현재 정확한 버스비는 모르지만 어릴 때 냈던 1000원보다는 비쌀 것이라고 생각하여 

최소한 1000원보다는 더 비쌀 것이라고 대답할 수 있을 것입니다. 🤓

---

빅 세타 표기법 (Big-Θ)

 

빅 세타 표기법은 점근적 상한과 하한을 모두 고려하여 실행 시간을 표기하는 방법입니다. 

 

간단히 말하면, 

최소 및 최대 실행 시간을 동시에 고려하여 특정 함수의 범위를 표현합니다. 

 

위의 그래프를 살펴보면 n이 충분히 큰 값일 때, 

running time이 k₁·f(n)과 k₂·f(n)의 그래프를 넘지 않는 것을 확인할 수 있습니다. 

 

이 때, 우리는 실행 시간을 f(n)의 빅 세타(Θ)로 나타낸다고 합니다. 

여기서도 빅오와 빅오메가와 같이 상수 k는 제외하고 함수 f(n)에 집중합니다. 

---

좀 더 쉽게 설명하자면...!  (마지막~)

 

이번에는 친구가 학교까지 가는 데 걸리는 시간에 대해 물어봤다고 상상해 봅시다! 

 

학교까지 가는 방법에 따라 걸리는 시간이 다르기 때문에 

가장 오래 걸리는 경우와 가장 짧게 걸리는 경우의 중간값을 고려하기로 했습니다. 

 

가장 오래 걸리는 경우는 학교까지 걸어가는 시간이고

(이것을 빅오로 표현할 수도 있겠죠!)

 

가장 빨리 갈 수 있는 방법은 부모님이 차로 데려다주는 것입니다. 

(이건 빅 오메가!)

 

따라서 두 시간의 중간값을 친구에게 대답하는 것입니다.

(이건 빅 세타!)

---

마무리

 

우리는 계산이 까다로운 평균 대신에, 

최악의 상황을 나타내는 빅오 표기법을 가장 많이 사용하는 것입니다. 

 

전체적인 시간 복잡도의 표기법들에 대해서 자세히 알아봤으니, 

다음 번에는 빅오 표기법의 특징과 종류에 대해서 알아보겠습니다. 🤓

(생각보다 작성하는 시간이 꽤 걸려서.. 공부 시간이 부족하면 조금 나중에 쓸게요..!)

---

📝 참고 자료

한국외대 신찬수 교수님의 Data Structures with Python 강의

https://www.tutorialspoint.com/data_structures_algorithms/asymptotic_analysis.htm

https://chayan-memorias.tistory.com/100

https://noahlogs.tistory.com/27

https://ko.khanacademy.org/computing/computer-science/algorithms/asymptotic-notation/a/big-big-theta-notation