코드를 실행하면 원하는 기능을 수행하고 종료되기까지 어느 정도의 시간이 걸립니다. 짧고 간단한 코드라면 금방 끝나겠지만, 복잡하고 어려운 코드라면 시간이 좀 더 걸릴 겁니다. 만약 지금에 만족하지 못하고 더 빠르게 실행되는 코드를 짜고 싶다면 어떻게 해야 할까요? 이를 대답하려면 어느 알고리즘이 더 나은지 비교할 수 있는 기준이 필요합니다.

문제 해결에 필요한 입력값과 문제를 해결하는 프로그램이 주어졌을 때, 프로그램이 입력값을 받아 동작하고 결과를 만들어내는 데 걸리는 정도를 복잡도라고 합니다. 그중 얼마나 오래 걸리는지는 시간 복잡도라고 하고, 얼마나 많은 메모리를 사용하는지는 공간 복잡도라고 합니다.

코딩 테스트에서는 두 복잡도에 대한 조건이 함께 제시됩니다. 문제에 맞는 코드를 짜는 것은 물론, 이 코드가 몇 초/몇 MB 이내에 실행되어야 하는지도 중요하다는 의미입니다. 따라서 가장 먼저 제시된 제한 시간과 메모리 사용량을 확인한 후 조건에 맞게 실행되도록 문제를 풀어야 합니다.

문제나 언어마다 주어진 시간이 다르지만 프로그래머스는 특별히 언급하지 않으면 제한 시간이 10초입니다. 하지만 10초가 어느 정도인지 감이 오지 않죠? 이를 이해하려면 먼저 우리가 짠 코드를 어떻게 시간으로 나타낼 수 있는지에 대해 알 필요가 있습니다. 몇 가지 시간 복잡도에 대해 알아봅시다.