[Rn] 시간 복잡도 기본 (Time Complexity Basic) - Part 1

목차

1. 시간 복잡도란?
2. 시간 복잡도를 사용하는 이유

이 글과 연관된 글

• 시간 복잡도 기본 (Time Complexity Basic) - Part 2
• 시간 복잡도 기본 (Time Complexity Basic) - Part 3
• 시간 복잡도 기본 (Time Complexity Basic) - Part 4

---

시간 복잡도란?

시간 복잡도는 작성한 코드가 실행되는 데 걸리는 시간을 예측할 수 있는 계산식입니다.

시간 복잡도를 사용하는 이유

시간 복잡도를 계산하면 작성한 코드가 의도한 제한 시간 내에 실행될 수 있는지를 코드를 작성하지 않고도 예측할 수 있습니다.
물론 시간을 정확하게 계산할 수는 없지만, 비슷한 수치는 예측할 수 있습니다.

예를 들어, 당신은 특정 문제를 30초(코드가 30초 안에 실행을 마쳐야 한다는 의미입니다.) 안에 해결하는 코드를 작성해야 합니다.

시간 복잡도를 계산하지 않았다면 다음과 같은 프로세스로 문제를 해결하게 됩니다.

1. 문제를 해결할 수 있는 알고리즘을 구상합니다.
2. 구상한 알고리즘을 코드로 작성합니다.
3. 작성한 코드를 실행하고 실행 시간을 측정합니다.
4. 실행 시간이 30초 이내인지 확인합니다.
5. 만약 30초 이내가 아니라면 1번부터 다시 반복합니다.

1~5를 계속 반복하면서 코드를 작성해야 합니다. 물론 운이 좋다면 한 번에 프로세스를 마무리할 수도 있습니다. 하지만 어려운 문제를 풀다 보면 1~5를 여러 번 반복해야 할 수도 있습니다.

하지만, 시간 복잡도를 계산하면 다음과 같은 프로세스로 문제를 해결하게 됩니다.

1. 문제를 해결할 수 있는 알고리즘을 구상합니다.
2. 해당 알고리즘의 시간 복잡도를 계산합니다.
3. 시간 복잡도에 문제 제한 사항을 대입한 뒤, 30초 이내에 실행될 수 있는지 확인합니다.
4. 만약 30초 이내가 아니라면 1번부터 다시 반복합니다.
5. 만약 30초 이내라면 코드를 작성합니다.
6. 코드를 작성합니다.

물론 시간 복잡도는 코드가 실행되는 시간을 일반화해서 계산하기 때문에 예상했던 시간보다 느리거나 빠를 수 있습니다. 따라서 작성한 코드가 항상 30초 이내에 실행될 수 있는 것은 아닙니다.
하지만 시간 복잡도를 계산하면 1~6을 반복하는 횟수를 획기적으로 줄일 수 있습니다.