점근적 분석(Asymtotic Analysis)과 분할 상환 분석(Amortized Analysis)

1. 점근적 분석(Asymtotic Analysis) 이란 

임의의 함수가 N -> ∞ 일때, 어떤 함수 형태에 근접해지는지 분석하는 방법이다.

예를들어 f(n) = n2 + 3n 일때, n이 매우 커진다면, 3n은 n2에 비해서 중요도가 떨어진다.

n이 매우 커진다면, "f(n) is asymptotic to n2" 라고 할 수 있다.

이 접근적 분석때문에 시간 복잡도 계산시 최고차항을 제외한 모든 항과 최고차항의 계수를 무시하는 것이다.

 

2. 점근 표기법(Asymtotic Notation)

점근 표기법에는 세 가지 표기법이 있다.

 

(1) Big- omega (Ω): lower bound. 점근적 하한

 

(2) Big-O (O): upper bound. 점근적 상한

 

(3) Big-theta (Θ): tight bound

 

이 세 표기법은 best case, worst case를 따지는 것이랑은 다르다.

예를들어, 배열에서 특정 값이 있는지 찾기 위해서는 best case에서 lower bound = 1, upper bound = 1이다. 따라서 tight bound 또한 1 이므로 Θ(1) 이라고 할 수 있다.

worst case 에서는  lower bound = n, upper bound = n이다. 따라서 tight bound 또한 n 이므로 Θ(n) 이라고 할 수 있다.

average case에서는 lower bound를 특정 짓는 것이 어려우므로, upper bound 만을 사용해 O(N/2) = O(N) 이라고 표현 할 수 있다.

 

출처 : https://www.khanacademy.org/

running time이 k2n과 k1n 사이에 있을 때, running time을 Θ(1)이라 할 수 있다 (점근적 분석에 따라서 상수 제거)

 

예를들어, binary search의 worst-case running time이 Θ(log2​n)이지만, binary search가 모든 시간 에 Θ(log⁡2n)이라고는 할 수 없다. 

처음에 바로 찾으면 Θ(1)이다. 

Θ(log⁡2n)보다 나빠질 수는 없지만, 가끔 더 낫다.  이 경우 상한선을 통해 표현 할 수 있다.

출처 : https://www.khanacademy.org/

Binary search에서 항상 O(log2​n)이라 할 수 있다. 

worst-case에서는 더 tight하게 Θ(log2​n)이라 할 수 있는 것이다. 

모든 경우를 포괄하는 경우에, binary search가 O(log2​n) time이라고 할 수 있다. Θ(log2​n)는 특정 상황에서만 적용 된다.

(best-case에서는 tight  bound가 Θ(1)이기 때문)

 따라서 binary search가 항상  O(log2​n)로 동작하지만, 항상 Θ(log2​n)로 동작한다고 할 수 는 없다.

big-O는 상한선이기 때문에 binary search가 O(N), O(N^2) , O(2^N)이라 해도 상관 없다. 

하지만 Θ(N), Θ(N^2) , Θ(2^N)이라고는 할 수 없다.

 

big-Omega는 반대로 하한선을 나타낸다.

binary search의 worst-case에서 Ω(1)이라고 할 수 있다. 이것 또한 항상 모든 경우 Ω(1)이라고 할 수 있다.

 

3.  분할 상환 분석 (amortized analysis)

예를 들어 보자. 커피를 만드는 기계가 있다. 만약 기계에 남은 커피가 있으면 컵에 따르기만 하면 되고, 10초가 걸린다.

반대로 남은  커피가 없다면 커피를 만들어야 하는데, 이는 10분이 걸린다.

대신 한번에 10인분의 커피를 만들 수 있다. 

 

이 때, 최악의 경우 10분의 시간이 걸린다 할 수 있다. 운이 좋으면 10초면 된다.

하지만 이렇게 분석하는 것이 커피를 가지고 오는 시간을 잘 반영한다고 할 수 있을 까?

 

예를들어, 100명의 사원이 커피를 가지러 갔을 때, 10명은 10분이 걸려 총 100분이 걸리고, 나머지 90명은 10초면 된다.

따라서 평균적으로 1분 정도의 시간이 필요하다고 결론 내릴 수 있다.

 

이렇게 어느 자료 구조의 연산들의 임의이 시퀀스가 주어졌을 때, 그 시퀀스 위의 모든 연산들이 수행되는 동안 각 연산의 평균적인 수행 시간을 분석하는 방법을 분할 상환 분석이라고 한다.

이와 대조 되는 분석 방법이 최악의 경우 분석 (worst-case analysis)이다.

분할 상환 분석은 평균의 경우 분석(average-case analysis)와는 다른데, 이는 평균의 경우 확률의 개념을 포함하지만 분할 상환 분석은 확률의 개념을 포함하지 않는 점에서 다르다. (자세한것 아래 reference 참고)

 

분할 상환 분석을 계산하는 방법에는 회계법, 퍼텐셜법 등이 있지만, 생략하고 핵심은

 

분할 상환 분석은 상황에 따라 성능이 크게 변동하는 연산이나 알고리즘의 "최악의 경우에도 평균적인" 성능을 측정해 해당 연산이나 알고리즘의 실제 성능을 과도하게 평가 절하 하는 것을 막을 수 있는 분석 기법이다.

 

따라서 배열에서 값을 추가 할 때, doubling이 일어날  수 있기에 최악의 경우 새로운 배열을 생성하고 복사하기에 O(N)의 시간복잡도가 걸릴 수 있지만, 분할 상환 분석에 의해서 배열에 값을 추가하는 것을 O(1)이라고 할 수 있는 것이다.

 

Reference:

https://gazelle-and-cs.tistory.com/87

분할 상환 분석 (Amortized Analysis)

https://www.khanacademy.org/computing/computer-science/algorithms/asymptotic-notation/a/big-big-omega-notation

Big-Ω (Big-Omega) notation (article) | Khan Academy

https://www.youtube.com/watch?v=tTFoClBZutw