알고리즘 기초 - 시간복잡도

---

시간복잡도?

---

정의 :

시간복잡도(Time Complexity)란, 어떤 알고리즘이 실행될 때 걸리는 연산 횟수를 입력의 크기 nnn에 따라 표현한 것을 말한다. 이는 실제 실행 시간을 직접 측정하는 것이 아니라, 알고리즘의 성능을 수학적으로 예측하고 비교하기 위한 도구이다.

보통 빅오(Big-O) 표기법을 사용해서 나타낸다.

 

왜 중요할까? 

알고리즘 문제를 풀 때 단순히 정답이 맞는 것만으로는 부족할 때가 있다.
예를 들어, 입력이 10개일 때는 1초도 안 걸리지만, 입력이 100만 개라면 같은 알고리즘이라도 몇 분이 걸릴 수도 있다.
이때, “내가 작성한 코드가 입력이 커졌을 때도 빠르게 동작할까?”를 판단하는 기준이 바로 시간복잡도다.

 

 

---

빅오 표기법

---

 

알고리즘의 실행 시간을 입력 크기 n이 무한히 커질 때의 성장률로 표현한다.

 

표기법	이름	예시	설명
O(1)	상수 시간	해시 테이블 조회	입력 크기와 상관없이 항상 일정한 시간 소요
O(logn)	로그 시간	이분 탐색	입력 크기가 커져도 조금씩만 증가
O(n)	선형 시간	배열 전체 탐색	입력 크기에 비례해서 실행 시간 증가
O(n log n)	로그 선형 시간	퀵 정렬, 머지 정렬	효율적인 정렬 알고리즘
O(n**2)	제곱 시간	버블 정렬	중첩 반복문에서 자주 발생
O(2**n)	지수 시간	부분집합 탐색	입력 크기 조금만 커져도 매우 느려짐
O(n!)	팩토리얼 시간	순열 탐색	가장 느린 경우, 현실적으로 불가능

 

 

입력 크기 nnn이 커질 때 빠른 순서대로 정리하면:

 

O(1) < O(logn) < O(n) < O(nlogn) < O(n2) < O(2n) < O(n!)

 

O(n) 예시

# O(n) 예시
arr = [1, 2, 3, 4, 5]
for x in arr:
    print(x)   # n번 실행됨

 

 

O(n**2) 예시

# O(n^2) 예시
arr = [1, 2, 3, 4, 5]
for i in arr:
    for j in arr:
        print(i, j)   # n * n번 실행됨

 

 

---

마무리

---

시간복잡도는 단순히 “수학”이 아니라, 코드를 효율적으로 작성하기 위한 필수 도구다.
앞으로 알고리즘을 공부하면서 문제를 풀 때마다 “내 풀이의 시간복잡도는 얼마일까?”를 습관처럼 따져본다면, 점점 더 좋은 코드를 작성할 수 있을 것이다