[Algorithm] Analysis - time complexity, big & small notations

Analyzing an algorithm

알고리즘을 분석한다면 다양한 요소들을 고려해야 할 것이다. Memory, communication bandwidth, or computer hardware 등 알고리즘이 요구하는 자원을 예측하는 것도 중요하지만, 대부분의 경우 Computational time이 제일 중요하게 여겨진다. 우리는 다양한 알고리즘 중에서 가장 효율적인 알고리즘을 찾아낼 수 있고, 상대적으로 빈약한 알고리즘을 걸러낼 줄 알아야 한다.

 

Complexity

어떤 알고리즘이 효율적인 알고리즘인지 알기 위해서 중요한 것은 바로 복잡도이다. 주어진 수 집합을 정렬하는 문제 해결의 경우를 생각해 보면, 같은 크기의 수 집합이라고 하더라도 그 구성에 따라 알고리즘의 수행 시간이 다를 것이다. 우리는 그러한 수 집합의 각 크기에 따른 모든 가능한 경우를 생각해 볼 수 있다. 그리고 그 모든 경우를 고려했을 때 문제 해결 시간이 가장 오래 걸리는 경우 (Upper bound), 가장 적게 걸리는 경우 (Lower bound), 그리고 평균적으로 걸리는 경우를 생각해 볼 수 있다.

 

 

Worst-case complexity

size가 n일 때 가장 많은 계산이 필요한 경우로, 위 그래프에서 가장 위에 놓인 곡선에 해당된다. Counterintuitive 한 특징으로 인해 그 모든 경우에서 최악의 경우를 보장해 주므로, 세 가지 경우 중 가장 유용하게 여겨지고 있다.

Best-case complexity

위와 반대의 경우이다. 위 그래프에서 가장 아래에 놓인 곡선에 해당된다.

Average-case complexity

평균적인 경우이다. 가운데에 위치해 있다.

 

Asymptotic notation

고등학교에서 다루는 함수의 극한 개념을 생각해 보면, x가 무한으로 갈 때 우리가 고려해줘야 할 것은 다항식인 경우 최고차항의 계수였다. 그 이유는 나머지는 무시될 수 있기 때문. Complexity를 고려할 때에도 마찬가지이다. input size가 커짐에 따라 덜 중요한 부분의 수식은 무시될 수 있다. 이렇듯 입력값이 뭐든 간에 걸리는 시간을 특징화할 수 있는 가장 적절한 명명법이 바로 Asymptotic notation이다. 대부분의 경우에서 아주 작은 input을 제외하고 이러한 근사적 명명법은 가장 효율적인 방법이다.

 

Θ - notation

 

특정 알고리즘의 모든 경우의 복잡도를 아우르는 개념이다. 모든 알고리즘을 Θ notation으로 표현할 수 있는 것은 아니다. 만약 이 알고리즘이 상한과 하한을 모두 가지고 있다면 나타낼 수 있는 명명법이다.

 

Θ(g(n))에 f(n)이 포함된다

f(n)이 Θ(g(n))의 member이다

f(n) = Θ(g(n))

g(n)이 f(n)을 위한 asymptotically tight bound이다

 

모두 같은 표현이다. 이 부분에서는 asymptotically nonnegative라는 표현을 알아두고 갈 필요가 있다. 한국말로는 점진적으로 0 이상의 값을 가진다는 의미인데, 만약 g(n)이 asymptotically nonnegative가 아니라면 Θ(g(n)) 집합은 비었다라고 할 수 있다. 

 

O - notation

 

만약 특정 알고리즘이 상한만을 가지고 있다면 우리는 빅-오 명명법을 사용한다. 따라서 상한과 하한으로 조건이 있는 Θ-notation 보다 더 하위 개념이며, 특정 알고리즘의 Θ-notation 집합은 O-notation의 집합에 포함될 수밖에 없다.

 

Ω - notation

 

마지막의 경우이다. 예상했겠지만 특정 알고리즘이 하한을 제공할 때 사용된다. 빅-오메가라고 불리는데, 빅 오와는 반대로 특정 알고리즘의 최소의 시간복잡도를 나타내는 데에 쓰인다. 예를 들어 삽입 정렬 (Insertion sort)의 경우 Ω(n)와 O(n²)의 시간복잡도를 가진다. 그리고 이런 bound가 삽입 정렬이 가질 수 있는 최대한 tight 한 bound가 될 수밖에 없다.

 

만약 어떤 알고리즘이 점근적 상한과 하한을 모두 가지고 있다는 것은 Θ-notation와 필요충분조건이라고 할 수 있다.

Problem: Is (x + y)² = O(x² + y²)?

 

Growth rates and dominance relations

수식들이 가지고 있는 증가율의 대소관계는 input의 값이 커질수록 계수와는 상관없이 결국 그들의 순서로 배치되게 되어있다. 계수가 중요한 영향을 미치는 경우는 비교하는 두 수식의 차수가 같을 때뿐이다. 우리는 따라서 다음의 지배적 관계만을 외워두면 대소비교를 쉽게 할 수 있을 것이다.

 

Little asymptotic notations

o-notation

간단히 설명하자면 빅 오 표기법과는 달리 상한의 차수보다 한 차수 낮을 필요가 있다. 이게 무슨 말이냐면, 빅 오의 경우 그러한 조건을 만족시키는 단 한 가지의 경우라도 있다면 만족이지만 리틀 오는 모든 경우에서 0 ≤ f(n) < cg(n)을 만족해야 한다.

 

w-notation

마찬가지이다. 모든 경우에서 0 ≤ cg(n) < f(n)을 만족해야 한다.

 

이 모든 표기법에 대해서 서로의 관계를 알아두면 좋다.