한 단계가 어느 코드 줄의 비용인지 연결한다
단계는 실제 반복 본문이 실행되는 순서를 따른다. 반복 제어와 함수 호출 비용은 이 모형에서 세지 않는다.
정확한 식에서 증가 차수를 분리한다
위 절에서 고른 입력 크기 n과 코드 예제를 그대로 쓴다. 같은 n에서도 반복 구조가 다르면 정확한 연산 수와 최고차항이 달라진다.
| 반복 구조 | 정확한 연산 수 | 현재 값 | 증가 차수 |
|---|
시간과 공간은 서로 다른 자원을 센다
같은 애너그램 판정도 복사 목록에서 문자를 찾아 지우는 방법과 26칸 빈도표를 쓰는 방법은 시간과 추가 공간의 증가가 다르다.
| 방법 | 주된 작업 | 시간 | 추가 공간 |
|---|---|---|---|
| 복사 목록 | 남은 문자에서 같은 문자를 찾아 삭제 | Θ(n²), 최악의 경우 | Θ(n) |
| 26칸 빈도표 | 고정된 문자 칸을 갱신하고 확인 | Θ(n) | Θ(1) |
비교 기준같은 과제, 같은 입력 크기 n
따로 셀 자원문자 작업과 추가 저장 셀
정확한 작업 수를 함수로 바꾼 뒤에는 시간과 공간을 한 값으로 섞지 않는다. 더 빠른 방법이 언제나 추가 공간도 더 적게 쓰는 것은 아니다.