알고리즘
알고리즘의 효율성을 판단하는 기준은 다음과 같다.
- 시간 복잡도(time complexity) : 얼마나 빠르게 결과를 출력하는가? (연산을 할 때 거치는 단계의 수)
- 공간 복잡도(space complexity) : 메모리를 얼마나 사용하는가?
효율성을 판단하는 표기법은 총 세 가지이다.
1. 빅오 표기법
"이것보단 더 나쁠 순 없어"와 같이 최악일 때의 성능을 판단해서 평균과 가까운 성능으로 예측한다. (상한)
2. 빅오메가 표기법
"이것보단 더 좋을 순 없어"와 같이 최상일 때의 성능을 판단해서 예측한다. (하한)
3. 빅세타 표기법
평균적인 성능을 판단한다.
왜 Big-O 표기법을 사용할까?
시간 복잡도를 읽기 쉽고 빠르게 파악할 수 있게 해주기 때문이다. 어떤 알고리즘을 선택해야 할 때 알고리즘의 실행 시간이 얼마나 걸리는지만 고려하는 것이 아니라, 리스트의 크기가 증가할 때 어떻게 증가하는지를 파악해야 하고 이때 빅오 표기법을 사용할 수 있다.
예를 들어, 단순 탐색과 이진 탐색 중 하나의 알고리즘을 선택해야 할 때 빅오 표기법으로 다음과 같은 비교가 가능하다.
단순 탐색은 원소를 하나씩 확인하기 때문에 n번을 연산해야 하므로 실행 시간이 O(n)이고 이진 탐색은 크기가 n인 리스트를 확인하기 위해 log n번의 연산이 필요하므로 실행 시간이 O(log n)이다.
그러므로 단순 탐색이 아닌 이진 탐색을 선택할 수 있는 것이다.
시간 복잡도
| 이름 | 표기법 |
| 상수(Constant) 시간 | O(1) |
| 로그(logarithmin) 시간 | O(logN) |
| 선형(linear) 시간 | O(N) |
| N long N 시간 | O(NlogN) |
| 이차(quadratic) 시간 | O(N^2) |
| 지수(exponential) 시간 | O(2^N) |
| N의 n승(N-power-n)시간 계승(factorial) |
O(N^n) O(N!) |
1. O(n)
Linear Search(선형 검색) 알고리즘은 한 개씩, 한 개씩 검색한다. 데이터가 10개면 10개의 스텝, 20개면 20개의 스텝이 필요하기 때문에 input size가 n이면 선형 알고리즘은 n 스텝이 요구된다. 이때의 시간복잡도를 빅오표기법으로 O(n)이라고 표현한다.
예제
- 배열에서 검색, 최솟값, 최댓값 찾기
- LinkedList에서 순회, 최솟값, 최댓값 찾기
2. O(1)
만약 array를 매개변수로 받는 메서드가 항상 첫 번째 인덱스를 출력한다면 input size가 10개이든, 100개이든 항상 1 스텝만 필요로 한다. 이렇게 동일한 수의 스텝이 계속 요구되는 시간 복잡도를 Constant Time(상수 시간)이라고 하며 O(1)이라고 표현한다.
그런데 위의 메서드에서 첫 번째 인덱스를 두 번 출력하게 된다면 그건 O(2)이 될까? 여전히 O(1)이다. input size가 얼마이든 동일한 수의 스텝이 필요한 건 다르지 않기 때문이다. 항상 선호되는 알고리즘이지만 구현하기는 쉽지 않다.
예제 코드
- 배열에서 원소 접근(random access)
- 스택 자료구조에서 push(삽입)과 pop(삭제)
- 큐에서 enqueue(삽입)과 dequeue(삭제)
- 해시 테이블에서 원소 접근
2-1. O(1)과 O(N) 비교하기
1) 1부터 주어진 N개까지의 합계를 구해야 할 때 O(1)과 O(N)을 구현한 예제 코드이다.
1️⃣ O(N)
1부터 N까지 반복하며 합계를 더하고 있다.
public int sum(int N) {
int total = 0;
for (int i = 1; i <=N; i++) {
total += i;
}
return total;
}
2️⃣ O(1)
연산을 통해 합계를 구한다.
public int sum(int N) {
int total = 0;
total = (N * (N + 1)) / 2;
return total;
}2) 배열의 요소를 조회하려고 한다.
1️⃣ O(N)
0부터 size-1까지 순회하며 value에 맞는 값이 있는지 찾는다. 0번째 인덱스에 찾는 값이 있다면 O(1)이 될 수도 있지만 만약 모든 요소에 찾는 값이 없다면 O(N)이 된다.
public int search(int[] arr, int value, int size) {
for (int i = 0; i < size; i++) {
if (arr[i] == value) return i;
}
return 0;
}
2️⃣ O(1)
index에 해당하는 배열의 요소를 반환한다.
public int getAt(int[] arr, int index) {
return arr[index];
}3. O(n²)
Quadratic Time(2차 시간)으로 Nested Loops(중첩 반복)이 있을 때 발생한다. 배열의 각 아이템에 대해 루프를 반복해서 실행하며 input size가 10개라면 완성하는데 100번의 스텝이 필요하다.
만약 아래의 예제처럼 다른 값으로 이중 for문을 반복하면 어떻게 될까?
public int doSomething(int N, int M) {
int total = 0;
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= M; j++) {
total += (i + j);
}
}
return total;
}이럴 때는 O(N²)이 아닌 O(NM)이라고 표기한다.
3-1. O(N)과 O(N²) 비교하기
1️⃣ O(N)
N이 음수일 때는 항상 N을 반환하기 때문에 O(1)이지만 그렇지 않을 때는 반복을 해줘야 하기 때문에 O(N)이다. 이때는 실행 시간이 많은 시간 복잡도를 가지게 된다.
public int doNothing(int N) {
int i, total = 0;
if (N < 0)
return N;
else {
for (i = 1; i <= N; i++) {
total += i;
}
return total;
}
}
2️⃣ O(N²)
N의 개수가 100번이라면 100 x 100번, 10000번 반복해야 한다.
public int doSomething(int N) {
int total = 0;
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= N; j++) {
total += i;
}
}
return total;
}- 버블 정렬(bubble sort)
- 선택 정렬(selection sort)
- 삽입 정렬(insertion sort)
4. O(log n)
Logarithmic Time(로그 시간)으로 이진 탐색 알고리즘의 시간 복잡도이다. 이진 탐색에서는 input을 일단 반으로 나누고 시작한다. 매번 스텝을 진행할 때마다 input size가 10에서 20이 되어도 검색을 하기 위한 스텝은 1만 증가한다.
이 시간복잡도는 선형 시간보다 빠르고 상수시간보다는 느리다. 데이터의 개수가 많으면 많을수록 효율적이다.
예제
이진 검색(binary search)처럼 각 스텝마다 연산 횟수가 1/2씩 줄어들 때의 시간 복잡도를 말한다. 아래 예제 코드에서는 N이 10이라면 i가 10, 5, 2, 1 순으로 줄어드는 것을 확인할 수 있다.
public int doSomething(int N) {
int total = 0;
for (int i = N; i > 0; i /= 2) {
total += i;
}
return total;
}
5. O(n log n)
예) 퀵 정렬
6. O(n!)
input 데이터가 n개일 때 결과를 계산하기 위해 n!(n 팩토리얼) 번의 연산이 필요하다.
예) 외판원 문제
점근적 표기법(asymptotic notation)
아래처럼 반복문이 3번 반복되는 경우에는 O(3N)이라고 할 수 있을까? 상수 값이 가지는 영향이 미비하기 때문에 O(N)이라고 표현하는 것이 맞다. 가지는 영향이 미비하다는 것은 O(N)이 달라짐에 따라 성능이 달라지는 것이지 앞의 상수 값으로 성능이 달라지지 않다는 의미로 생각하면 될 것 같다.
public int doSomething(int N) {
int total = 0;
for (int i = 1; i <= N; i++) {
total += i;
}
for (int i = 1; i <= N; i++) {
total += i;
}
for (int i = 1; i <= N; i++) {
total += i;
}
return total;
}
만약 이런 경우에는 어떨까?
이중 for문을 다섯 번을 돌고 한 번의 for문을 반복해서 O(5N² + N)으로 표현할 수 있을 것 같다. 점근적 표기법으로는 어떻게 변경이 될 수 있을까? 이럴 때는 최고차항에만 집중하자. 그러면 O(5N²)이 된다. 위에서 얘기했듯이 상수를 제거하면 아래 예제 코드의 시간 복잡도는 O(N²)이 될 것이다.
public void doSomething(int N) {
int total[5] = { 0 };
for (int i = 0; i < 5; i++) {
for (int j = 1; j <= N; j++) {
for (int k = 1; k <= N; k++) {
total[i] += (i + j + k);
}
}
}
for (int i = 0; i < N; i++) {
printf("total[%d] = %d\n", i, total[i]);
}
}빅오표기법 한 눈에 보기
| 네모 칸의 수 | O(log n) | O(n) | O(n log n) | O(n²) | O(n!) |
| 16 | 0.4초 | 1.6초 | 6.4초 | 25.6초 | 66301년 |
| 256 | 0.8초 | 25.6초 | 3.4분 | 1.8시간 | 2.7x10⁴⁹⁸년 |
| 1024 | 1.0초 | 1.7분 | 17분 | 1.2일 | 1.72x10²⁶³¹년 |
시간 복잡도의 예제
| 시간복잡도 | 예 |
| O(1) | - 배열에서 원소 접근(random access) - 스택 자료구조에서 push(삽입)과 pop(삭제) - 큐에서 enqueue(삽입)과 dequeue(삭제) - 해시 테이블에서 원소 접근 |
| O(logN) | - 이진 검색(binary search) |
| O(N) | - 배열에서 검색, 최솟값, 최댓값 찾기 - LinkedList에서 순회, 최솟값, 최댓값 찾기 - 계수 정렬(버킷 정렬) |
| O(NlongN) | - 병합 정렬 - 퀵 정렬(평균 시간 복잡도) - 힙 정렬 |
| O(N^2) | - 버블 정렬 - 선택 정렬 - 삽입 정렬 |
| O(2^N) | - 피보나치 수열 |
| O(N!) | - 팩토리얼 |
참고
- https://www.youtube.com/watch?v=BEVnxbxBqi8
- <Hello Coding 그림으로 개념을 이해하는 알고리즘>, 아디트야 바르가바
- https://www.youtube.com/watch?v=UOsEmxxPfyA&list=PLrj92cHmwIMfxmffI2RSuSmWfmHvLksoB
'Computer Science > Algorithm' 카테고리의 다른 글
| [백준] 9020 - 골드바흐의 추측 (Java) (0) | 2022.09.20 |
|---|---|
| [백준] 2581 - 소수 (Java) (1) | 2022.09.19 |
| [백준] 2839 - 설탕 배달 (Java) (0) | 2022.09.18 |
| [백준] 2869 - 달팽이는 올라가고 싶다 (Java) (0) | 2022.09.18 |
| [백준] 1193번 - 분수찾기 (Java) (0) | 2022.09.18 |
