⭐️ 시간복잡도란?
시간복잡도란 특정 함수나 알고리즘이 얼마나 효율적인지, 특히 입력 크기가 커질 때 성능이 어떻게 변하는지 예측하는데 중요한 요소이다. 실제로 시간을 측정하는 것이 아니라, 입력 크기(N)에 비례하여 연산의 개수가 얼마나 증가하는지를 대략적으로 파악하는 것을 말한다.
✅ 빅-O 표기법 이해하기
빅-O 표기법은 알고리즘의 최악의 경우(Worst-case scenario) 시간 복잡도를 나타낸다.
상수항이나 중요하지 않은 계수는 무시하고, 입력 크기 N이 커질 때 가장 큰 영향을 미치는 향만 남겨서 표기하는 방식이다.
주요 빅-O 표기법 종류
- O(1) 상수 시간(Constant Time)
- 입력 크기와 관계없이 연산 횟수가 일정
- ex) 배열에서 특정 인덱스의 요소에 접근 =
arr[0]
- O(log N) 로그 시간(Logarithmic Time)
- 입력 크기가 커져도 연산 횟수가 매우 조금 증가.
- 주로 문제를 절반씩 줄여나가는 알고리즘에서 많이 보임.
- ex) 이진 탐색(Binary Search)
- O(N) 선형 시간(Linear Time)
- 입력 크기에 비례하여 연산 횟수가 증가
- ex) 배열의 모든 요소를 한 번씩 순회 =
for i in arr { ... }
- O(N log N) 선형 로그 시간(Linearithmic Time)
- O(N)보다 느리지만 O(N²)보다 훨씬 빠름.
- 정렬 알고리즘에서 흔히 볼 수 있음.
- ex) 퀵 정렬(Quick Sort), 병합 정렬(Merge Sort)
- O(N²) 2차 시간(Quadratic Time)
- 입력 크기의 제곱에 비례하여 연산 횟수가 증가.
- 중첩된 루프에서 흔히 발생.
- ex) 버블 정렬(Bubble Sort), 삽입 정렬(Insertion Sort), 선택 정렬(Selection Sort)
- O(2ᴺ) 지수 시간(Exponential Time)
- 입력 크기가 조금만 커져도 연산 횟수가 기하급수적으로 증가.
- 매우 비효율적인 알고리즘
- ex) 재귀적인 피보나치 수열(Memoization 없는 경우)
- O(N!) 팩토리얼 시간(Factorial Time)
- 입력 크기가 커질수록 연산횟수가 엄청나게 증가.
- 현실적으로 작은 N에서만 사용 가능.
- ex) 외판원 문제(Traveling Salesman Problem)의 브루트 포스 방식
✔️ Swift 코드에서 시간 복잡도 계산하는 방법
Swift 코드에서 시간 복잡도를 따져볼 땐 다음 원칙들을 적용한다.
1. 기본 연산은 O(1)
할당, 산술 연산, 특정 인덱스 접근 등 대부분의 기본 연산은 상수 시간(O(1))으로 간주한다.
func basicOperation(value: Int) -> Int {
let result = value * 2 + 5 // O(1)
return result
}2. 반복문(Loop)은 O(N) 또는 O(N * 내부 연산)
반복문은 입력 크기(N)에 따라 반복되는 횟수가 결정되므로, 일반적으로 선형 시간 이상이 나온다.
// O(N)
func sumArray(arr: [Int]) -> Int {
var sum = 0
for element in arr { // N번 반복
sum += element // O(1)
}
return sum
}
// O(N^2)
func printPairs(arr: [Int]) {
for i in arr { // N번 반복
for j in arr { // N번 반복
print("\(i), \(j)") // O(1)
}
}
}3. 중첩된 반복문은 곱셈
반복문 안에 또 다른 반복문이 있으면 각 반복문의 시간 복잡도를 곱한다.
for i(N번) 안에for j(N번) => O(N times N) = O(N²)for i(N번) 안에for j(M번) => O(N times M)
4. 재귀 함수는 호출 스택 깊이 또는 호출 횟수
재귀 함수의 시간 복잡도는 주로 재귀 호출의 깊이와 각 호출에서 수행되는 연산에 따라 결정된다.
// O(N) - N번 호출
func factorial(n: Int) -> Int {
if n <= 1 {
return 1
}
return n * factorial(n: n - 1)
}
// O(2^N) - Memoization 없는 경우
func fibonacci(n: Int) -> Int {
if n <= 1 {
return n
}
return fibonacci(n: n - 1) + fibonacci(n: n - 2)
}5. Collection 타입의 연산
Swift의 Array, Dictionary, Set 등 컬렉션 타입의 특정 연산은 내부 구현에 따라 시간 복잡도가 달라진다.
Array:- 인덱스로 접근:
arr[index]= O(1) - 맨 뒤에 추가:
arr.append(element)는 보통 O(1)이지만, 용량 재할당 시 O(N) - 맨 앞/중간에 삽입/삭제:
arr.insert(at:),arr.remove(at:)= O(N) - 요소 탐색:
arr.contains(element)는 O(N) (선형 탐색)
- 인덱스로 접근:
Dictionary,Set:- 삽입, 삭제, 검색: 평균적으로 O(1), 최악의 경우(해시 충돌 심화) O(N)
6. 가장 큰 영향을 미치는 향만 고려
알고리즘에 여러 부분의 시간 복잡도가 있을 때, 가장 큰 영향을 미치는 향(dominant term)만 남긴다.
func exampleComplexity(arr: [Int]) {
// Part 1: O(N^2)
for i in arr {
for j in arr {
print(i + j)
}
}
// Part 2: O(N)
for k in arr {
print(k)
}
}
// 전체 시간 복잡도는 O(N^2 + N) -> O(N^2)📌 결론
결론적으로, Swift에서 알고리즘의 시간 복잡도를 계산하는 핵심은 코드 내의 각 연산이 입력 크기 N에 비례하여 몇 번 수행되는지 분석하고, 가장 큰 영향을 미치는 항을 빅-O 표기법으로 나타내는 것이다.
앞으로는 알고리즘을 풀 때 이러한 점도 고려하여 풀며, 특히 반복문과 컬렉션 타입의 연산을 할 때 주의를 해야할 것 같다.
