Complexity

알고리즘의 효율을 측정할 때 우리는 복잡도(Complexity)라는 용어를 사용한다.

 

복잡도는 두 가지로 분류가 가능한데, 공간 복잡도(Space Complexity), 시간 복잡도(Time Complexity)이다.

 

1. 공간 복잡도는 문제의 크기에 따라 알고리즘 수행에 필요한 메모리의 공간이 얼마나 필요한가를 의미한다.
2. 시간 복잡도는 문제의 크기에 따라 알고리즘 수행에 시간이 얼마나 걸리는가를 의미한다.

 

분석의 종류에는 여러가지가 있다. 입력 값들에 따라서 알고리즘의 수행 속도가 달라질 수 있다.

예시로 수행 시간을 측정했는데 입력이 아주 운이 좋게 아무런 작업도 하지 않고 수행을 끝낼 수 있게 되는 최선의 경우(Best Case) vs 입력이 아주 나쁘게 들어와 한 번의 작업도 건너뛰지 말아야하는 최악의 경우(Worst Case) vs 입력이 무작위로 들어와 평균적으로 수행을 마치는 평균의 경우(Avarage Case) 등이 있을 수 있다

최악의 경우 : f(n) = n²+2n+100
최선의 경우 : f(n) = 2nlogn
평균의 경우 : f(n) = 2nlogn+100

Big-O 표기법은 함수에 대해 상한을 찾게 해준다. 예시로, 수식들을 그래프로 그릴 때 n²의 상승폭이 밑의 log n의 상승폭보다 크니 다른 항들은 다 떼고 보고 그래프를 그린다는 것이다. 또한 일반적으로 f(n) = O(g(n))으로 표현된다. n의 값이 클 때(0 이상 일 때) f(n)의 상한이 g(n)의 상수배라는 말이다. 즉, 위에 함수로 예를 들면 f(n) = n²+2n+100이 주어진 알고리즘의 수행 시간이라면 g(n) = n²이라는 것이며, f(n)이 g(n)보다 크니 g(n)의 상수배가 f(n)의 상한이라는 것이다.

 

Big-O 표기법의 정의
O(g(n)) = {f(n): n ≥ n(0)인 경우인 모든 n에 대해 0 ≤ f(n) ≤ cg(n)을 만족하는 양의 상수 c와 n(0)이 존재한다.}
n이 작을 때에는 생략한다. 즉, n이 작을 경우의 상승폭은 중요치 않다라는 얘기다.

즉, Big-O Notation에 의하면 상술한 O(n²)가 O(n³), O(n⁴)도 된다는 것이다.

 

Omega 표기법은 함수의 하한을 찾게 해준다. 이 것은 n의 값이 클 때에 f(n)의 하한이 g(n)의 상수배라는 것이다. 예시로, 위에 작성한 함수를 이용해보자면 f(n) = n²+2n+100일 때에 Ω(n²)라는 것이다.

 

Omega 표기법의 정의
O(g(n)) = {f(n): n ≥ n(0)인 경우인 모든 n에 대해 0 ≤ cg(n) ≤ f(n)을 만족하는 양의 상수 c와 n(0)이 존재한다.} 예를 들어, f(n) = 1/2*n²인 경우에 이 함수의 하한은 n², n, logn.. 그 외 등등이 있을거다.

또한 Big-O 표기법은 연산 수에 큰 영향을 주지 않는 가지들을 모두 쳐내고 표기한다. 상수를 나타내는 1은 10억이 되어도 1이고 한 번만 실행되어도 1이다. n또한 2n도 n이고 100n도 n으로 나타내듯 시각화할 수 있다.

 

Tight 표기법은 알고리즘의 평균 수행 시간은 항상 하한과 상한 사이에 존재한다. 만약 상한(O)과 하한(Ω)이 같다면 세타(θ) 표기법 또한 같은 증가율을 같는다.

예를 들어 f(n) = 10n²+n의 상한은 O(n²)이 되고, 하한도 Ω(n²)가 된다.
이 경우 최선의 경우와 최악의 경우의 증가율이 같다.
결과적으로 Tight-Bound의 경우 또한 같아진다.

 

Tight 표기법의 정의
O(g(n)) = {f(n): n ≥ n(0)인 경우인 모든 n에 대해 0 ≤ c₁g(n) ≤ f(n) ≤ c₂g(n)을 만족하는 양의 상수 c₁과 c₂와 n(0)이 존재한다.}

이해가 되지 않는 사람들을 위해 덧붙이자면,
g(n)이 n일 경우 c의 하한은 만족할지라도 상수배로 증가하는 n에 c를 아무리 곱한다한들
제곱수만큼 증가하는 n²보다 항상 클 수가 없다는 것이다.
n²의 경우에서도 n의 상한은 만족할지라도 하한은 만족하지 못할 것이다.

하지만 현재 컴퓨터를 공부하는 90% 이상의 사람들은 세타의 의미로 Big-O 표기법을 사용하고 있으며 세타 표기법을 사용하는 사람들은 드물다.