5.5.2 중요한 단계

이전 예제를 한층 더 깊이 분석해 보자. 첫 번째 버전인 print_numbers_version_one는 N단계가 필요하다고 말했다. 루프를 upperLimit만큼, 즉 N번 실행하기 때문이다.

하지만 정말로 딱 N단계가 필요할까?

나눠서 살펴보면 매 루프 안에서 여러 단계가 일어남을 알 수 있다.

첫째, number가 2로 나누어 떨어지는지 확인하는 비교 단계(if number % 2 == 0)다. 비교는 매 루프마다 일어난다.

둘째, 짝수일 때만 일어나는 출력 단계(print(number))다. 따라서 출력은 한 번 걸러 일어난다.

셋째, 매 루프마다 실행되는 number += 1이다.

앞선 장들에서 알고리즘의 빅 오를 표현할 때 어떤 단계를 세어야 하는지 결정하는 법을 배우겠다고 언급했었다. 그렇다면 예제에서는 어떤 단계를 중요하게 고려해야 할까? 비교나 출력, number 증가 중 무엇이 중요할까?

정답을 말하자면 모든 단계가 중요하다. 단지 빅 오 용어로 단계를 표현할 때 상수를 버리고 표현식을 단순화할 뿐이다.

위 예제에도 적용해 보자. 모든 단계를 센다면 N번의 비교와 N번의 증가, N / 2번의 출력이 있다. 모두 합해 2.5N단계다. 하지만 상수 2.5가 제거되니 O(N)이라고 표현한다. 그럼 어떤 단계가 중요했을까? 모두 중요하지만 상수를 제거함으로써 루프 안에서 정확히 무슨 일이 일어나는지 보다는 실질적으로 루프가 실행되는 횟수에 더 초점을 맞추게 된다.