코딩 테스트 문제 중에는 프로그램 실행 시간이 특정 시간 미만이어야 한다는 조건이 있는 경우가 있습니다. 일반적으로 이 시간은 1초를 기준으로 하며, 문제에서 주어지는 모든 형태의 입력을 처리하는 데 프로그램이 1초 이상 걸리면 안 된다는 의미입니다. 시간 제한이 있는 문제에서 실행 시간이 해당 제한 시간을 넘어간다면 시간 초과(TimeOut, TO)가 발생하여 오답으로 처리됩니다.

우리가 작성하는 코드가 문제에서 요구하는 만큼 효율적인지 알려면 어떻게 해야 할까요? 코드의 실행 시간을 측정하는 가장 쉬운 방법은 직접 예시 입력을 넣어 프로그램을 실행해보는 것입니다. 하지만 효율성을 측정하는 문제의 경우 대부분 입력 크기가 매우 큽니다. 1만 개의 입력을 받는 문제를 풀 때 코드가 효율적인지 측정하기 위해 모든 입력을 직접 넣을 수는 없습니다.

이때는 우리가 작성하는 코드의 실행 시간이 입력 데이터의 크기와 어떤 상관관계가 있는지 파악해서 그 효율성을 계산합니다. 이렇게 코드 혹은 알고리즘의 실행 시간과 데이터의 상관관계를 시간 복잡도라고 합니다.

시간 복잡도는 코딩 테스트에서 매우 중요한 개념으로, 이를 모르면 코딩 테스트에서 요구하는 효율적인 코드를 작성할 수 없습니다. 이 장에서는 시간 복잡도와 그 계산법을 알아봅니다.