시 공간 복잡도
먼저, 간단하게 말하자면 공간 복잡도는 코드가 실행됨에 있어서 얼마나 공간이 많이 차지하게 되는가를 따지는 방법이고,
시간 복잡도는 코드가 실행됨에 있어서 얼마나 시간이 오래 걸리냐의 방법이다.
복잡도를 나타내는 표기법은 크게 세가지로 구성되어있다.
- O (Big-O)
- Ω (Omega)
- Θ (Theta)
가장 먼저 Big-O는 점근적 상한을 의미하는데, 최악의 상황을 고려하여 만들어진 것이다.
그 다음 Omega는 점근적 하한을 의미하는것으로, 최소한 이정도는 걸릴것이라는 보장을 나타낸다.
마지막 Theta는 점근적 상한과 점근적 하한의 정확한 값을 나타낸다.
이 3가지의 경우중 Theta를 사용하는것이 가장 좋을 것 같지만 계산이 너무 복잡해지기 때문에 잘 사용하지 않는다. 그리고 우리가 코드를 작성하여 서비스를 하는경우 최악의 상황을 더 중요하게 생각하기 때문에 대부분의 경우 Bic-O 표기법을 사용한다.
시간 복잡도
시간복잡도는 코드가 실행됨에 따라 다양한 크기의 입력이 주어졌을때 해당 코드가 얼마나 시간이 걸리는지를 나타내는 방법이다.
예시 코드로 살펴보자
public int time(int n) {
int num = n; // 1
num++; // 1
int result = 0; // 1
for(int i=0; i<n; i++) { // i=0 : 1, result + n : n, i++ : n, i<n : 1 >> 2n + 2
result += n;
}
// 총 시간 : 2n + 5
return result;
}이 코드를 살펴보면,
int num = n; // 1
num++; // 1
int result = 0; // 1어떠한 입력 n이 들어와도 1번의 계산만을 하는 경우 상수 시간이 걸린다.
이 3줄의 코드는 총 3 정도의 시간이 걸린다 할 수 있다.
반면
for(int i=0; i<n; i++) { // i=0 : 1, result + n : n, i++ : n, i<n : 1 >> 2n + 2
result += n;
}이러한 반복문의 경우 n의 입력이 들어왔을때
int i=0 에서 1 정도의 시간,
i<n 비교문에서 1 정도의 시간,
result += n; 을 n의 크기만큼 하기 때문에 n 정도의 시간,
i++을 n의 크기 만큼 사용하기 때문에 n 정도의 시간이 걸린다.
이 반복문의 경우 2n+2 정도의 시간이 걸린다
따라서 총 걸리는 시간은 (상수시간 3) + (반복문 시간 2n + 2)
총합 2n + 3의 선형 시간 복잡도가 나온다
하지만 계산 복잡도의 경우 O(2n+3)이라 표현하지 않는다.
n이 매우 커졌을때 상수항들은 상대적으로 무시될 정도로 작기 때문에 무시하게 되어 결국 O(n) 만 남게된다.
공간 복잡도
공간 복잡도는 크게 고정 공간과 임시공간 메모리의 크기를 나타낸다
여기서 말하는 고정공간은 코드를 작성할때 우리가 미리 선언한 배열의 길이라 생각하면 편하고, 임시공간은 공간이 한정적이지 않은 가변길이의 vector나 ArrayList 등을 생각하면 쉽다.
public void prac(int n) {
//고정길이
int[] arr1 = new int[10];
for(int i=0; i<10; i++) {
arr1[i] = i;
}
//가변길이
ArrayList<Integer> arr2 = new ArrayList<Integer>();
for(int i=0; i<n; i++) {
arr2.add(n);
}
}이 메소드를 보면 고정길이 배열의 경우 10으로 공간이 결정되어있다.
이 배열은 어떠한 입력 n이 들어와도 크기는 바뀌지 않는다.
따라서 크기는 10으로 고정되어있기 때문에 상수로 표현하며,
표현식은 O(1)로 표현할 수 있다.
반면 가변길이 ArrayList의 경우 n이 입력되는 크기에 따라 배열의 크기가 변한다.
즉, 크기가 n이 되기 때문에 공간 복잡도를 나타내면 O(n)이라 할 수 있다.
복잡도 계산 방법
복잡도 계산 방법은 크게 어렵지 않다.
일반적으로 입력되는 데이터에 영향을 받아 계산이 몇번 되는지에 따라 복잡도가 바뀐다.
앞서 설명했듯
public void met1(int n){
int a = 0;
}
public void met2(int n){
int a = n;
}
public void met3(int n){
int a = 1;
int b = 1;
int c = a+b;
}met1 메소드는 n 값이 무엇이든 a는 전혀 영향을 받지 않기 때문에 상수 시간복잡도 O(1)이다.
그렇다면 met2 메소드는 입력되는 n에 변수 a가 영향을 받기 때문에 O(n)인가?
아니다. 결국 대입은 1번이고, 결국 계산은 1번이 실행되기 때문에 정답은 met1과 동일하게 O(1)이다.
met3는 계산이 3번인데 O(3)으로 표현하지 않는 이유는 최대의 데이터가 입력되는 경우 상수 시간은 고려되지 않기 때문에 O(1)로 표현한다.
public void met4(int n){
int result = 0;
for(int i=0; i<n; i++){
result += 1;
}
}
public void met5(int n){
int result = 0;
for(int i=0; i<n; i++){
for(int j=0; j<n; j++) {
result += 1;
}
}
}
public void met6(int n){
int result = 0;
for(int i=0; i<n; i++){
result += 1;
}
for(int i=0; i<n; i++){
result += 1;
}
}met4 메소드 경우 앞서 간단하게 설명했듯 입력된 n의 크기만큼 계산이 반복되기 때문에 시간 복잡도는 O(n)이 된다.
met5 메소드는 반복문이 중첩된 메소드이다. 입력된 값 n 만큼의 계산을 n번 반복하기 때문에 n^2이 된다. 따라서 시간복잡도는 O(n^2)이 된다.
그렇다면 met6 반복문은 어떨까.
입력된 값에 따라 반복문이 2개이기 때문에 met5 처럼 O(n^2) 인가?
정답은 아니다. 반복문이 중첩이 아니라 그냥 더해진것이기 때문에 2n 개의 계산이 이루어지고, 데이터가 커짐에 따라 상수항은 무시되어지기 때문에 met4와 동일하게 O(n)의 시간복잡도를 가지고 있다.
1. O(1)
- 입력값이 얼마나 되든 일정한 속도를 나타낸다
- 가장 효율적인 시간 복잡도를 가지고 있다.
2. O(log n)
- 상수 시간에 이어 두 번째로 효율적인 시간 복잡도이다.
- 입력에 대해 로그 시간으로 실행된다.
- 매 반복마다 탐색 범위를 1/2로 감소 시키는 이진 탐색 알고리즘이 대표적이다
O(n)
- O(log n) 다음으로 효율적인 시간복잡도이다.
- 선형시간 복잡도로 할 수 있으며, 입력된 데이터 만큼 동일한 비율로 늘어간다
- 처음부터 순차적으로 탐색하는 순차 탐색 알고리즘이 대표적이다
O(n log n)
- O(log n) 을 n 번 반복하는 알고리즘에 대한 복잡도이다.
- 대표적으로 배열을 2개로 나누고 그 안에서 정렬을 진행하여 병합 정렬 알고리즘을 예로 들 수 있다
O(n^2)
- 일반적으로 중첩 반복문에서 나타나는 시간 복잡도이다.
- 입력 값에 따라 가파르게 증폭된다.
