계산 시간 추정하기

문제 

10억개의 int 중에서 100만개의 int를 작은 순서대로 추출하려고 한다
메모리는 얼마가 필요하며 총 계산 시간은 얼마가 걸릴까?

1. 메모리가 얼마 필요할까?

 

int의 메모리 크기느 일반적으로 4byte라고 말한다 하지만 이는 정확하지 못하다.

c, c++의경우 4byte

java의 경우 일반적으로 4byte

python의 경우 24byte가 출력된다.

python은 24byte인 이유는 객체이기 때문이다. sys.maxsize를 할경우 64bit컴퓨터 기준 8byte가 출력된다.

계산을 위해 전제조건으로  64bit java 언어를 기준으로 하겠다.

 

int로 충분히 10억까지의 숫자를 담을수 있으므로 10억은 int로 만들수있다 10억 x 4byte를 하면 약 4GB의 메모리 공간이 필요함을 알 수 있다. 

 

 

2. 시간복잡도 선택

10억개의 리스트를 정렬하는건 상당히 큰 작업이다.

 

이럴경우 다음과 같은 정렬 알고리즘을 생각해 볼 수 있다.

 

부분 정렬 알고리즘 사용

퀵셀렉션(Quickselect) 또는 힙셀렉션(Heapselction)과 같은 부분 정렬 알고리즘을 사용하여 전체 리스트를 정렬하는 대신 작은 순으로 필요한 만큼의 요소만 찾는다.

퀵 셀렉션의 경우 최선의 경우 O(N) 최악의 경우 O(N^2)의 시간 복잡도를 같는다.

 

분할 정복 알고리즘 사용

병합 정렬(Merge Sort)이나 퀵 정렬(Quick Sort)과 같은 분할 정복 알고리즘을 사용하여 전체 리스트를 정렬하는 대신 작은 순으로 필요한 만큼의 요소만 선택한다.

병합 정렬의 경우 평균 O(nlogn) 최악의 경우도 같은 시간 복잡도를 가진다.

 

총 100만개의 작은 숫자를 구해야 하니 병합정렬 기준으로 시간 복잡도를 계산한다

 

다음과 같은 가정을 해보자.

일반적으로 1 GHz 프로세서에서는 10^9 연산을 1초에 수행할 수 있다고 가정

10^9 x log2​(10^9) = 10^9 x 30 ≈ 30×10^9x 10^9 x 30 ≈ 30×10^9
즉 약 30초의 계산결과가 평균적으로 나온다.