시간복잡도와 공간복잡도
CS와 PS
📜 Big-O 표기법
입력값 n과 관계된 최대 연산을 표기하는 방법이다.
여기서 최대라는 뜻은 Worst-Case, 최악의 경우만 본다는 뜻이다.
왜냐하면 예를 들자면선형 탐색(Linear Search) 알고리즘의 경우
| index(0) | index(1) | index(2) | index(3) | index(4) |
|---|---|---|---|---|
| 5 | 3 | 2 | 1 | 4 |
위와 같은 상자 5개에서 5라는 값을 찾고자 할 때 index 0부터 4까지 순차적으로 탐색하는데,
보다시피 5는 맨 앞에 있으므로 첫 탐색에 결과 값이 나온다. 그러니까 말하자면 Best-Case인 것이다.
이처럼 운이 좋을 경우 신뢰할 수 없는 데이터가 나올 가능성이 있기 때문에 항상 최악의 경우를 상정하고 보는 것이다.
그러면 적어도 더 이상의 나쁜 경우는 없을 것이기 때문에 신뢰할 수 있는 데이터가 되는 것.
위 상자에서 Worst-Case를 보면, 값 5가 index4에 위치한 경우
index 0~4까지 총 5번의 탐색을 거치므로 시간 복잡도는 O(n)이 된다.
왜냐하면 n은 상자의 길이(Length)로 볼 수 있기 때문이다.
- O(1) - Constant
- 입력 데이터의 크기에 상관없이 언제나 일정한 시간이 걸리는 알고리즘.
- O(log2 n) - Logarithmic
- 입력 데이터의 크기가 커질수록 처리 시간이 로그(log)만큼 짧아지는 알고리즘. 이진 탐색이 대표적이며, 재귀가 순기능으로 이루어지는 경우도 해당
- O(n) - Linear
- 입력 데이터의 크기에 비례해 처리 시간이 증가하는 알고리즘. 예를 들어 데이터가 10배가 되면, 처리 시간도 10배가 된다. 대표적으로 for문이 있다.
- O(n log2 n) - Linear-Logarithmic
- 데이터가 많아질수록 처리시간이 로그(log) 배만큼 더 늘어나는 알고리즘. 예를 들어 데이터가 10배가 되면, 처리 시간은 약 20배가 된다. 정렬 알고리즘 중 병합 정렬, 퀵 정렬이 대표적.
- O(n^2) - quadratic
- 데이터가 많아질수록 처리시간이 제곱으로 늘어나는 알고리즘. 예를 들어 데이터가 10배가 되면, 처리 시간은 최대 100배(10x10)가 된다. 이중 루프(n^2 matrix)가 대표적이며 단, m이 n보다 작을 때는 반드시 O(nm)로 표시하는 것이 바람직하다.
- O(2^n) - Exponential
- 데이터가 많아질수록 처리시간이 기하급수적으로 늘어나는 알고리즘. 대표적으로 피보나치 수열이 있으며, 재귀가 역기능을 할 경우도 해당.
// O(1)
System.out.println("Hello world!");
입력값 n이 몇이든 연산이 1이므로 시간 복잡도는 O(1)이다.
// O(n)
for (int i = 0; i < n; i++) {
System.out.println("Hello world!");
}
입력값 n에 따라 연산이 정비례하므로 시간 복잡도는 O(n)이다.
// O(n^2)
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
System.out.println("Hello world!");
}
}
이중 루프. 입력값 n에 따라 연산이 n의 제곱만큼 늘어나므로 시간 복잡도는 O(n^2)이다.
예를 들어 n=5일 경우 for문 두 개가 5번씩 돌아가기 때문에“Hello World!”는 25번이 찍히게 된다.
for (int i = 0; i < N; i++) {
System.out.println("Hello world!");
}
for (int i = 0; i < N; i++) {
System.out.println("Hello world!");
}
또한, 위와 같이 for문 두 개가 따로따로 있을 경우는 시간 복잡도가 O(n^2)이 아니고 O(n)이다.
왜냐하면 한 블록에서의 Worst-Case만을 표기하기 때문
📜 시간복잡도를 고민해야 한다
알고리즘 문제를 풀다 보면 같은 문제라도 어떤 해법을 선택하는지에 따라 수행에 걸리는 시간이 크게 차이 난다.
일반적으로 알고리즘에선 1억번의 연산 횟수를 어림잡아 1초정도 걸릴 거라고 기준을 잡는다.
이 등가 개념은 개인용 PC의 CPU 연산속도를 근거로 나온 수치라고 하는데,
현대의 상용 CPU는 대충 초당 1억 번의 연산을 하기 때문이란다.
📕 문제 : 1부터 N까지 수의 합 구하기
// solution 1
// 시간복잡도 O(N^2)
int sum = 0;
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= N; j++) {
if (i == j) {
sum += j;
}
}
}
// solution 2
// 시간복잡도 O(N)
int sum = 0;
for (int i = 1; i <= N; i++) {
sum += i;
}
// solution 3
// 시간복잡도 O(1)
int sum = 0;
sum = N * ( N + 1 ) / 2;
입력값 N에 대해 2중 for문으로 돌려 푼 1번 방법은 O(N^2)의 시간 복잡도가 나온다.
입력값 N에 대해 for문 한 번으로 푼 2번 방법은 O(N)의 시간 복잡도가 나온다.
입력값 N에 대해 수학공식을 대입한 3번 방법은 O(1)의 시간 복잡도가 나온다.
예를 들어 1부터 10만까지 수의 합을 구하여야 한다면,
1번 : 10만 x 10만 = 100억
2번 : 10만 = 10억
3번 : 10만 = 1
이 값들을 가지고 수행 시간을 예상해본다면,
1억 = 1초이므로
1번 : 100억 = 100초
2번 : 10만 = 0.001초
3번 : 1 = 즉시(이루 말할 수 없이 빠름)
위와같은 값을 예상할 수 있다.
1초가 걸리는 입력값 N의 크기
| BigO | 입력 |
|---|---|
| O(1) | - |
| O(lgN) | - |
| O(N) | 1억 |
| O(NlgN) | 500만 |
| O(N^2) | 1만 |
| O(N^3) | 500 |
| O(2^N) | 20 |
| O(N!) | 10 |
문제에 알맞은 알고리즘 찾기
자바 컬렉션의 시간 복잡도
📜 공간 복잡도
시간 복잡도는 어떤 명령을 수행하는데 걸리는 시간을 말한다
공간 복잡도는 어떤 명령을 수행하는데 필요한 메모리의 크기를 말한다
가장 이상적인 프로그램은 시간 복잡도와 공간복잡도가 모두 낮은 것이지만,
일반적으로 시간복잡도와 공간 복잡도는 반비례 관계이다.
우선 왜 그런지 한번 살펴보자.
📕 문제 : 소수(Prime Number) 구하기
소수(Prime Number) ?
1과 자기자신으로만 나누어 떨어지는 수3, 5, 7 …
간단하게 정리하자면 소수를 구하기 위한 조건은 아래와 같다고 볼 수 있다
2부터 n-1 까지의 어떤 정수로도 나누어 떨어지지 않는 수
public static void main(String[] args) {
// 연산 횟수를 체크하기 위한 변수
int operationCount = 0;
// 1000이하의 모든 소수를 구하기 위한 조건 (n<=1000)
for(int primeNumber = 2; primeNumber <= 1000; primeNumber++) {
// 소수를 판별하기 위한 값을 갖는 지역변수
int operation;
// 연산횟수를 증가시킴
// 2부터 n-1까지의 모든 값으로 나누다 나누어떨어지면
// 소수가 아니므로 반복문을 탈출하고 다음 수를 연산
for(operation = 2; operation < primeNumber; operation++) {
operationCount++;
if(primeNumber % operation == 0) {
break;
}
}
// 2부터 n-1까지의 모든 값으로 나누어떨어지지 않았으므로 소수이다. 출력 !
if(primeNumber == operation) {
System.out.println("primeNumber = " + primeNumber);
}
}
// 최종 연산 횟수를 출력
System.out.println("operations count = " + operationCount);
}
출력 값
primeNumber =2
primeNumber =3
primeNumber =5
… 중략 …
primeNumber = 983
primeNumber = 991
primeNumber = 997operations count = 78022
2부터 n-1 까지의 어떤 정수로도 나누어 떨어지지 않는 수
또한 이렇게도 볼 수 있다
소수 = 소수로 나누었을때 나누어 떨어지지 않는 수
그렇다면 2는 소수이므로 4이상의 모든 짝수또한 제외할 수 있겠다
소수를 찾을 때 4이상의 짝수를 제외한 1000이하의 홀수를 대상으로
구해놓은 소수들을 이용하여 찾으면 더 빠르게 연산할 수 있지 않을까?
public static void main(String[] args) {
// 연산 횟수를 체크하기 위한 변수
int operationCount = 0;
// 찾은 소수의 개수
int primeCount = 0;
// 찾은 소수를 저장하는 배열
int[] primeNumbers = new int[300];
// 배열 첫 칸에 소수 2를 집어넣고 찾은 소수의 개수를 1 증가시킴
primeNumbers[primeCount++] = 2;
// 2까지의 소수를 찾았으므로 3이상의 '홀수'를 대상으로 루프
for(int n = 3; n <= 1000; n += 2) {
int i;
for(i = 1; i < primeCount; i++) {
// 연산횟수를 증가시킴
operationCount++;
// 찾은 소수로 나누어봄
// 나누어 떨어질 경우 소수가 아니므로 반복문 탈출
if(n % primeNumbers[i] == 0) {
break;
}
}
// 마지막까지 나누어떨어지지 않았다.
// 이는 소수이므로 배열에 저장하고 찾은 소수의 개수를 증가시킴
if(primeCount == i) {
primeNumbers[primeCount++] = n;
}
}
// 배열 전체를 대상으로 루프하며 찾아낸 소수들을 출력
for(int i = 0; i < primeCount; i++) {
System.out.println("primeNumbers = " + primeNumbers[i]);
}
// 최종 연산 횟수를 출력
System.out.println("operations count = " + operationCount);
}
출력 값
primeNumber =2
primeNumber =3
primeNumber =5
… 중략 …
primeNumber = 983
primeNumber = 991
primeNumber = 997operations count = 14622
📜 결론
시간복잡도와 공간복잡도가 어떻게 반비례 관계가 되는지 간단하게 살펴보았다.
이와 같이 빠른 알고리즘은 더 많은 메모리를 사용한다.
78022 - 14622 = 63400 만큼의 연산을 덜 수행했지만,
배열을 사용했으므로 메모리를 더 많이 사용했다.
상기의 코드에서 300칸짜리 정수형 배열을 사용했는데.
정수형은 4Byte의 크기를 가지므로 300x4 = 1,200Byte (약 1.2KB)정도의 메모리를 더 사용했음을 알 수 있다.
결론적으로 시간복잡도에서 연산횟수 63,400만큼의 이득을 보았으나
공간복잡도에서 메모리 1.2KB정도의 손해를 보았다.
결국 항상 두 개의 가치 중 한 가지를 일부 포기해야만 하는(trade-off) 상황이 생기는데,
단도직입적으로 얘기하자면 우리는 시간 복잡도를 우선으로 생각해야만 한다.
예를 들어 어떤 프로그램을 짜고 보니 이 녀석이 명령 A를 수행하는데 10일이라는 시간이 걸리지만,
메모리를 더 많이 쓴다면 시간을 10일에서 1일까지 줄일 수 있다고 가정해보자.
그럼 메모리를 더 사다가 꼽으면 된다 !
이렇게 시간은 돈을 주고도 살 수 없지만 메모리는 돈주면 살 수 있다.
또한 현대의 하드웨어는 성능이 너무 엄청나서 대부분의 개발자들은 말도 안 되는 삽질을 하지 않는 한
평소 메모리의 부족을 느낄 일이 사실상 없다고 봐도 무방하다. (가끔 헛짓해서 OutOfMememory 뜨는 경우가 있긴 하다)
일반적으로 개발자들이 사용하는 개발용 노트북의 경우 메모리를
작게는 8GB부터 64GB까지 다양하게 사용하는데 이게 얼마나 큰 메모리인지 계산해보자면,
int[] ints = new int[10000][10000];
Java에서 정수형(int)은4byte의 크기를 갖는다
위 배열의 크기를 계산해보면
10,000 x 10,000 x 4 =400,000,000 Byte
1024 Byte=1 KB
1024 KB=1 MB
400,000,000 Byte= 약400 MB
우리가 사실상 사용할 일 없는 비현실적인 배열의 크기에 비해
정말 별 볼일 없는 메모리 크기가 나옴을 알 수 있다.
그러니 항상 메모리보다는 수행 시간(시간 복잡도)을 중요하게 여겨야 한다.
