한 줄씩 실행하며 대입 횟수를 누적한다
함수와 n에 따라 코드 줄별 실행 횟수가 달라진다. 단계 이동은 현재 실행과 누적 연산 수를 같은 시점에 보여 준다.
여기서 세는 연산
total, value, count에 값을 넣는 명시적 대입만 센다. 반복 제어, 함수 호출, 반환은 세지 않는다.0회
계산 모형이 달라지면 세는 대상도 달라진다
대입 모형과 산술 모형은 횟수를 세는 연산이 서로 다르다. 계산된 식은 해당 모형의 연산 수이지 기계 시간이 아니다.
sum_loop: T(n) = 1 + n
sum_extra: T(n) = 1 + 2n
total과 count 갱신: T(n) = 2 + 2n
반복 안의 대입 한 줄이 늘면 n회가 추가된다.
n + 1 · 1회
곱셈 · 1회
정수 나눗셈 · 1회
지정한 산술 연산은 3회지만 큰 정수의 실제 시간은 자릿수에도 영향을 받는다.
연산 수는 코드 구조를 설명하고 실행 시간은 특정 언어, 구현, 컴퓨터에서 측정한 값이다.