알고리즘을 공부하면서 '시간 복잡도(Time Complexity)'라는 개념이 얼마나 중요한지 자주 마주하게 된다. 시간 복잡도는 알고리즘이 주어진 입력을 처리하는 데 걸리는 시간을 나타내는 개념으로, 이를 이해하면 알고리즘의 효율성을 평가하는 데 큰 도움이 된다. 이번에는 시간 복잡도가 무엇인지, 그리고 왜 중요한지에 대해 깊이 있게 공부해보자.
시간 복잡도란?
시간 복잡도는 알고리즘이 어떤 입력을 받았을 때, 그 입력을 처리하는 데 걸리는 시간을 나타낸다.
주로 입력 크기(input size)에 대한 함수로 표현되며, 입력이 커질수록 알고리즘이 얼마나 더 오래 걸리는지를 설명해준다.
시간 복잡도 표기법 - Big-O 표기법
시간 복잡도는 보통 Big-O 표기법을 사용해 표현한다. 이 표기법은 입력 크기에 따라 알고리즘의 실행 시간이 어떻게 변하는지, 가장 빠르게 증가하는 항만을 고려해서 나타낸다. 주로 사용되는 Big-O 표기법의 예시는 다음과 같다:
- O(1): 입력 크기와 상관없이 항상 일정한 시간이 걸림 (예: 배열의 첫 번째 요소 접근)
- O(log n): 입력 크기가 커질수록 시간이 느리게 증가함 (예: 이진 탐색)
- O(n): 입력 크기에 비례해서 시간이 증가함 (예: 단순 반복문)
- O(n^2): 입력 크기의 제곱에 비례해서 시간이 증가함 (예: 중첩 반복문)
시간 복잡도의 대표적인 예시들 (출처: 위키피디아)
시간 복잡도를 이해하기 위한 예시
예를 들어, 숫자 리스트에서 가장 큰 숫자를 찾는 알고리즘을 생각해보자. 리스트가 길어질수록 비교해야 할 숫자가 많아지기 때문에, 시간 복잡도는 리스트의 길이에 비례하게 된다.
function findMax(arr: Array): Int {
var max = arr[0]
for (i in 1 until arr.size) {
if (arr[i] > max) {
max = arr[i]
}
}
return max
}
위 코드에서 리스트의 길이가 n
이라면, 최대 n-1
번 비교를 해야 가장 큰 수를 찾을 수 있다. 그래서 이 알고리즘의 시간 복잡도는 O(n)이다.
시간 복잡도 계산 예시 - Kotlin으로 작성하기
다양한 시간 복잡도를 가진 알고리즘을 Kotlin 코드로 작성해보고, 그 시간 복잡도를 분석해보자.
1. O(1) - 상수 시간 복잡도
fun getFirstElement(arr: Array): Int {
return arr[0]
}
이 함수는 입력 배열의 첫 번째 요소를 반환한다. 배열의 크기와 상관없이 항상 동일한 시간에 실행되므로 시간 복잡도는 O(1)이다.
2. O(n) - 선형 시간 복잡도
fun printAllElements(arr: Array) {
for (element in arr) {
println(element)
}
}
이 함수는 배열의 모든 요소를 출력한다. 배열의 크기 n
에 비례하여 반복 횟수가 늘어나므로 시간 복잡도는 O(n)이다.
3. O(n^2) - 이차 시간 복잡도
fun printPairs(arr: Array) {
for (i in arr.indices) {
for (j in arr.indices) {
println("${arr[i]}, ${arr[j]}")
}
}
}
이 함수는 배열 내 모든 요소의 쌍을 출력한다. 두 개의 중첩된 반복문이 사용되었기 때문에, 시간 복잡도는 O(n^2)이다.
4. O(log n) - 로그 시간 복잡도
fun binarySearch(arr: Array, target: Int): Int? {
var left = 0
var right = arr.size - 1
while (left <= right) {
val mid = (left + right) / 2
when {
arr[mid] == target -> return mid
arr[mid] < target -> left = mid + 1
else -> right = mid - 1
}
}
return null
}
이 함수는 이진 탐색 알고리즘을 구현한 것이다. 배열이 정렬되어 있다는 가정 하에, 입력 크기가 절반으로 줄어들기 때문에 시간 복잡도는 O(log n)이다.
5. O(n log n) - 선형 로그 시간 복잡도
fun mergeSort(arr: Array): Array {
if (arr.size <= 1) return arr
val mid = arr.size / 2
val left = mergeSort(arr.sliceArray(0 until mid))
val right = mergeSort(arr.sliceArray(mid until arr.size))
return merge(left, right)
}
fun merge(left: Array, right: Array): Array {
var indexLeft = 0
var indexRight = 0
val newArray: ArrayList = ArrayList()
while (indexLeft < left.size && indexRight < right.size) {
if (left[indexLeft] <= right[indexRight]) {
newArray.add(left[indexLeft])
indexLeft++
} else {
newArray.add(right[indexRight])
indexRight++
}
}
newArray.addAll(left.slice(indexLeft until left.size))
newArray.addAll(right.slice(indexRight until right.size))
return newArray.toTypedArray()
}
이 함수는 병합 정렬 알고리즘을 구현한 것이다. 병합 정렬은 입력 크기를 반으로 나누고, 각 부분을 재귀적으로 정렬하여 합치는 과정이므로 시간 복잡도는 O(n log n)이다.
다양한 시간 복잡도를 가진 알고리즘을 직접 구현해보면서, 각각의 시간 복잡도가 어떻게 계산되는지 이해하는 것이 중요한 것 같다.
'Computer Science > Algorithms' 카테고리의 다른 글
알고리즘 공간복잡도 공부하기 (0) | 2024.09.14 |
---|---|
알고리즘 기초 : 분할정복, 병합정렬, 이진 탐색, 퀵 정렬 쉽게 이해하기 (0) | 2024.09.10 |