Asymptotic Analysis 점근적 분석
우리는 코드를 짤 때, 성능을 아예 배제하고 짤 수 없다. 어떤 프로그램을 구매할 때, 정작 우리도 속도가 더 빠르고, 정확도가 높은 것을 사용하고 싶지 않은가? 마찬가지다.
점근적 분석은 시간복잡도를 분석하는 방법으로, 충분히 큰 input(입력값)에 따른 작업량의 횟수로 분석하는 방법이다. 물론 네트워크 속도나 컴퓨터의 처리 속도 등 시간복잡도에 영향을 줄 수 있는 요소들을 아예 염두에 두지 않은 방법이기 때문에, 아주 정확한 시간을 얻어 분석하는 방법은 아니지만, 우리가 짠 알고리즘의 시간적 성능을 좀 더 간편하게 파악하기에는 더할 나위없이 좋다. 그런데 왜 "점근"적 분석일까? 그리고 또 한가지 input이 충분히 커야한다고 앞서 언급했는데, 이유가 뭘까?
점근적 분석 시 Input은 충분히 커야한다
지금부터 파란색으로 이차함수 그래프, 빨간색으로 일차함수 그래프를 나타낸 3개의 좌표평면을 보여줄 것이다. 다음을 유의하면서 그래프를 대소비교해보자.
x값이 증가함에 따라 결국 어떤 함수의 함숫값이 더 큰가?
그리고 그 함수는 몇 차식인가?
참고로 x는 입력값, y는 작업량의 횟수를 나타낸다. (즉, 값이 작아야 좋은 것) 또, 우리가 과자를 0개 먹을 수는 있어도(먹지 않음), -1개를 먹을 수 없다는 점에 착안해서 입력값에 0을 넣을 수는 있어도 음수는 넣을 수 없다는 점을 잊지 말고 1사분면만 보도록 하자. (편의상 함수, 함숫값이라는 말을 빼고 색깔로만 말하겠다.)
파란색 : y = x2 - 5
- 빨간색: y = x
파란색: y = x2 + 1
- 빨간색: y = x
파란색: y = x2
- 빨간색: y = 100x
마지막 케이스는 다소 극단적이었지만, 결국 이차식의 함숫값이 일차식보다 커진다는 것을 보여주고 싶었다. 여기서 왜 Input의 값이 충분히 커야하는지가 알 수 있다. x는 input이라고 했는데, x가 충분히 크지 않을 때는 일차식이 더 클 수도 있으니, 분석 결과를 신뢰할 수 없게 된다.
어떤 프로그램의 로직을 식으로 나타내기만 하면, 결국에 어떤 로직이 더 성능이 좋은지는 다른 항, 상수, 계수들을 무시하고 최고차항만으로 성능을 알 수 있기 때문이다. 그런데 다만 항상 파란색이 큰 것은 아니었다. x값이 작을 때는 빨간색이 크기도 했었다. 즉, 교점이 있는 경우라면, 입력값이 충분히 클 때만 유의미하다는 것이다.
정리
점근적 분석을 사용하는 이유는 결국 성능을 식으로 나타냈을 때 최고차항만 보면 성능을 파악할 수 있기 때문이다. 편리하지 않은가? (사실 편리하기 위해 최고차항만 보는 것이다. 닭 => 알, 알 => 닭)
입력값이 충분히 커야하는 이유는 적어도 교점 이상의 input이 들어왔을 때, 분석법이 유의미하기 때문이다.
점근 표기법
앞서 최고차항으로만 따진다고 했는데, 뒤에 언급할 기준이 되는 함수들의 집합이라고 생각하면 된다.(e.g. 2x, 2x + 1 등은 그냥 x로 취급하고, 2x2, 100x2 - 10x + 1 등은 x2로 취급하고)
속도 비교
바로 아래에 있는 좌표평면 말고 그 다음에 나오는 좌표평면을 보면 알겠지만 초록색보다 보라색이 더 성능이 떨어진다. 다시 말하지만 다시 한번 입력값이 충분히 크지 않다면 점근적 분석이 크게 의미가 있지 않다. 예를 들어, 내가 생각한 알고리즘이 초록색, 보라색 두가지가 있는데 입력값이 기껏해야 5라면, 원래 우리는 보라색의 성능이 더 나쁘다고 알고 있었는데, 초록색이 더 나쁘지 않은가? 게다가 5정도 되는 입력값이면 성능상 그렇게 큰 차이도 없어서 굳이 분석하고 있을 필요는 없을 것 같다.(항상은 아니다!)
이게 진짜다
성능 좋은 순으로(x축과 가까운 순으로). 좌표평면에는 상수 그래프는 없다. 간략하게 말하자면 우리가 어떤 입력값을 넣어도 고정된 시간이 걸린다면? 천만, 천조 등 무엇을 넣어도 상수시간이 걸린다면? 그럼 그건 제일 효율이 좋을 수 밖에 없다.
상수상수;<;log;x;<;x;<;x,log;x<;x2;<;2x 상수는 빼고, 아래 그래프 색깔로 맞추자면 상수없음파란색초록색보라색검정색빨간색상수없음<파란색<초록색<보라색<검정색<빨간색
3가지 대표적인 점근 표기법
지금부터 점근 분석법에 대해 조금 더 자세하게 들여다볼 예정이다. 앞서 말한 점근적 분석을 표기하는 방법에는 대표적으로 3가지가 있다. 더 나아가면 스몰o 등도 있지만 여기서는 다루지 않는다. O;,;Θ;,;Ω **Big-O빅오 / Theta세타 / Omega오메가**이다. 각 문자 뒤에 있는 괄호에 식을 넣는데 그 식에 대한 집합을 나타낸다. 위의 표기법들은 각 집합의 조건에서 딱 한가지만 다르고 전부 동일하다. 먼저 공통된 부분을 먼저 살펴보자. f(n)=5n2+10n+1 위와 같이 함수식이 있다고 생각해보자. 우선 우리는 점근적 분석을 할 때, 편의상 최고차항만 보기로 했다. 그럼, 다음과 같아질 것이다. 5n2 또, 우리는 계수를 무시하기로 했으니 다음과 같아질 것이다. 왜 이렇게 하는지는 앞서 설명했는데, 다시 한번 언급하자면, 결국 충분히 큰 입력값만 들어온다면 다른 유형의 최고차항과 비교했을 때의 결과가 유사해지기 때문이다. n2 그래서 위 함수 f(n)에 대하여 다음이 성립한다. f(n)∈O(n2);f(n)∈Θ(n2);f(n)∈Ω(n2)
보통은 다음과 같이 등호로 표기하는데 같은 뜻이다. f(n)=O(n2) ;f(n)=Θ(n2) ;f(n)=Ω(n2)
그럼 차이점은 뭘까? 각각 다음과 같은 말을 추가해주면 된다. Big-O빅오는 기껏해야(at most), Omega오메가s는 적어도(at least), Theta세타는 별다른 말을 넣어줄 필요는 없고 빅오와 오메가의 교집합이라고 이해하면 좋을 것 같다. 그럼 각각을 이해를 돕기 위해 y와 x2 를 이용한 그래프들을 보도록 하자.
- Big-O빅오 : 기껏해야(at most) O(n2) ;;y≤x2
색칠된 영역을 보면 알 수 있듯이, 5x + 1, 2logx + 10 등도 전부 O(x2) 포함된다. 하지만 이렇게 널럴하게 잡아버리면 그만큼 정보의 손실이 있기 때문에 가능하면 폭 좁게 잡아야 한다. 방금 얘기한 식들의 경우 각각을 O(x), O(log x)로 잡는 것이다.
- Omega오메가: 적어도(at least) Ω(n2) ;;y≥x2
- Theta세타: (빅오와 오메가의 교집합!) Θ(n2)
정리
우선 점근적 분석법에서는 최고차항 외의 다른 항들은 계산할 때 제외시키고, 최고차항의 계수 역시 취급하지 않는다. 그렇게 해서 함수식들은 최고차항의 차수에 따라 집합을 구성하게 되는데, O(f(N))를 예로 말하자면, 빅오 f(N)는 기껏해야 f(N)의 상수비율로 증가하는 함수들의 집합인 것이다. 보기 쉽게 말로 풀어서 조건제시법으로 나타내자면, 보다큰상수가있고보다작지않은입력값그리고보다큰모든들에대해O(f(N))={g(N);|0보다;큰;상수;c가;있고,;0보다;작지;않은;입력값;N0,;그리고;N0보다;큰;모든;N들에;대해,;cf(N);≥;g(N);} 한번 세타와 오메가인 경우 위에서 어디를 고쳐야할지 생각해보자.
Running Time 분석시 3가지 유형의 케이스들
수행시간을 분석할 때 중요한 3가지 케이스들이 있다. 구체적인 예시들은 다음 글의 주제인 Sorting에서 좀 더 이해하기 좋을 것 같아서 개념만 짚고 넘어가도록 하자. 우리가 알고리즘을 적용할 때, 정말 다양한 상태의 input을 만나게 된다. 우리가 정렬해야하는 배열이 있다고 가정해보자. 이 때 이 배열은 보통 흔하게 무작위로 나열된 상태 뿐 아니라, 정렬된 상태일 수도 있고, 역정렬된 상태일 수도 있다. 어떤 상태의 배열인지에 따라 성능이 좋은 알고리즘도 달라진다. 즉, 같은 배열을 갖고 다양한 정렬 알고리즘을 돌렸을 때 작업량의 차이가 있을 것이라는 것이다. 그럼 우리가 알고리즘의 성능을 파악할 때 어떻게 해야할까? 대표적으로 Best Case, Average Case, Worst Case 각각 3가지의 경우에서의 성능을 분석하는 방법들이 있다. Best Case는 어떤 알고리즘에서 가장 짧은 시간이 걸리는, 즉, 성능이 가장 좋은 케이스를 말한다. 하지만 우리는 이미 삶은 통해 알고 있겠지만, 최악을 생각해야 위험에 대비할 수 있다. 이와 마찬가지로 좋은 케이스보다는 Worst Case에 좀 더 중점을 둬야 한다. 이것은 가장 시간이 오래 걸리는 경우를 말하는 것인데, 어떤 경우에 우리가 작성한 알고리즘이 성능이 낮다면 이에 대한 대책을 세울 수 있을 것이다. 그리고 또 하나 중요한 것은 모든 경우의 성능의 평균값인 Average Case이다. 항상 나쁜 것이 들어오는 경우만 생각한다면, 즉, 최악의 케이스만 고려해서 로직을 작성하게 되면 오히려 실제와 거리가 멀어져 성능 향상에 저해될 수 있다. 처음에 얘기했지만 그 때, 그 때 다를 수 있다는 것을 잊지 말자.