Order

Time complexity

시간 복잡도는 알고리즘이 수행되는 데 걸리는 시간을 의미하며,

시간 복잡도가 클 수록 알고리즘이 수행 되기까지 걸리는 시간이 길다는 것을 의미한다.

 

시간 복잡도를 계산하기 위해선 2개의 파라미터가 필요하다.

- Input size

입력으로 들어온 값의 크기를 의미한다.

입력으로 들어온 값은 배열일 수도, 특정 값이나 문자열, 혹은 graph와 같이 vertices, edges가 들어올 수 있다.

 

- Basic operation

알고리즘은 여러 줄의 코드로 이루어진다.

그 중 핵심이 되는 코드를 기본 연산으로 삼아서 시간 복잡도를 계산한다.

예로 들어 순차 탐색 알고리즘의 경우에는 배열의 특정 index와 찾고자 하는 값의 비교 연산이 이에 해당한다.

 

시간 복잡도 분석은 모든 input size에 대해 얼마나 basic operation이 수행되었는지를

수학적으로 분석하는 것이다.

현실적으로 모든 input size에 대해 분석하는 것은 불가능하기에 input size n에 대해

각 알고리즘별로 best, worst, average case (혹은 every case)를 분석하게 된다.

 

 

Order

여러 알고리즘의 각각의 시간 복잡도가 존재할텐데, 이들의 시간 복잡도를 일일히 비교하는게 쉽지 않다.

따라서 시간 복잡도를 일종의 그룹으로 묶어서 같은 그룹에 속한 알고리즘은 비슷한 효율을 낸다고 판단하게 된다.

그것이 가능한 이유는 알고리즘을 분석할 때 "충분히 큰 input"에 대해 생각하고 분석하기 때문이다.

 

n + 100, n의 시간 복잡도를 갖는 두 알고리즘이 있다고 가정해보자.

n=1인 경우에 대해서는 두 알고리즘은 101배 라는 엄청난 효율성의 차이를 보인다.

하지만, n=1억인 경우에 대해서는? 두 알고리즘의 효율 차이가 무의미 해진다.

 

그럼 알고리즘을 order하는 방법을 알아보자.

(참고로 Big O, Omega를 정의 한 뒤, 이 둘을 바탕으로 Theta를 정의하고,

추가로 Small o에 대해서도 알아보자)

 

- Big O

간단하게 말하면 O(f(n))에 대해 최고차항의 차수가 f(n)보다 작거나 같으면 O(f(n))에 포함된다.

자세하기 말하면 아래의 식을 만족하는 함수(시간 복잡도 함수)의 집합이 O(f(n))가 된다.

풀어 쓰면, 특정 c와 N이 존재하여 다음의 식이 성립하면 그 함수(g)는 O(f)에 포함된다는 뜻이다.

 

증명 예시를 들어보자.

모순에 의한 증명 예시를 들어보자.

 

- Omega

간단하게 말하면 Ω(f(n))에 대해 최고차항의 차수가 f(n)보다 크거나 같으면 Ω(f(n))에 포함된다.

자세하기 말하면 아래의 식을 만족하는 함수(시간 복잡도 함수)의 집합이 Ω(f(n))가 된다.

풀어 쓰면, 특정 c와 N이 존재하여 다음의 식이 성립하면 그 함수(g)는 Ω(f)에 포함된다는 뜻이다.

 

증명 예시를 들어보자.

 

모순에 의한 증명 예시를 들어보자.

 

- Theta

간단하게 말하면 Θ(f(n))에 대해 최고차항의 차수가 f(n)와 같으면 Θ(f(n))에 포함된다.

자세하기 말하면 아래의 식을 만족하는 함수(시간 복잡도 함수)의 집합이 Θ(f(n))가 된다.

풀어 쓰면, 특정 c와 N이 존재하여 다음의 식이 성립하면 그 함수(g)는 Θ(f)에 포함된다는 뜻이다.

즉, Big O와 Omega를 모두 만족하는 시간 복잡도 함수 g가 Θ(f)에 포함된다.

 

- Small o

간단하게 말하면 o(f(n))에 대해 최고차항의 차수가 f(n)보다 작으면 o(f(n))에 포함된다.

자세하기 말하면 아래의 식을 만족하는 함수(시간 복잡도 함수)의 집합이 o(f(n))가 된다.

풀어 쓰면, 모든 c에 대해, 특정 N이 존재하여 다음의 식이 성립하면 그 함수(g)는 o(f)에 포함된다는 뜻이다.

즉, Big O의 경우에는 위 식을 만족하는 c가 하나만 존재하면 포함이 되었지만,

Small o의 경우에는 모든 c에 대해 위 식을 만족해야 포함이 된다.

 

그렇기에 g가 f보다 더 효율적인 알고리즘이라는 지표가 된다.

 

모순에 의한 증명 예시를 들어보자.

 

Determine Order using Limit

BIg O, Omega는 할만할 지 몰라도, Theta, small o는 이를 분석하는게 꽤 까다롭다.

하지만, 극한의 개념을 이용하면 이를 간단하게 분석할 수 있다.

 

간단하게 말해서 최고차항의 차수로 비교했었다.

이를 극한의 개념으로 적용해보면 위와 같은 결과를 도출할 수 있다.

이를 이용하면 복잡한 시간 복잡도 함수도 로피탈의 법칙 등을 이용하면 order을 나름 쉽게 구할 수 있다.