#7 [C 자료구조] 알고리즘 시간 복잡도 실전편

앞서 배운 알고리즘 복잡도 중 시간 복잡도가 성능 분석을 위해 쓰인다고 언급했다.

따라서 우리는 시간 복잡도를 실전에 어떻게 쓰이는지 알아볼 필요가 있다.

알고리즘은 최선의 경우와 최악의 경우, 평균의 경우로 나눠서 분석해볼 수 있다.

자 실전 예시를 보자!!!

인생은 실전이야

예를 들어,

운 좋게 환승시간 딱딱 맞춰서 강의하러 학교에 간 경우 36분

집을 나와서 운나쁘게 열차를 놓쳐 4분을 기다리게 된 경우 40분

놀랍지 않게 우리의 알고리즘은 대부분 최악의 경우를 가정해서 나타낸다.

이 것이 바로 최악 경우 분석 (Worst Case Analysis)이다.

 

각각의 특징을 비교해보면

최악 경우 분석	성능 보장	마! 내가 적어도 이 정도는 한다!
평균 경우 분석	입력의 확률 분포 가정	마! 이건 내 보통 실력이다!
최선 경우 분석	최적 알고리즘 (최대치)	마! 내가 원래 이 까지 할 수 있다!

이렇게 된다.

 

 

---

 

복잡도의 점근적 표기(Asymptotic Notation)

복잡도는 보통 입력 크기에 대한 함수로 표기한다.

for문 while문 등 복잡하게 입력이 다변화하면

f(n) = 5n² - 35n + 124

와 같이 다항식으로 표기할 수 있게 된다.

그러나 시간 복잡도 함수에서는 가장 차수가 큰 n항만을 표기, 계수 또한 생략하여 표기한다.

n이 무한대로 증가한다고 가정하기 때문이다!!

따라서 f(n) = 5n² - 35n + 124의 복잡도는 n² 라고 볼 수 있다.

 

복잡도가 점근적으로 상한 하는지, 하한 하는 여부에 따라 복잡도를 표현하는 방식이 존재한다.

O(Big-Oh): 점근적 상한

Ω(Big-Omega): 점근적 하한

Θ(Theta): O와 Ω가 같을 경우

수식의 의미를 다음과 같이 알고 다음 챕터로 넘어가자!

 

1) O(Big-Oh) 점근적 상한

 

복잡도의 점근적 상한을 나타낸다! 최악 경우 분석에 해당한다고 보면 될 것이다.

위의 f(n) 예시의 5n² - 35n + 124의 O 표기는 f(n) = O(n²)이다.

이는 다시 f(n) ≤ c * g(n) 으로 나타낼 수 있는데 'n의 값이 일정 수준이 넘어가면 그 어떤 값을 대입하여도 c * g(n) 보다 결괏값이 작거나 같다.(c=상수)'라는 뜻이다. 즉 f(n)의 상한 이라는 뜻이다.

 

다시 말해, f(n) ≤ c * g(n)의 값을 우리가 직접 구해야 한다! 원래 있는 것이 아니다.

만약 만족하는 c와 g함수(보통 최고 차수)가 있다면 우리는 O(n²)가 실재한다는 것을 입증할 수 있는 것이다.

식을 풀어보면

f(n) ≤ c * g(n)
5n² - 35n + 124 ≤ c * n²

대략 c = 4, n > 3 이면 답을 만족한다. 즉 답이 있으므로 참!  f(n) = O(n²)

그리고 f(n)은 절대 4n² 보다 절대 클 수 없다.

위 표에서 n0은 균형 분기점이라고 보면 된다.

최고 차수에 따라 식이 달라져도 점근적 상한은 O(g(n))을 유지한다.

다음의 예시를 보면 더 쉽게 이해가 가능할 것이다.

 

2) Ω(Big-Omega) 점근적 하한

복잡도의 점근적 하한이다. 최선 경우 분석이라 보면 된다.

위의 f(n) 예시의 5n² - 35n + 124의 Ω표기는 f(n) = Ω(n²)이다.

즉 복잡도가 이 것보다 작을 수는 없다! 이 말이다. 이 또한 O와 마찬가지로 계수 없는 최고 차 항만을 쓴다. 최고 차 항의 낮은 단계를 써도 무방하다(f(n) = Ω(n)).

또한 c * g(n) ≤ f(n) 이렇게 반대로 나타낸다.

또 차수가 증가하더라도 Ω(g(n))이 점근적 하한이 된다.

이 또한 예시를 보자면,

이와 같다. 반드시 최고 차 항을 따라가는 것은 아니다. 그보다 더 작은(로그 까지도) 항또한 오메가 안에 들어갈 수 있다.

 

3) Θ(Theta) O와 Ω가 같을 경우

f(n) = 5n² - 35n + 124 식의 경우

f(n) = O(n²) =Ω(n²) 가 된다.

따라서 우리는 이를 f(n) = Θ(n²)라고 표기한다.

 

수식으로 표기하면

c1 * g(n) ≤ f(n) ≤ c2 * g(n)

을 만족하는 것이다.

 

Θ를 만족하지 못하는 식은

f(n) = 6*2ⁿ + n²

-> f(n) = O(2ⁿ) =/ Ω(n²)

이런 게 있으시겠다!!

 

---

 

 

알고리즘 복잡도 실제 사례

마지막으로 어떤 알고리즘들이 위와 같은 값을 나타낼지 생각해보자!

먼저 각각의 시간은 다음과 같은 명칭과 예시를 가지고 있다.

 

O(1) 상수 시간 - 리스트에서 사람 1명을 찾는 시간

O(logn) 로그 시간 - 반씩 줄여가면서 검색하는 데 걸리는 시간 (이진 탐색), 피보나치 최적 탐색

O(n) 선형 시간 - 한 명이 모든 사람과 악수하는 데 걸리는 시간

O(nlogn)로그 선형 시간 - 가장 큰 수를 제 위치에 배치하는데 걸리는 시간

O(n²) 제곱 시간 - 모든 사람이 다른 모든 사람과 악수하는 데 걸리는 시간

O(n³) 세제곱 시간 - 3차원 그래프

O(2ⁿ) 지수 시간

O(n!) 계승

크기 순서대로 정렬한 것이다. 계승 시간이 가장 긴 알고리즘 복잡도를 가지고 있다는 것을 알 수 있다.

입력 크기가 작으면 수행 시간은 비슷하지만 무한대로 갈수록 기하급수적으로 증가한다!

반대로 알고리즘을 잘 짜면 시간을 기하급수적으로 줄일 수 있다는 말이 된다.

 

잘 키운 알고리즘 열 슈퍼컴 필요 없다!

라는 마인드로 흙수저는 알고리즘을 잘 짜야합니다.