[Algorithm] 복잡도 (with 자바)

복잡도 (with 자바)

'이것이 취업을 위한 코딩 테스트다 with 파이썬' 이라는 책을 공부 중입니다. 이 글은 해당 책의 내용을 요약, 정리한 글입니다. 책에서는 파이썬을 기반하여 복잡도를 설명하지만 여기서는 해당 내용을 자바로 변경하여 표현하고, 내용을 덧붙였습니다.

학습 목표

 · 복잡도란?

 · 시간 복잡도

 · 공간 복잡도

 · 시간과 메모리 측정(자바 사용)

---

 복잡도란?

 

복잡도(Complexity)는 알고리즘의 성능을 나타내는 척도다. 복잡도는 시간(Time) 복잡도와 공간(Space)복잡도로 나눌 수 있다.

 

시간 복잡도: 알고리즘을 위해 필요한 연산 횟수. 특정한 크기의 입력에 대하여 알고리즘이 얼마나 오래 걸리지는지를 의미

공간 복잡도: 알고리즘을 위해 필요한 메모리의 양. 특정한 크기의 입력에 대하여 알고리즘이 얼마나 많은 메모리를 차지하는지를 의미

 

시간 복잡도와 공간 복잡도는 거래 관계(Trade-off)가 성립할 수 있다. 메모리를 많이 사용하고, 반복되는 연산을 생략하거나 더 많은 정보를 관리하면서 계산의 복잡도를 줄일 수 있다. 실제로 메모리를 더 많이 사용해서 시간을 비약적으로 줄이는 방법으로 메모이제이션 기법이 존재한다.

 

시간 복잡도

 

시간 복잡도를 표현할 때는 빅오(Big-O) 표기법을 사용한다. 간단히 설명하면, 빅오 표기법은 가장 빠르게 증가하는 항만을 고려하는 표기법이다. 즉, 함수의 상한만 나타낸다.

 

다음 예제는 N개의 데이터를 차례로 받아 더하는 코드다.

 

int []arr = {1,2,3,4}; //N개의 데이터
int sum = 0;

for(int value : arr)
   sum += value;

 위 코드는 연산 횟수가 N에 비례함을 알 수 있다. sum 변수의 0을 대입하는 연산도 있지만, 이런 연산의 횟수는 N이 커짐에 따라 무시할 수준으로 작아진다. 따라서 영향력이 큰 부분은 N에 비례하는 연산을 수행하는 반복문이고, 시간 복잡도를 O(N)이라고 표기한다.

 

 

빅오 표기법	명칭
O(1)	상수 시간
O(logN)	로그 시간
O(N)	선형 시간
O(NlogN)	로그 선형 시간
O(N²)	이차 시간
O(N³)	삼차 시간
O(2ᴺ)	지수 시간

(시간 복잡도 표, 위쪽에 있을수록 빠르다)

 

시간 복잡도 기반으로 코딩 테스트 문제의 시간 제한을 유추할수 있다. 숙련자들은 문제를 해석하기 전에 조건을 먼저 보기도 한다. 문제의 조건부터 확인하면 문제를 풀기 위해 얼마나 효율적인 알고리즘을 작성해야 하는지 눈치 챌 수 있다.

 

예를 들어 데이터의 개수 N이 1,000만 개를 넘어가고 시간 제한이 1초라면, 대략 최악의 경우 O(N)의 시간 복잡도로 동작하는 알고리즘을 작성해야 할 것을 예상할 수 있다.  데이터의 크기나 탐색 범위가 100억을 넘어가면, 이진 탐색과 같이 O(logN)의 시간 복잡도를 갖는 알고리즘을 작성해야한다.

 

실제 코딩 테스트 문제의 시간 제한은 1~5초 가량이며, 보통 연산 횟수가 10억을 넘어가도록 작성하면 오답 판정 받을 수 있음을 주의하자.  

 

시간 제한이 1초인 문제의 경우

- N의 범위가 500: 시간 복잡도가 O(N³) 알고리즘을 설계하면 문제를 풀 수 있다.

- N의 범위가 2,000: 시간 복잡도가 O(N²) 알고리즘을 설계하면 문제를 풀 수 있다.

- N의 범위가 100,000: 시간 복잡도가 O(NlogN) 알고리즘을 설계하면 문제를 풀 수 있다.

- N의 범위가 10,000,000: 시간 복잡도가 O(N) 알고리즘을 설계하면 문제를 풀 수 있다.

 

공간 복잡도

 

공간 복잡도를 표기할 때도 빅오 표기법을 이용한다. 일반적으로 메모리 사용량 기준은 MB 단위로 제시된다.

 

코딩 테스트 문제 풀이는 대부분 배열(또는 리스트)을 사용한다. 고전적인 프로그래밍 언어에서 정수형 자료형인 int를 기준으로 배열 크기에 따른 메모리 사용량은 다음과 같다. (컴파일러에 따라 조금씩 달라질 수 있음)

 

- int a[1000]: 4KB

- int a[1000000]: 4MB

-int a[2000][2000]: 16MB

 

코딩 테스트에서 보통 메모리 사용량을 128~512MB 정도로 제한한다. 즉, 일반적인 경우 데이터의 개수가 1,000만 단위가 넘지 않도록 알고리즘을 설계해야한다.

 

시간과 메모리 측정

 

자바에서는 코드를 통해 수행 시간과 메모리 사용량을 측정할 수 있다. 다음은 자바의 기본 정렬 코드의 시간과 메모리를 측정하는 코드다. 자바의 기본 정렬 알고리즘은 ‘듀얼 피벗 퀵 알고리즘’을 사용하며, 평균 시간 복잡도 O(NlogN), 최악의 경우 시간 복잡도는 O(N2)이다.

 

수행 시간 측정

import java.util.Arrays;

public class Main {

   public static void main(String[] args) {

       int []arr = new int [100_000_000];

       for(int i=0; i<100_000_000; i++) {
           arr[i] = (int) Math.random();
       }

       long before = System.currentTimeMillis(); //코드 실행 전 시간

       //실행할 소스코드
       Arrays.sort(arr);

       long after = System.currentTimeMillis(); // 코드 실행 후 시간
       long diff = (after - before); //두 시간에 차이
       System.out.println("시간차이(밀리세컨즈) : "+diff);

   }
}

main 함수 실행 결과

 

메모리 사용량 측정
import java.util.Arrays;



public class Main {

   public static void main(String[] args) {

       int []arr = new int [100_000_000];
       
       for(int i=0; i<100_000_000; i++) {
           arr[i] = (int) Math.random();
       }

       // Garbage Collection으로 메모리 초기화
       System.gc();


       // 실행전 메모리 사용량 조회
       long before = Runtime.getRuntime().totalMemory() - Runtime.getRuntime().freeMemory();
       System.out.println("Used Memory : " + before);


       // 프로그램 소스코드
       Arrays.sort(arr);

       // Garbage Collection으로 메모리 정리
       System.gc();

       // 실행 후 메모리 사용량 조회
       long after  = Runtime.getRuntime().totalMemory() - Runtime.getRuntime().freeMemory();

       // 메모리 사용량 측정
       long usedMemory = (before - after)/1024;

       System.out.println("Used Memory(MB): " + usedMemory);

   }
}

 

main 함수 실행 결과

 

 참고 

https://www.baeldung.com/java-sorting

hijuworld.tistory.com/2

m.blog.naver.com/PostView.nhn?blogId=spdlqjdudghl&logNo=220903158930&proxyReferer=https%3A%2F%2Fwww.google.com%2F