계산 시간 구하는 법

지난 글: [알고리즘] - 입력 크기와 계산 시간과의 관계

 

입력 변화에 따른 계산 시간 변화는 실제로 프로그램을 작성해서 컴퓨터에서 실행해보고 실제 걸리는 시간을 계측하는 것이 가장 현실적이다. 하지만 이 방법으로는 같은 알고리즘이라도 사용하는 컴퓨터에 따라 계산 시간이 달라져서 불편하다. 

따라서 계산 시간에는 '스탭 수'라는 것을 활용한다고 한다. '1스텝'은 계산의 기본 단위로, '계산을 종료하기까지 기본 단위를 몇 회 실행했는가'로 계산 시간을 측정한다. 예로, 선택 정렬의 계산 시간을 이론적으로 구해보자. 선택 정렬은 아래어ㅏ 같은 알고리즘이었다.

1. 수열에서 최솟값을 찾는다. 

2. 최솟값을 수열의 가장 왼쪽 숫자와 교환하고 정렬을 끝낸다. 1로 돌아간다.

수열의 숫자 개수를 n이라고 하면 1의 '최솟값을 찾는다' 프로세스는 n개의 숫자를 확인하면 끝난다. 여기서 '하나의 숫자를 확인한다'는 조작을 기본 단위로 생각하고 이때 걸리는 시간을 Tc라고 하면, 1.은 n x Tc 시간에 끝난다. 계속해서 '두 개의 숫자를 교환한다'라는 조작도 기본 단위로 Ts 시간이 걸린다고 하면 2.의 프로세스는 n과 관계없이 교환을 한 번만 하므로 Ts 시간에 끝난다. 1. 과 2. 는 n회 반복하고 1회의 라운드마다 확인할 숫자가 하나씩 줄어들므로 전체 계산 시간은 다음이 된다고 한다. (n x Tc + Ts) + ((n - 1) x Tc + Ts) + ((n - 2) x Tc + Ts) + ···· + (2 x Tc + Ts) + (1 x Tc + Ts)

마지막 한 개의 숫자는 확인이 불필요하지만 확인해서 교환하는 시간을 포함하고 있다고 한다.

 

솔직히 이해는 했는데 수학 시간에나 보던 알파벳과 숫자를 활용한 식을 보니 어지럽다.

열심히 하자..!

 

참고 서적: