증가율을 보는 이유
입력이 두 배가 될 때 처리량이 어떻게 늘어날지 이해하면 큰 자료에서의 한계를 예상할 수 있다. 하지만 복잡도 기호가 초 단위 시간을 직접 알려 주지는 않는다. 어떤 연산을 기본 비용으로 보는지와 입력 크기의 정의도 중요하다. 숫자의 자릿수가 늘어나는 문제라면 산술 연산을 언제나 같은 비용으로 가정해도 되는지 검토한다.
상수가 만드는 차이
가상의 두 구현 비용을 각각 100n과 n의 제곱으로 단순화해 보자. n이 10이면 앞은 1000, 뒤는 100이고 n이 1000이면 앞은 100000, 뒤는 1000000이다. 작은 구간에서 이긴 구현이 큰 구간에서도 이긴다고 보장할 수 없다는 예시다. 실제 프로그램이 이 식대로 움직인다는 측정 주장은 아니다.
숨은 작업을 포함하기
정렬 뒤 이진 탐색을 한 번 하는 프로그램에서 탐색 단계만 로그 시간이라고 설명하면 정렬 비용을 놓친다. 입력을 읽고 자료를 변환하거나 결과를 출력하는 비용도 전체에 포함된다. 반복 조회에서 한 번의 준비 비용을 나누어 볼지에 따라 분석 목적이 달라진다. 사용자가 겪는 전체 작업과 분석한 구간을 연결해야 한다.
측정 조건의 일치
실제 시간은 캐시 상태와 장비 부하, 최적화와 실행 환경의 영향을 받을 수 있다. 같은 입력과 같은 기능 결과를 비교하고 준비 단계가 포함되었는지 맞춘다. 반복 결과의 변동도 기록한다. 작은 코드 조각의 측정이 전체 서비스 성능을 그대로 대표한다고 가정하지 않는다.
함께 사용하는 방법
복잡도 분석으로 커지는 입력의 위험과 필요한 자료구조를 판단하고 측정으로 실제 조건의 병목을 확인한다. 여러 크기에서 결과를 보면 이론적인 경향과 구현 비용의 관계를 이해하기 쉽다. 빠른 실행 한 번을 일반적인 우위로 삼지 않고, 더 좋은 증가율이라는 이유로 모든 환경에서 빠르다고 단정하지도 않는다.
관련 문서
알고리즘 / 이진 탐색 / 프로파일링 결과 해석 / 성능 비교 실험 설계