함수의 점근적 분석법

1. 점근적 분석법(Asymptotic Analysis)

• 정렬 문제에서 숫자의 이런 것이 문제의 크기가 된다.
  이런 문제의 크기가 아주 크게 증가했을 때, 우리가 갖고 있는 이 알고리즘은 과연 얼마만큼의 계산량을 요구하는가?
  그래서 굉장히 점근적으로 큰 숫자에 대해서 분석하기 때문에 점근적 분석법이라는 이름이 지어짐.
• 만약에 우리가 같은 문제를 푸는 서로 다른 2개의 알고리즘이 있다고 했을때, 컴퓨터 사이언티스트로써 어떤 알고리즘이 다른 것보다 더 좋은지에 대해서 좀 더 과학적으로 수치적으로 표현할 수 있기 위해서 점근적 분석을 다루게 되었음
• 두 알고리즘이 있다고 했을 때, 2개를 비교하는 가장 간단하는 방법은 둘 다 코드로 구현해서 비교하는 것.
• 코드로 구현해서 테스트 케이스를 주고 과연 이 알고리즘은 몇초가 걸리고 저 알고리즘은 몇 초가 걸리는지.
• 이 알고리즘의 메모리는 얼마나 소비되고 저 알고리즘은 메모리를 얼마나 소비하는지를 실제로 측정해 볼 수 있음
• 하지만 위의 방법이 최선은 아님. 프로그래머들은 비싸니까!
• 또한, 사람이 하는 일이다보니 오류가 발생할 수도 있음.
• 그리고 프로그래머의 실력에 따라 달라질 수 잇음
• 그러기에 우리가 추구하는 것은 이런 주어진 알고리즘을 수학적으로 분석해서 과연 이 두 개의 알고름 중에 뭐가 더 좋더라는 결론을 내리고자 하는 것.
  알고리즘을 분석하는데, 이 알고리즘의 런타임, 메모리 요구량이 어떤 변수를 통해 표현되는 것.
• 여기서 변수는 어떤 배열이 있는데 여기에 몇 개의 요소가 있나? 보통 N이라고 표현하는데 이 N이라는 것이 변수가 됨.
• 그런데 어떤 알고리즘이나 문제에 따라선 변수가 단순히 N 하나만 있는 게 아니라 그 이상의 변수들의 조합으로 나타내질 수도 있음.

2. 점근적 분석법의 과정

• 알고리즘이 주어졌을 때, 우리가 알고리즘을 성능 테스트를 했을 때, 무엇을 지표로 삼을 것인가를 먼저 선택해야 함.
• 특정 요소를 검색하는 검색 알고리즘 같은 경우, 몇 번의 비교연산이 수행되었는가가 이 알고리즘의 계산량을 표현하는데 중요한 변수
  가 됨.
• 뿐만 아니라 그 알고리즘 자체도 중요하지만 이것에 연관된 자료구조도 상당히 중요함
• 그래서 점근적 분석법은 알고리즘과 자료구조의 관계성을 고려해서 수행해야 됨.
• 또한 우리가 이 알고리즘을 어떤 컴퓨터나 어떤 os에서 구동시키는가와 상관없이 수학적으로만 이루어져야 한다는 특징이 있음.
  
• 빨간색 그래프가 f(n)=n^2이고, 파란색은 g(n) = n^2-3n+2
• 만약 n=1000인 경우, f(n)=1,000,000이고, g(n)= 997,002가 된다.
• 그리고 이걸 상대적인 비율로 나타내면,
  ( f(1000)-g(1000) ) / f(1000) = 0.002998 < 0.3%
  가 되고, 이 변수를 무한대로 커졌을 때는 이 둘의 상대적 비율의 차이는 0에 수렴한다는 걸 알수 있다.
• 여기서 점근적 분석법의 핵심은 N이 무한히 커졌을 때, 두 알고리즘은 얼마나 차이가 나는가가 핵심!
• 또 다른 예로
  • f(n) = n^6
  • g(n) = n^6-23n^5+193n^4-729n^3+1206n^2-648n
  • 위의 예와 마찬가지로 0의 근처에서는 크게 차이가 나지만,
  • 변수를 크게 줄수록 차이는 줄어듭니다.
• 두 알고리즘의 함수가 다르더라도 결국제 제일 중요한 것은 가장 차수가 높은항! leading term이라고 애기하는 가장 차수가 높은 항이 제일 중요하다!
• 계수의 차이는 컴퓨터의 성능으로 커버칠 수 있다고 해도 차수는 커버칠 수 없다.
  

3. weak ordering

• 수학의 순서론 등장하는 개념 중의 하나.
• 조건:
  • 비반사성: 모든 x에 대해 R(x,x)는 거짓
  • 비대칭성: 모든 x,y에 대해 R(x,y)가 참이면 R(y,x)는 거짓
  • 추이성: 모든 x,y,z에 대해 R(x,y)와 R(y,z)가 참이면 R(x,z)는 참
  • 비비교성의 추이성: 모든 x, y, z에 대해 R(x, y)와 R(y, x)가 거짓이고 R(y, z)와 R(z, y)가 거짓이면 R(x, z)와 R(z, x)는 거짓

참고

• 인공지능을 위한 알고리즘과 자료구조
• Weak ordering(위키백과)