점근적 분석

어떠한 데이터 구조 또는 알고리즘일지라도 모든 상황에서 최적의 성능을 제공하지는 못한다. 그렇기에 어떤 데이터 구조 또는 알고리즘이 최적의 성능을 낼 수 있는지 확인하기 위해 실행 속도를 측정한다.

입력값이 소규모일 때는 어떤 알고리즘을 쓰더라도 일정 수준 이상의 속도 또는 효율성을 기대할 수 있다. 하지만 우리가 알고리즘의 실행 비용 또는 복잡성의 측정에 대해 이야기할 때는 입력값이 상당히 큰 규모임을 의미한다. 점근적 분석^{asympotic analysis}이란 무한대의 가까운 입력값을 분석하는 데 걸리는 시간을 측정하는 방법이다.

• 최악의 상황(데이터가 폭주하는)의 경우, 얼마만큼의 저장 공간이 필요한가?
• 알고리즘이 특정 규모의 입력값을 처리하는 데 걸리는 시간은 얼마인가?
• 그 문제를 해결할 수 있는가?

일반적으로 점근적 성장 속도가 느릴수록 알고리즘의 성능이 좋은 것으로 판단한다.

데이터 크기 분석 방법

정렬 알고리즘의 실행 시간 측정에 있어 우리는 상수 c 또는 k 가 정확히 어떤 값인지 모른다. 실제 상수의 값을 측정하고 싶더라도, CPU의 성능 설정, 그리고 프로그래밍 언어에 따라 상수가 달라질 수 있으며, 알고리즘의 실행 환경이 완전히 동일한 경우에만 측정이 가능하므로, 점근적 분석에 의한 실행 시간 측정에서 상수를 무시하는 경우가 대부분이다.

컴퓨터 과학에서, 빅오^Big-O는 함수의 점근적 분석을 표현하는 가장 대표적인 방법 중 하나이며, 알고리즘 표현에서 상수를 감춤으로써 좀 더 간편하게 실행 속도를 측정할 수 있다. 빅오는 함수의 알고리즘 실행 시간 중 외부 경계선 즉 성장의 순서^{order of growth}를 비교한다. 외부 경계선은 해당 알고리즘이 분석을 완전히 마치기까지 걸릴 수 있는 최대 시간을 의미한다.