알고리듬분석2 - Introduction to Algorithms ch3 Growth of Function

Growth of Function

 -  Time complexity를 보여줌으로써 알고리즘의 Efficiency를 간단하게 보여줄 수 있다.

 

Asymptotic efficiency : input의 크기가 충분히 클 때, 효율성을 분석 할 수 있다

 - 점근적 이라는 뜻

따라서 시간복잡도의 평가는 input의 크기가 무한일 때를 기준으로 측정해서 표기한다.

Notation 표기 방법

Notation 표기

O - notation (upper bound)

Big O notation 관련 설명

BIG O의 경우 O(g(n))의 증가율이 f(n)을 넘지 않는 것을 의미합니다. 

사진으로 예를 들면 빨간색 선으로 되는 부분이 g(n) = 2n^2 + 1 이고 n 이 무한으로 갔을 때, 시간 복잡도는 n^2이 된다.

이때, n^2 은 그 어떤 숫자를 넣어도 2n^2 + 1의 값을 넘길 수 없다. ( n^2 > 2n^2 + 1)

따라서 O(g(n)) 라고 표기할 수 있다. ( 본인은 아무리 커도 넘을 수 없을때 Big O 라고 외웠음)

Notation 표기 방법에는 작거나 같으면 이라고 되어있다.

 

Ω- notation (Lower bound)

 

오메가 notation 관련 설명

오메가도 BIG O 와는 반대로 증가율이 아무리 커도 f(n)을 넘길 수 없는 것을 의미 한다.

Notation 표기 방법에도 크거나 같으면이라고 되어있다.

 

Θ - notation (tight bound)

Θ notation 관련 설명

Θ의 경우, BIG O 와 OMEGA 둘다를 만족 할 때, 즉 같을 때 사용하는 표기법이다.

그래서 tight ( = ). 

예를 들어 n + 1 는 Θ(n) 으로 표현 할 수 있는 것이다.

세타(Θ) 로 표시 할 수 있으면 빅오 로도 오메가로도 표현이 가능하다

 

세타의 proposition

 

세타에 대해서 이해했다면 위 사진 (Proposition)에 대해서는 쉽게 이해 할 수 있음.

 

 

요약

앞서 설명한 것에 대한 요약

모든 notation들은 As tight as possible! ( 가능한 세타를, 세타를 사용 할 수 없을 때에는 BIG O를)

 

이 외에도 Little O 와 Little Omega 가 존재하는데 이 둘은 각각 BIG O 와 BIG Omega에서 세타가 빠진 값이다.

little o = BIG O - Θ (same for little omega)

위의 Notation 사진을 보면 쉽게 이해 할 수 있다.

 

 

Optimality of algorithm

- 모든 문제들은 풀기 위한 최소한의 complexity (Lower-Bound of Problem) 가 존재한다.

 - 따라서 앞서 설명한 Worst-case 와 최소한의 complexity 가 일치 하면, 알고리즘이 Optimal 하다고 표현한다.

 

 

 

Asymptoyic Analysis

• 어떤 방식이 더 나은지 알려주는 useful tool 이 될 수 있다
• TIme complexity가 더 느리다고 해서 무시할 수 는 없다.

250까지의 각각의 time complexity

250 까지의 그래프를 보면  n^3 가 2^n 보다 더 빠른 시기에 250이라는 값을 가지게 되었다. 즉 효율성으로 보았을 때 2^n이 더 좋아보인다.

1000 까지의 각각의 time complexity

 

1000까지의 그래프를 보면 둘이 비슷한 시점에 만난 것 같아 보인다.

5000 까지의 각각의 time complexity

5000까지의 그래프에서는 2^n이 훨씬 빠른 시간안에 5000이라는 숫자에 도달한다.

 

이렇게 그래프들의 범위를 통해 각각의 time complexity의 효율이 달라지는 모습을 보아 현실에서는 각기 다른 기준이 필요해 보인다.