시간 복잡도 (Time Complexity)
평균을 구하는 문제를 두 종류의 자료구조(변수, 배열)를 사용해서 각각에 맞는 알고리즘으로 해결할 수 있다. 변수는 변수에 맞는 알고리즘, 배열은 배열에 맞는 알고리즘을 이용해서 해결한다. 심지어 같은 자료구조를 쓰더라도 알고리즘은 여러 가지가 될 수 있다는 것도 확인할 수 있다. 예를 들어, 배열의 평균을 구하는 알고리즘이 여러 개있다. 이왕 문제를 해결할 때 더 좋은 알고리즘을 사용하는 것은 당연한 이야기히다. 그렇다면 “더 좋은 알고르짐”이란 무엇일까를 고민할때 이는 사용자의 요구에 따라 달라질 수 있다
- 메모리 사용량: 메모리를 더 작게 사용하고 싶은 사용자라면 메모리를 적게 사용하는 알고리즘이 좋은 알고리즘이다 (이는 공간 복잡도(Space Complexity)와 관련이 있다)
- 실행 속도: 어떤 사용자는 실행 속도가 더 빠른 알고리즘을 원할 것이다. 이 때는 메모리를 더 많이 사용하더라도 속도가 더 빠른 알고리즘이 성능이 더 좋은 알고리즘이다
이렇게 사용자에 따라 중요하게 여기는 것이 다르지만, 일반적으로 컴퓨터 과학에서 알고리즘의 성능을 평가할 때는 알고리즘의 샐힝 속도를 가장 중요한 척도로 사용한다.
이를 시간 복잡도라고 한다. 시간 복잡도란 특정 알고리즘이 어떤 문제를 해결하는 데 필요한 연산의 횟수를 입력 크기의 함수로 나타낸 것이다. 즉, 입력 데이터의 크기가 증가함에 따라 알고리즘의 실행 시간이 얼마나 증가하는지를 나타낸다.
하지만 시간을 실제 측정하여 알고리즘을 평가하기에는 현실적으로 어려움이 많다
- 컴퓨터 사양의 차이: 사용자마다 컴퓨터 사양(CPU, 메모리 등)이 다르기 때문이다. 같은 알고리즘이더라도 성능이 좋지 않은 컴퓨터와 성느잉 좋은 컴퓨터의 실행 시간은 다르다
- 프로그래밍 언어 및 컴파일러의 차이: 어떤 언어로 작성되었는지, 어떤 컴파일러나 인터프리터를 사용하는지에 따라 실제 실행 시간이 달라질 수 있다
- 환경적 요인: 현재 컴퓨터에서 실행 중인 다른 프로세스 등 환경적인 요인도 영향을 미친다
따라서 알고리즘을 평가할 때는 실제 시간을 측정하는 방식이 아닌, 코드에서 성능에 많은 영향을 미치는 부분, 즉 연산의 횟수를 예측하는 방식을 사용한다. 그렇다면 코드에서 성능에 많은 영향을 미치는 부분은 어떤 것일까? 그것은 주로 반복문(for, while 루프, 재귀 호출 등)과 입력 크기에 비례하여 실행되는 연산이다. 반복문이 여러 번 반복될수록, 또는 입력 크기에 비례하는 연산이 많아질수록 실행 시간이 길어진다. 따라서 특정 알고리즘의 성능을 평가할 때는 해당 알고리즘의 핵심 연산이 몇 번 수행되는지를 보고 성능을 예측한다
시간 복잡도 예시 – 선형 검색(Linear Search)(
Q. 주어진 배열에서 5를 찾으시오. int[] arr = {1, 3, 5, 7, 9};
5를 찾기 위해서 간단한 알고리즘을 떠울릴 수 있다. 배열의 0번 인덱스부터 끝까지 순회하며 5인지 아닌지를 검사하는 것이다
public class Solution {
public static int findFive(int[] arr) {
for (int i = 0; i < arr.length; i++) { // 배열의 길이만큼 반복
if (arr[i] == 5) { // 각 원소를 5와 비교
System.out.println("arr[" + i + "]은 5입니다. 문제를 해결했습니다.");
return i; // 5를 찾으면 해당 인덱스를 반환
}
System.out.println("arr[" + i + "]은 5가 아닙니다.");
}
System.out.println("배열에서 5를 찾지 못했습니다.");
return -1; // 5를 찾지 못한 경우 -1 반환
}
public static void main(String[] args) {
int[] arr = {1, 3, 5, 7, 9};
findFive(arr);
}
}
이 코드를 실행하면 다음과 같은 출력을 볼 수 있다
arr[0]은 5가 아닙니다.
arr[1]은 5가 아닙니다.
arr[2]은 5입니다. 문제를 해결했습니다.
길이가 5인 배열에서 세 번만에 원하는 데이터를 찾았다. 그렇다면 사용한 알고리즘의 성능을 어떤 식으로든 표현할 수 있어야 한다. 하지만 찾는 데이터가 배열의 어디에 있는지에 따라서 성능은 천차만별이다
- 최선의 경우(Best Case): 찾는 데이터가 배열의 첫 번째 원소에 있다면, 한 번의 비교(arr[0] == 5)만으로 찾을 수 있다
- 최악의 경우(Worst Case): 찾는 데이터가 배열의 마지막 원소에 있거나, 배열에 아에 존재하지 않는다면, 배열의 길이(n) 만큼 순회하고 비교해야 찾거나 못 찾았다고 판단할 수 있다
- 평균의 경우(Average Case): 데이터가 배열의 중간 인덱스에 있다면, 대략 n/2번 정도 비교해서 찾을 수 있다
이렇듯 경우에 따라서 성능이 많이 잘라질 수 있기 때문에, 경우를 나누어서 성능을 평가한다
- 최선의 경우: 빅-오메가 (Big-Ω, Omega Notation)로 표현한다
- 최악의 경우: 빅-오 (Big-O, O Notation)로 표현한다
- 평균의 경우: 빅-세타 (Big-Θ, Theta Notation)로 표현한다
이 중에서 빅-O(Big-O) 표기법을 가장 많이 사용한다. 그 이유는 알고리즘의 성능을 평가할 때는 보통 “최악의 상황에서도 이 정도의 성능은 보장한다”는 의미로 최악의 경우를 기준으로 삼기 때문이다. 이는 시스템 안정성과 성능 보장을 위해 중요한 지표가 된다
조금 전에 배열에서 원하는 데이터를 찾는 알고리즘(선형 검색)의 성능을 빅-O 표기법으로 평가해보자. 배열의 첫 번째 원소부터 마지막 원소까지 비교하면서 찾으므로, 최악의 경우는 찾는 데이터가 배열의 가장 마지막에 있거나 배열에 없는 경우이다. 만약 입력의 크기, 즉 배열의 데이터가 n개 있다면 이 알고리즘은 최악의 경우 n 번의 비교 연상을 수행해야 한다. 이를 빅-O 표기법으로 O(n)으로 표현한다
O(n)은 입력 데이터 수(n)에 비례하여 계산량이 증가한다는 의미이다. 1차 함수의 모양처럼, n에 1을 넣으면 연산량이 1에 비례하고, n에 5를 넣으면 연산량은 5에 비례하게 된다. 데이터가 많아질수록 그의 비례해서 계산량이 많아진다는 것을 의미힌다. 이러한 이유로 O(n) 알고리즘을 선형 시간 알고리즘(Linear Time Algorithm)이라고 부른다
다양한 시간 복잡도 유형 (성능이 좋은 순서)
O(1) – 상수 시간 (Constant Time)
- 입력의 크기에 상관없이 항상 일정한 시간이 걸린다. 계산량이 꼭 한 번일 필요는 없다. 문제를 해결하는 데 입력의 크기에 상관없이 100번의 계산이 걸린다고 하더라도, n에 대한 의존성이 없으므로 상수 시간으로 간주하여 O(1)으로 표기한다
- 예: 배열에서 특정 인덱스의 원소에 접근하기 (arr[5])
O(log n) – 로그 시간 (Logarithmic Time)
- 입력 크기가 커질수록 실행 시간 증가율이 매우 낮은 알고리즘이다. 주로 이진 검색(Binary Search)과 같이 데이터를 절반씩 줄여나가며 탐색하는 경우에 나타난다.
- 예: 정렬된 배열에서 이진 검색으로 특정 값 찾기
O(n) – 선형 시간 (Linear Time)
- 입력 크기에 비례하여 실행 시간이 증가한다
- 예: 배열의 모든 원소를 순회하며 합계 계산, 선형 검색
O(n log n) – 선형 로그 시간 (Linearithmic Time)
- O(n)보다 느리지만 O(n²)보다는 빠르다. 효율적인 정렬 알고리즘(병합 정렬, 퀵 정렬 등)에서 많이 나타난다
- 예: 효율적인 정렬 알고리즘(Merge Sort, Quick Sort)
O(n²) – 이차 시간 (Quadratic Time)
- 입력 크기의 제곱에 비례하여 실행 시간이 증가한다 중첩된 반복문(nested loop)에서 자주 나타난다. n이 조금만 커져도 실행 시간이 크게 늘어난다
- 예: 버블 정렬(Bubble Sort), 선택 정렬(Selection Sort), 삽입 정렬(Insertion Sort)과 같은 비효율적인 정렬 알고리즘
O(2ⁿ) – 지수 시간 (Exponential Time)
- 입력 크기가 조금만 커져도 실행 시간이 기하급수적으로 증가한다. 매우 비효율적인 알고리즘으로, 보톡 작은 입력에만 사용 가능하거나, 더 효율적인 방법을 찾아냐 한다
- 예: 피보나치 수열을 재귀로 단순 구현하는 경우
O(n!) – 팩토리얼 시간 (Factorial Time)
- 입력 크기가 조금만 커져도 실행 시간이 폭발적으로 증가하는 가장 비효율적인 알고리즘 중 하나이다. n=10만 되어도 엄청난 시간이 소요된다
- 예: 외판원 문제(Traveling Salesman Problem)의 브루트 포스(Brute-force) 해결법
빅-O 표기법의 특징 및 규칙
빅-O 표기법의 특징은 입력이 늘어날 때 계산량이 늘어나느 척도(성장률)를 나타내기 위한 것이다
- 최고차항만 표기: 함수의 최고차항(가장 큰 영항을 미치는 항)만 표기한다
- 예: n² + 2n + 100의 성능을 보이는 알고리즘이 있다면, n이 커질수록 n²이 2n이나 100보다 훨씬 빠르게 증가하므로, 2n + 100은 버리고 O(n²)으로 표기한다
- 상수 계수 제거: 상수 계수는 큰 의미가 없으므로 제거한다
- 예: 3n² + 100n 이라면 가장 큰 항은 3n²이다. 여기서 3은 제거사여 O(n²)으로 표기한다. 5n 이라면 O(n)이 된다
이러한 규칙은 빅-O 표기법이 정확한 연산 횟수를 나타내는 것이 아니라, 알고리즘의 실행 시간이 입력 크기에 따라 얼마나 빠르게 증가하는지(점근적 상한)을 보여주기 위함이다. 즉, 입력 n이 무한히 커질 때 어떤 함수에 수렴하는지를 나타내는 것이다