함수의 점근적 분석법

함수의 점근적 분석법

: 문제의 크기(주어진 숫자)가 매우 클 때 내가 만든 알고리즘이 얼마만큼의 계산량을 요구하는가를 분석하는 것

 

Linear Search와 Binary Search의 비교를 예로 들면

 

Linear Search

:어떤 값을 찾으려고 할 때 앞에서부터 순차적으로 체크하는 것

Binary Search

:Array가 sorting 되어있을 때만 사용 가능. 중간값과 찾고자하는 값을 비교해서 중간값보다 찾고자하는 값이 작으면 중간값을 기준으로 왼쪽부분만 검색하면 됨

 

⇒n이 증가함에따라 Linear Search 계산량도 증가하지만 Binary Search는 크게 증가하지 않는것으로 보아 이 경우에는 Binary Search가 더 효율적인 알고리즘이라고 볼 수 있다.

 

 

알고리즘 분석

• 알고리즘이 주어졌을 때 무엇을 성능의 지표로 삼을지를 결정해야 한다.
• data structure와 알고리즘의 관계성을 고려해야함
• 우리가 이 알고리즘을 어떤 컴퓨터나 머신에서 구동되는지 고려하지말고 온전히 수학적으로만 생각한다.
• 주어진 수가 무한히 커졌을 때 두 알고리즘의 차이가 어떻게 되는지를 분석하는것이다. = 가장 높은 차수의 계수가 중요하다. ex)n^-1 = n^ + 3n + 2

 

두 알고리즘 f(n)과 g(n)이 다항식으로 표현됐을 때

• f(n)의 최고차항의 계수 : α
• g(n)의 최고차항의 계수: β
• M = α/β +1

위와 같은 조건일때

f(n) < Mg(n)

이 항상 성립한다는 것을 알 수 있다.

 

하지만 다음과 같이 차수가 다르면

f(n)은 g(n)을 절대 따라잡을 수 없다.

 

따라서

가 성립한다면 이 두 함수는 동일한 복잡도를 가진다고 할 수 있다.

라면 f(n)이 g(n)보다 낮은 복잡도를 가지고 있다. 즉 f(n)이 효율적인 알고리즘이다.