[Algorithm] 시간복잡도와 공간복잡도는 반비례

소수(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 = 997

operations 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 = 997

operations count = 14622

 

---

결론

빠른 알고리즘은 더 많은 메모리를 사용한다

78022 - 14622 = 63400 만큼의 연산을 덜 수행했지만,

배열을 사용했으므로 메모리를 더 많이 사용했다

상기의 코드에서 300칸짜리 정수형 배열을 사용했는데,

정수형은 4Byte의 크기를 가지므로 300x4 = 1,200Byte (약 1.2KB)정도의 메모리를 더 사용했음을 알 수 있다

결론적으로,

시간복잡도에서 연산횟수 63,400만큼의 이득을 보았으나

공간복잡도에서 메모리 1.2KB정도의 손해를 보았다