[알고리즘] 알고리즘을 평가하는 시간 복잡도와 빅오 표기법(Big-O)

 

 

 

 

알고리즘 평가 요소

 

1. 시간 복잡도 (Time Complexity)

코드의 실행 시간이 얼마나 빠른가? 알고리즘의 수행 시간을 나타낸다.
실행 시간이 빠를수록 주어진 시간 내에 더 많은 일을 할 수 있어 효율적이다.

 

2. 공간 복잡도 (Space Complexity)

얼마나 메모리를 적게 쓰는가? 알고리즘 수행에 필요한 메모리 공간을 의미한다.
실행하는 코드가 요구하는 메모리 공간이 적을수록 한번에 사용할 수 있는 여분의 공간이 더 많이 생긴다.
더 적은 용량을 사용할수록 더 많은 공간을 사용할 수 있어 효율적이다.

 

시간복잡도와 공간복잡도는 알고리즘을 평가하는 요소로 중요하게 여기고, 그 중 시간복잡도를 더 고려한다.
시간복잡도와 공간복잡도 계산을 할 땐 점근적 표기법을 이용하여 나타낸다.

 

 

---

 

 

점근적 표기법 (Asymptotic Notation)

알고리즘의 실행시간은 환경에 따라 다르게 측정된다. 실행환경으로 알고리즘 구분하면 사용자에 따라 다르게 나타날 수 있다. 모두에게 주어진 정보를 가지고 어떤 알고리즘이 더 빠를지 계산하는 방법은 코드를 통해 알 수 있다. 중심이 되는 연산의 실행 횟수로 성능을 분석하는 것이다.

연산 횟수는 입력 크기 n에 대한 함수로 표기하는데, 함수가 길고 복잡할수록 비교하기 어려워져 단순화된 식을 요구한다. 그렇게 단순화하여 사용하는 식이 점근적 표기법이다.

 

 

1. 최상의 경우 '오메가 표기법 (Big - Ω Notation)

말 그대로 최선의 시나리오로 최소 이정도의 시간이 걸린다는 것을 계산한다.

 

코드 실행 시에 주어진 조건이 최상의 모습이며, 결과를 구하기 다른 연산이 필요하지 않은 경우이다.
정렬을 예로 들면 [ 1, 2, 3,4 ,5 ]의 리스트를 오름차순으로 정렬하는 것과 [ 5, 4, 3, 2, 1 ]을 오름차순 정렬할 때 차이가 난다. 이미 오름차순 정렬이 되어있는 첫번째 리스트의 경우 그냥 비교연산하며 정렬을 확인할 수 있지만, 내림차순 정렬이 되어 있는 두번째 리스트의 경우에는 모든 요소가 제자리를 찾기 위해 이동해야 한다.

이처럼 주어진 조건이 최상이라고 가정하여 문제를 풀 때 오메가 표기법을 사용한다.

 

$$f(n) = Ω(g(n)$$

 

 

2. 평균 '세타 표기법 (Big - θ Notation)

평균적인 경우를 계산하는 빅 세타 표기법. 오히려 제일 사용하지 않는다.

알고리즘이 복잡해질수록 평균적인 경우를 구하기 어려워지고, '평균'이라는 것을 증명하기 어렵다. 상황에 따라서 알고리즘 성능이 달라질 수 있는데 그 '평균'을 하나로 정의할 수도 없다.

 

$$f(n) = θ(g(n)$$

 

 

3. 최악의 경우 '빅오 표기법 (Big - O Notation)

시간복잡도를 표기할 때 가장 많이 사용하는 것이 최악의 경우를 나타내는 빅오 표기법이다. 
주어진 조건이 최악인 경우 알고리즘 성능을 계산한다.

평균의 경우를 구할 때는 상황에 따라 평균이 달라질 수 있지만, 최악의 경우는 항상 같은 결과를 보여준다. 언제나 최상의 조건이 주어질 수 없고, 최악의 상황에도 좋은 성능을 보인다면 좋은 알고리즘이라고 할 수 있다.

그래서 우리는 시간복잡도를 계산할 때 이 빅오 표기법을 사용하며, 점근적으로 나타낸다.

 

$$f(n) = O(g(n))$$

 

 

---

 

 

빅-오 표기법 (Big - O Notation)

 

최고차항만 표기

빅오 표기법을 나타낼 때 단순화된 점근적 표기를 이요한다. 연산에 영향을 주는 것을 제외하고 모두 제외시키는 것이다.
연산에 영향을 주는 걸 어떻게 판단할까? 식을 보면서 설명할 수 있다.

 

 

$T(n) = n^2 + 2n + 1$ 이 식에서 최고차항은 $n^2$이고, 빅오로 표기하면 $O(n^2)$로 볼 수 있다.

 

상수?

먼저 제일 뒤에 상수 1은 아무런 영향도 주지 않는다. $2n$에서 주어진 $n$에 따라 값이 결정된다.

만약 $n$이 2가 주어지면 $2*2+1$로 $5$를 구할 수 있고, 만약 $n$이 50이면, $2*50+1$로 101이 된다. 결국 값의 크기는 상수보다 곱하기로 이루어진 항이 더 큰 영향을 준다.

 

 

계수 제거

위 비교에서 또 하나를 알 수 있다. $2n$에서 앞에 있는 계수랑 뒤에 있는 $n$ 중 어떤 것이 더 큰 영향을 줄까?

$n=2$인 경우와 $n=50$인 경우를 계산해보았다. 결국 계수는 $n$을 따라가는 역할만 한다. $n$의 값이 작을수록 작은 결과가 나오고, 클수록 큰 결과가 나온다. 계수가 2가 아니라 1394여도 마찬가지로 $n$에 따라서 결과가 결정된다. 따라서 항에서 중요한 것은 앞에 붙은 숫자인 계수가 아닌 $n$을 중심으로 봐야한다.

 

 

차수 우선

$T(n) = n^2 + 2n + 1$ 에서 마지막까지 살아남은 건 $n^2$ 하나였다. 위 비교를 보면 $2n$도 결과에 영향을 주는데 왜 사라졌을까? $n$과 $n^2$ 중 결과에 더 큰 영향을 주는 건 $n^2$였기 때문이다.

 

$1$과 $2n$을 비교할 때, 더 큰 영향을 주는 $2n$을 살렸고, $2*n$에서 더 큰 영향을 주는 $n$을 살렸다. 같은 원리로 $n^2 + 2n$에서 더 큰 영향을 주는 건 $n^2$이다. $n$에 따라서 그 결과가 달라질텐데, 그냥 단순히 곱을 해주는 것과 제곱으로 올라가는 건 큰 차이가 있다. 숫자가 작으면 차이가 얼마 안 나겠지만 우리는 최악의 경우를 생각해야 한다. 아주 큰 숫자가 주어질 경우, 즉 아주 많은 연산이 들어간다면 제곱을 하는 것이 더 큰 영향을 준다.

 

 

최고 차항

만약 연산 횟수가 $T(n) = n^2 + 2n + 1$가 아닌 $T(n) = 2n^4 + n^2 + 5n$이 나온다면 빅오로 표기했을 때 $O(n^4)$로 표기할 수 있다. 수학을 풀 듯 자세하게 계산할 필요 없이 그저 더 나은 성능을 구하는 것임으로 불필요한 것은 제거하여 더 큰 영향을 주는 것만 남긴다. 이것이 점근적 표기 방식이다.

 

 

 

시간복잡도 그래프

https://www.bigocheatsheet.com/

 

빅오 표기법으로 나타낸 성능을 그래프로 그리면 이와 같다.

시간이 지날수록 수행되는 연산을 보여준다. 아무리 시간이 지나도 동일한 상수값을 유지하는 $O(1)$과 $n$의 계승을 나타내는 $O(n!)$을 보면 그 차이를 한 눈에 볼 수 있다.

작은 알고리즘에서는 그 티가 나지 않겠지만, 큰 프로젝트에서 많은 연산과 데이터를 사용하는 알고리즘을 실행시킬 경우 그 차이는 매우 커진다. 이를 위해 우리는 더 효율적인 알고리즘을 사용하기 위해 노력해야 한다.

 

 

복잡도 단계

$$O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(2^n) < O(!)$$

 

위 그래프를 통해서도 알 수 있듯이 복잡도가 점점 커지는 순서로 나열해보았다. 
더 적은 시간복잡도를 만드는 알고리즘을 고려해야 한다.

 

 

 

---

 

 

 

reference

"점근 표기법 (asymptotic notation) 알아보기", yoongrammer, https://yoongrammer.tistory.com/78
"[algorithm] 시간복잡도란? 시간복잡도 계산하는 법 ( O(1), O(n), O(logn))",
삽질 기록 차곡차곡, 삽질 금지구역,  https://joyhong-91.tistory.com/12
"시간 복잡도(Time Complexity) 및 공간 복잡도(Space Complexity)", yoongrammer, https://yoongrammer.tistory.com/79
"빅-오 표기법 (Big-Oh Notation)", Crocus, https://www.crocus.co.kr/231