시간복잡도란 무엇인가? 왜 우리는 이걸 신경 써야 할까

1. 같은 문제, 다른 결과

코딩 테스트 문제를 풀다 보면 이런 경험을 한 적이 있다.

분명히 정답 로직인데,
예제도 잘 통과하고 로컬 테스트도 문제없다.
그런데 제출하자마자 시간 초과가 뜬다.

 

코드는 틀리지 않았는데 왜 실패했을까?
이때 등장하는 개념이 바로 **시간복잡도(Time Complexity)**다.

---

2. 입력 크기가 커지면 문제가 생긴다

대부분의 문제는 입력 데이터가 작을 때는 잘 동작한다.
하지만 입력이 커질수록 코드의 성능 차이는 극단적으로 벌어진다.

예를 들어,

• 데이터가 10개일 때는 10번 반복해도, 100번 반복해도 큰 차이가 없다
• 하지만 데이터가 100,000개라면?
  • 100,000번 반복하는 코드는 여전히 빠르다
  • 10,000,000,000번 반복하는 코드는 현실적으로 실행이 불가능하다

👉 문제는 ‘지금’이 아니라 ‘커졌을 때’ 발생한다.

시간복잡도는 바로 이 입력이 커질 때 코드가 얼마나 느려지는지를 판단하기 위한 기준이다.

---

3. 시간복잡도는 “연산 횟수”를 보는 개념이다

시간복잡도는 실제 실행 시간(초, 밀리초)을 계산하지 않는다.
대신 입력 크기에 따라 연산 횟수가 어떻게 증가하는지를 본다.

예를 들어,

• 반복문이 한 번 도는 코드
• 반복문이 두 번 중첩된 코드

이 둘은 입력이 커질수록 연산 횟수 차이가 기하급수적으로 벌어진다.

중요한 점은:

• 컴퓨터 성능
• 프로그래밍 언어
• 실행 환경

이런 것들과 무관하게 알고리즘 자체의 성장 속도를 비교한다는 것이다.

---

4. Big-O 표기법이란?

시간복잡도는 보통 Big-O 표기법으로 표현한다.

Big-O 표기법은 다음 질문에 답하기 위한 도구다.

“입력 크기 n이 커질수록
이 알고리즘의 연산량은 어떤 형태로 증가하는가?”

 

여기서 중요한 규칙이 있다.

Big-O의 핵심 규칙

• 가장 큰 영향력을 가지는 항만 남긴다
• 상수는 무시한다

예를 들어:

• O(n + 10) → O(n)
• O(2n) → O(n)
• O(n² + n) → O(n²)

이유는 단순하다.
입력이 커질수록 지배적인 항 하나만 의미를 가지기 때문이다.

---

5. 대표적인 시간복잡도 유형

O(1) – 상수 시간

입력 크기와 무관하게 항상 같은 시간에 실행된다.
배열의 특정 인덱스 접근이 대표적인 예다.

O(n) – 선형 시간

입력 크기 n에 비례해서 연산 횟수가 증가한다.
한 번의 반복문이 이에 해당한다.

O(n²) – 제곱 시간

이중 반복문 구조에서 자주 등장한다.
입력이 조금만 커져도 급격히 느려진다.

O(log n) – 로그 시간

입력을 절반씩 줄여나가는 알고리즘에서 나타난다.
이진 탐색이 대표적인 예다.

---

6. 그래서 시간복잡도가 왜 중요할까?

시간복잡도는 단순한 이론이 아니다.

• 코딩 테스트에서는 시간 초과 = 오답
• 실무에서는
  • 응답 속도 저하
  • 서버 비용 증가
  • 사용자 경험 악화

로 이어진다.

같은 기능을 구현하더라도
어떤 알고리즘을 선택하느냐에 따라 결과는 완전히 달라진다.

---

7. 마무리하며

시간복잡도는 코드를 “잘 짰는지” 판단하는 기준 중 하나다.
정답을 맞히는 것에서 끝나는 것이 아니라,
입력이 커져도 버틸 수 있는 코드인지를 고민하게 만든다.

앞으로 알고리즘 문제를 풀 때,
혹은 코드를 작성할 때
한 번쯤은 이렇게 질문해보자.

“이 코드는 입력이 100배 커져도 괜찮을까?”