차수의 계수 생략하지 않기

단, 이런 상황에서 시간 복잡도를 측정할 때는 ‘O(n)이네, O(nlogn)이네, O(n²)이네’처럼 단정 짓지 말고 빅오 표기법에 의해 생략되는 차항의 계수도 꼼꼼하게 따져보세요. 측정한 것보다 느리더라도 얼마든지 통과하는 경우도 있고, 반대로 빠르더라도 통과하지 못하는 경우도 있습니다. 시간 복잡도가 프로그램의 실제 실행 시간을 예측하지 못하는 것입니다. 특히 여러 시간 복잡도가 엮이면 이런 상황이 자주 발생하기 때문에 뭉뚱그려서 표현하기보단 차수의 계수까지 모두 계산하여 고려하는 것이 맞습니다(이 내용은 반복해서 언급할 테니 지금은 이런 사항이 있구나 정도로만 생각하면 됩니다).

왜 이렇게 계산해야 하는지 궁금한 분을 위해 간단히 살펴보겠습니다. 3n³ + 5n²이라는 소요 시간을 가진 함수가 있다고 가정하면 빅오 표기법은 O(n³)이 될 것입니다. 1초의 제한 시간을 기준으로 한다면 O(n³)의 최대 입력 개수는 500개 정도가 됩니다. 문제에서 입력 개수가 500개 주어졌고, 자신의 코드를 빅오 표기법으로 계산해보니 O(n³)이 나와서 아슬아슬하게 통과할 것 같다고 생각하여 제출했다면 높은 확률로 실패합니다. 3n³으로는 200개도 감당하기 어려운 코드입니다. 따라서 이 함수로는 통과할 수 없으니 코드를 바꿔야 한다고 빠르게 결론을 내릴 수 있습니다.