2.2.1 어림짐작해보기

시간 복잡도는 정확한 실행 시간을 계산하는 용도가 아닙니다. 단지 실행 시간이 어떤 요인으로 결정되는지 나타내는 수식일 뿐입니다. 따라서 시간 복잡도에서는 곱하거나 더해지는 상수 부분은 나타내지 않습니다.

▲ 그림 2-3 O(N) 시간 복잡도로 표기되는 여러 실행 시간 함수

예를 들어 길이가 N인 배열의 반만 사용하는 알고리즘이 있다고 합시다. 이때 반복 횟수는 N/2일 것입니다. 이는 빅오 표기법으로 O(N/2)로 나타낼 수 있지만 상수 부분을 제외하고 O(N)으로만 표기합니다. N에 비례한다는 것을 나타내기 위해서입니다. 이와 비슷하게 길이가 N인 배열을 두 번 반복하는 경우 또한 O(2N)이 아니라 O(N)으로 표기합니다. 즉, O(N) = O(2N) = O(N/2)가 성립합니다.