2. Asymptotic Analysis

Photo by Stephen Dawson on Unsplash

2. Asymptotic Analysis

점근적 분석

db's photo
db
·Jun 30, 2022·

6 min read

Table of contents

Asymptotic Analysis 점근적 분석

우리는 코드를 짤 때, 성능을 아예 배제하고 짤 수 없다. 어떤 프로그램을 구매할 때, 정작 우리도 속도가 더 빠르고, 정확도가 높은 것을 사용하고 싶지 않은가? 마찬가지다.

점근적 분석은 시간복잡도를 분석하는 방법으로, 충분히 큰 input(입력값)에 따른 작업량의 횟수로 분석하는 방법이다. 물론 네트워크 속도나 컴퓨터의 처리 속도 등 시간복잡도에 영향을 줄 수 있는 요소들을 아예 염두에 두지 않은 방법이기 때문에, 아주 정확한 시간을 얻어 분석하는 방법은 아니지만, 우리가 짠 알고리즘의 시간적 성능을 좀 더 간편하게 파악하기에는 더할 나위없이 좋다. 그런데 왜 "점근"적 분석일까? 그리고 또 한가지 input이 충분히 커야한다고 앞서 언급했는데, 이유가 뭘까?

왜 "점근"적 분석이고, 왜 input은 "충분히 커"야할까?

지금부터 파란색으로 이차함수 그래프, 빨간색으로 일차함수 그래프를 나타낸 3개의 좌표평면을 보여줄 것이다. 다음을 유의하면서 그래프를 대소비교해보자.

  1. x값이 증가함에 따라 결국 어떤 함수의 함숫값이 더 큰가?
  2. 그리고 그 함수는 몇 차식인가?

    참고로 x는 입력값, y는 작업량의 횟수를 나타낸다. (즉, 값이 작아야 좋은 것) 또, 우리가 과자를 0개 먹을 수는 있어도(먹지 않음), -1개를 먹을 수 없다는 점에 착안해서 입력값에 0을 넣을 수는 있어도 음수는 넣을 수 없다는 점을 잊지 말고 1사분면만 보도록 하자. (편의상 함수, 함숫값이라는 말을 빼고 색깔로만 말하겠다.)

  • 첫번째
    • 파란색 : y = x2 - 5
    • 빨간색: y = x
  • 두번째
    • 파란색: y = x2 + 2
    • 빨간색: y = 4x + 5
  • 세번째
    • 파란색: y = 1/200x2 - x
    • 빨간색: y = x
  • 네번째
    • 파란색: y = x2 + 1
    • 빨간색: y = x
  • 다섯번째
    • 파란색: y = x2
    • 빨간색: y = 100x

마지막 비교는 다소 극단적이었는데, 이렇게 해도 결국 처음에 빨간색이 클 수도 있지만, 교점의 x 이후에는 파란색 즉, 이차함수가 크다. 어떤 계수나 어떤 항을 넣어도 결국에는 이차함수가 크다. 이게 바로 우리가 점근적 분석을 사용하는 이유다.

어떤 프로그램의 로직을 식으로 나타내기만 하면, 결국에 어떤 로직이 더 성능이 좋은지는 다른 항, 상수, 계수들을 무시하고 최고차항만으로 성능을 알 수 있기 때문이다. 그런데 다만 항상 파란색이 큰 것은 아니었다. x값이 작을 때는 빨간색이 크기도 했었다. 즉, 교점이 있는 경우라면, 입력값이 충분히 클 때만 유의미하다는 것이다.

정리

점근적 분석을 사용하는 이유는 결국 성능을 식으로 나타냈을 때 최고차항만 보면 성능을 파악할 수 있기 때문이다. 편리하지 않은가? (사실 편리하기 위해 최고차항만 보는 것이다. 닭 => 알, 알 => 닭)

입력값이 충분히 커야하는 이유는 적어도 교점 이상의 input이 들어왔을 때, 분석법이 유의미하기 때문이다.

점근 표기법

표기법에 앞서

앞에서 얘기했는데 우리는 최고차항만 보고 또 최고차항의 계수는 무시하기로 했다. 이 말은 2x, 2x + 1 등은 그냥 x로 취급하고, 2x2, 100x2 - 10x + 1 등은 x2로 취급하고. 그럼 이런 생각을 할 수 있다. 그럼 x와 x2처럼 기준이 되는 것들이 있지 않을까? 맞다. 그리고 또 이걸 다르게 얘기하면 x를 기준으로 여기에 속하는 함수들이 있을 것이고, 또, x2에 속하는 것들이 있을 것이다. 집합이 생각나지 않는가? 맞다. 집합과 정말 관련이 짙다. 자, 그러면 먼저 그 기준이 되는 함수들을 먼저 보고, 대표적인 점근 표기법 3개를 보자.

속도 비교

바로 아래에 있는 좌표평면 말고 그 다음에 나오는 좌표평면을 보면 알겠지만 초록색보다 보라색이 더 성능이 떨어진다. 다시 말하지만 다시 한번 입력값이 충분히 크지 않다면 점근적 분석이 크게 의미가 있지 않다. 예를 들어, 내가 생각한 알고리즘이 초록색, 보라색 두가지가 있는데 입력값이 기껏해야 5라면, 원래 우리는 보라색의 성능이 더 나쁘다고 알고 있었는데, 초록색이 더 나쁘지 않은가? 게다가 5정도 되는 입력값이면 성능상 그렇게 큰 차이도 없어서 굳이 분석하고 있을 필요는 없을 것 같다.(항상은 아니다!)

이게 진짜다

성능 좋은 순으로(x축과 가까운 순으로). 좌표평면에는 상수 그래프는 없다. 간략하게 말하자면 우리가 어떤 입력값을 넣어도 고정된 시간이 걸린다면? 천만, 천조 등 무엇을 넣어도 상수시간이 걸린다면? 그럼 그건 제일 효율이 좋을 수 밖에 없다.

$$ 상수 \; < \; log \; x \; < \; x \; < \; x\,log \; x < \; x^2 \; < \; 2^x $$ 상수는 빼고, 아래 그래프 색깔로 맞추자면 $$ 상수 없음 < 파란색 < 초록색 < 보라색 < 검정색 < 빨간색 $$

3가지 대표적인 점근 표기법

지금부터 점근 분석법에 대해 조금 더 자세하게 들여다볼 예정이다. 앞서 말한 점근적 분석을 표기하는 방법에는 대표적으로 3가지가 있다. 더 나아가면 스몰o 등도 있지만 여기서는 다루지 않는다. $$ O \; , \; \Theta \;,\; \Omega $$ Big-O빅오 / Theta세타 / Omega오메가이다. 각 문자 뒤에 있는 괄호에 식을 넣는데 그 식에 대한 집합을 나타낸다. 위의 표기법들은 각 집합의 조건에서 딱 한가지만 다르고 전부 동일하다. 먼저 공통된 부분을 먼저 살펴보자. $$ f(n) = 5n^2 + 10n + 1 $$ 위와 같이 함수식이 있다고 생각해보자. 우선 우리는 점근적 분석을 할 때, 편의상 최고차항만 보기로 했다. 그럼, 다음과 같아질 것이다. $$ 5n^2 $$ 또, 우리는 계수를 무시하기로 했으니 다음과 같아질 것이다. 왜 이렇게 하는지는 앞서 설명했는데, 다시 한번 언급하자면, 결국 충분히 큰 입력값만 들어온다면 다른 유형의 최고차항과 비교했을 때의 결과가 유사해지기 때문이다. $$ n^2 $$ 그래서 위 함수 f(n)에 대하여 다음이 성립한다. $$ f(n) \in O(n^2) \; f(n) \in \Theta(n^2) \; f(n) \in \Omega(n^2) $$

보통은 다음과 같이 등호로 표기하는데 같은 뜻이다. $$ f(n) = O(n^2) \ \; f(n) = \Theta(n^2) \ \; f(n) = \Omega(n^2) $$

그럼 차이점은 뭘까? 각각 다음과 같은 말을 추가해주면 된다. Big-O빅오는 기껏해야(at most), Omega오메가s는 적어도(at least), Theta세타는 별다른 말을 넣어줄 필요는 없고 빅오와 오메가의 교집합이라고 이해하면 좋을 것 같다. 그럼 각각을 이해를 돕기 위해 y와 x2 를 이용한 그래프들을 보도록 하자.

  • Big-O빅오 : 기껏해야(at most) $$ O(n^2) \ \ \; \; y \le x^2 $$

색칠된 영역을 보면 알 수 있듯이, 5x + 1, 2logx + 10 등도 전부 O(x2) 포함된다. 하지만 이렇게 널럴하게 잡아버리면 그만큼 정보의 손실이 있기 때문에 가능하면 폭 좁게 잡아야 한다. 방금 얘기한 식들의 경우 각각을 O(x), O(log x)로 잡는 것이다.

  • Omega오메가: 적어도(at least) $$ \Omega(n^2) \ \ \; \; y \ge x^2 $$
  • Theta세타: (빅오와 오메가의 교집합!) $$ \Theta(n^2) $$

정리

우선 점근적 분석법에서는 최고차항 외의 다른 항들은 계산할 때 제외시키고, 최고차항의 계수 역시 취급하지 않는다. 그렇게 해서 함수식들은 최고차항의 차수에 따라 집합을 구성하게 되는데, O(f(N))를 예로 말하자면, 빅오 f(N)는 기껏해야 f(N)의 상수비율로 증가하는 함수들의 집합인 것이다. 보기 쉽게 말로 풀어서 조건제시법으로 나타내자면, $$ O(f(N)) = \{ g(N) \; | 0보다 \; 큰\; 상수\; c가 \;있고,\; 0보다\; 작지 \;않은 \;입력값\; N_0,\; 그리고 \;N_0보다 \;큰\; 모든\; N들에 \;대해, \;cf(N)\; \ge\; g(N) \; \} $$ 한번 세타와 오메가인 경우 위에서 어디를 고쳐야할지 생각해보자.

Running Time 분석시 3가지 유형의 케이스들

수행시간을 분석할 때 중요한 3가지 케이스들이 있다. 구체적인 예시들은 다음 글의 주제인 Sorting에서 좀 더 이해하기 좋을 것 같아서 개념만 짚고 넘어가도록 하자. 우리가 알고리즘을 적용할 때, 정말 다양한 상태의 input을 만나게 된다. 우리가 정렬해야하는 배열이 있다고 가정해보자. 이 때 이 배열은 보통 흔하게 무작위로 나열된 상태 뿐 아니라, 정렬된 상태일 수도 있고, 역정렬된 상태일 수도 있다. 어떤 상태의 배열인지에 따라 성능이 좋은 알고리즘도 달라진다. 즉, 같은 배열을 갖고 다양한 정렬 알고리즘을 돌렸을 때 작업량의 차이가 있을 것이라는 것이다. 그럼 우리가 알고리즘의 성능을 파악할 때 어떻게 해야할까? 대표적으로 Best Case, Average Case, Worst Case 각각 3가지의 경우에서의 성능을 분석하는 방법들이 있다. Best Case는 어떤 알고리즘에서 가장 짧은 시간이 걸리는, 즉, 성능이 가장 좋은 케이스를 말한다. 하지만 우리는 이미 삶은 통해 알고 있지 않은가? 최악을 생각해야 위험에 대비할 수 있지 않을까? 이와 마찬가지로 좋은 케이스보다는 Worst Case에 좀 더 중점을 둬야 한다. 이것은 가장 시간이 오래 걸리는 경우를 말하는 것인데, 어떤 경우에 우리가 작성한 알고리즘이 성능이 낫다면 이에 대한 대책을 내세울 수 있을 것이다. 그리고 또 하나 중요한 것은 모든 경우의 성능의 평균값인 Average Case이다. 항상 나쁜 것만 들어오는 것을 생각할 수도 없는 노릇 아닌가? 언제나 최악의 케이스만 생각하며 만들게 되면 오히려 실제와 달라져 성능 향상에 크게 영향을 못 미칠 수도 있다. 그 때, 그 때 달라요를 잊지 말자.