2.1.3 입력 데이터 개수별 사용 가능한 시간 복잡도 알고리즘

이처럼 시간 복잡도는 프로그램 실행 시간을 결정짓는 중요한 요소이기에 코딩 테스트에서 코드를 작성할 때는 자신이 생각한 풀이의 시간 복잡도를 따져 보아야 합니다. 컴퓨터의 연산 속도는 굉장히 빠릅니다. 프로그램 실행 시간 1초라는 제한이 있을 때, 어느 정도 시간 복잡도이어야 시간 제한을 만족할 수 있을까요?

1초를 만족하는 정해진 시간 복잡도는 문제별로 다릅니다. 문제별로 주어지는 입력 데이터의 종류와 그 개수가 다르기 때문에 정해진 시간 복잡도는 있을 수 없습니다. 하지만 입력 조건에서 명시되어 있는 최악의 경우를 시간 복잡도에 대입해보았을 때 1억이 넘지 않는다면 실행 시간이 1초보다 빠른 충분히 효율적인 코드일 가능성이 높습니다.

예를 들어 문제에서 주어진 조건에 따라 N 값이 최대 1만이라고 가정한다면, 시간 복잡도 O(N logN)을 갖는 코드는 N을 대입했을 때 그 값이 약 13만으로 계산되기 때문에 충분히 효율적인 코드라고 할 수 있습니다. 하지만 작성한 코드가 시간 복잡도 O(N²)을 갖는다면 N을 대입했을 때 1억이 되기 때문에 시간 제한을 맞추지 못할 가능성이 매우 큽니다.

따라서 자신의 시간 복잡도에 문제의 제한 사항에 표기된 가장 큰 입력을 대입하여 계산했을 때 아무리 커도 1억을 넘기지 않아야 시간 제한에서 안전한 코드입니다.