1. 시간복잡도
시간복잡도란?
입력값과 연산 수행 시간의 상관관계를 나타내는 척도를 시간 복잡도라고 한다.
Big-O 표기법
같은 알고리즘을 가지고 테스트를 하더라도 입력 값이 달라짐에 따라 수행 시간은 매우 짧아질 수도, 매우 길어질 수도 있다.
| 2 | 1 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|---|
예를 들어 10개의 배열에 위처럼 숫자가 들어가 있고 이 숫자를 오름차순으로 정렬하려면 '2'와 '1'만 바꿔주면 된다. 수행 시간이 아주 짧을 것이다.
| 10 | 9 | 8 | 7 | 6 | 5 | 4 | 3 | 2 | 1 |
|---|
하지만 만약 숫자가 이렇게 들어가 있었다면 수행 시간이 더 오래 걸릴 것이다.
시간 복잡도는 보통 이런 최악의 상황일 때 걸리는 시간을 이용해 나타낸다.
그리고 이걸 Big-O 표기법이라고 한다.
자료의 수에 따른 실행시간 변화
for(int i=0; i<n; i++) {
System.out.println(n);
}위 코드는 n번을 반복하면서 값을 출력하는 예제이다.
즉, 자료의 수는 n개이며 Big-O 표기법에 따라 O(n)이라고 나타낼 수 있다.
자료의 수가 증가함에 따라 소요되는 처리시간 증가율을 그래프로 나타낸 것이다.
빨간색 영역에 가까워질수록 수행 시간이 굉장히 오래 걸리는 알고리즘이라 할 수 있고
초록색에 가까워질수록 수행 시간이 짧은 알고리즘이라 할 수 있다.
2. 예제
O(1)
if(n%2 == 0) {
System.out.println("짝수");
} else {
System.out.println("홀수");
}위 예제는 입력한 n이 짝수면 한 단계에 걸쳐 수행이 완료되었을 거고 홀수면 두 단계에 걸쳐 수행이 완료되었을 것이다.
하지만 우리는 이걸 O(1), O(2) 등으로 나누지 않고 전부 O(1)으로 나타낸다.
O(n)
for(int i=0; i<n; i++) {
System.out.println(n);
}반복문을 이용해 n번 반복한다면 이는 Big-O 표기법으로 O(n)이라 나타낼 수 있다.
n의 값에 따라 처리수도 1:1 비례해서 늘어난다.
O(n²)
for(int i=0; i<n; i++) {
for(int j=0; j<n; j++) {
System.out.println(n * j);
}
}반복문이 두 번 겹쳐져 있는 이중 반복문의 경우는 O(n²)으로 나타낼 수 있다.
O(n³)
for(int i=0; i<n; i++) {
for(int j=0; j<n; j++) {
for(int k=0; k<n; k++) {
System.out.println(n * j + k);
}
}
}O(nm)
for(int i=0; i<n; i++) {
for(int j=0; j<m; j++) {
System.out.println(n * m);
}
}얼핏 보면 O(n³) 의 예제와 같은 이중 포문 같지만 엄연히 다르다. n번 반복하는 반복문을 두 번 중첩시킨 것이 아니라
n번 반복문과 m번 반복문을 중첩시켰다.
O(2ⁿ)
public static int pibo(int n) {
if (n == 0) return 0;
else if (n == 1) return 1;
return pibo(n - 1) + pibo(n - 2);
}위 코드는 피보나치 수열을 구현한 것이다. pibo(n)을 호출하면 pibo(n-1)과 pibo(n-2)가 호출된다.
그리고 이 호출 작업은 총 n번 반복되기 때문에 이를 Big-O 표기법으로 나타내면 O(2ⁿ)이 된다.
O(logN)
public static int binarySeacrh(int[] num, int target, int low, int high) {
int mid = (low + high) / 2;
if(target == num[mid]) return mid;
else if(target < num[mid]) return binarySeacrh(num, target, low, mid-1);
else return binarySeacrh(num, target, mid+1, high);
}위 코드는 이진 탐색 기법을 코드로 구현한 것이다.
탐색을 해나갈수록 탐색해야 할 데이터의 개수가 절반으로 나누어지기 때문에
이를 Big-O 표기법으로 나타내면 O(logN)이 된다.
3. etc
상수항 무시
if(n%2 == 0) {
System.out.println("짝수");
} else {
System.out.println("홀수");
}
for(int i=0; i<n; i++) {
System.out.println(n);
}위 코드는 O(1)과 O(n)의 코드를 합친 것이다. O(1)과 O(n)이 합쳐져 O(n+1)이라고 표현해야 할 것 같지만 Big-O 표기법에서는 상수항을 무시하는 것이 규칙이다. 즉, O(n)이 된다.
for(int i=0; i<n; i++) {
System.out.println(n);
}
for(int i=0; i<n; i++) {
System.out.println(n);
}마찬가지로 위 코드도 O(n)이 두 번 반복되니 O(2n)이 되어야 할 것 같지만 O(n)이 된다.
영향력이 낮은 항 무시
for(int i=0; i<n; i++) {
for(int j=0; j<n; j++) {
System.out.println(n * j);
}
}
for(int i=0; i<n; i++) {
System.out.println(n);
}위 코드는 O(n²)와 O(n)이 합쳐져 O(n²+n)이 될 것 같지만 O(n²)이 된다. n²에 비해서 n은 영향력이 낮으므로 이를 무시하고 표기하는 것이 규칙이다.
앞서 상수항과 영향력이 낮은 항을 무시하는 이유는 Big-O 표기법이 실제 소요시간을 나타내기 위한 방법이 아니라
자료의 수가 증가함에 따라 소요시간이 얼마나 증가하는지를 나타내기 위한 방법이기 때문이다.
대략적인 소요시간 추측하기
O( ) ← 이 괄호 안에 들어가는 식을 계산해서 1억당 1초 정도로 생각할 수 있다고 한다.
예를 들어 n이 1억인데 시간 복잡도가 O(n)이면 소요시간이 1초정도 걸린다는 뜻이다.
n이 1억, m이 10, 시간 복잡도가 O(nm)이면 소요시간이 10초가 된다는 것이다.
이렇게 대략적인 소요시간을 코딩하기 전에 추측해봄으로써
주어진 제한 시간 안에 답을 구할 수 있는지 확인할 수 있다.
[출처]
https://todaycode.tistory.com/45
[시간 복잡도란?
1. 시간 복잡도 1-1. 시간 복잡도란? 1-2. Big-O 표기법 2. 예제 2-1. O(1) 2-2. O(n) 2-3. O(n²) 2-4. O(n³) 2-5. O(nm) 2-6. O(2ⁿ) 2-7. O(logn) 3. 그 외 3-1. 상수항 무시 3-2. 영향력이 낮은 항 무시 3-3. 대략적인 소요시
todaycode.tistory.com](https://todaycode.tistory.com/45)