[알고리즘 분석]6. Running Time - 2

목차

1. Primitive Operations(기본 연산들)

2. Counting Primitive Operations(연산의 개수 새기)

3. Growth Rate of Running Time(수행시간의 증가율)

 

1. Primitive Operations(기본 연산들)

1) The Random Access Machine(RAM) Model

 

 지난 게시물에서 언급했듯이, 특정 하드웨어/소프트웨어 상황에서 계산을 해볼 경우 그 상황에만 맞는 수행시간이 계산될 것입니다. 따라서, 가상의 컴퓨터를 두고, 이 안에서 계산을 한다고 가정합니다.

 이 가상의 컴퓨터는 어떤 memory cell을 사용해도 시간은 일정한 설정으로, 즉 코어는 하나이며, 메모리가 무한이라고 가정한 컴퓨터라고 생각하면 됩니다.

 

2) Primitive Operations(기본 연산들)

 기본 연산들에 걸리는 시간은 각각 컴퓨터마다 다릅니다. 이를 imstruction set이라고 하며, cpu마다 각각의 코드들이 존재하며, 모두 다른 특징을 가지고 있습니다. 우리가 사용할 가상의 컴퓨터도 이 instruction set이 필요합니다. 따라서 전부(어떤 계산이든) RAM model은 시간이 동일하다고 가정합니다.

 

2. Counting Primitive Operations(연산의 개수 새기)

 구하고자 하는 알고리즘의 연산의 개수를 새는 과정을 요약하면 다음과 같습니다.

1. 알고리즘을 수도코드로 작성한다.

2. input의 개수를 n이라고 할 시, 결과를 n에 대한 함수로 작성함

3. input값 n에 따라서 소요되는 시간을 알 수 있음!

 이때, 6n - 1은 최악의 경우를 고려하여 나온 값입니다.

 

3. Growth Rate of Running Time(수행시간의 증가율)

1) Growth Rate of Running Time(수행시간의 증가율)

 설령 프로그램을 돌리는 하드웨어 혹은 소프트웨어가 변한다고 하더라도, 결과값인 함수의 증가율을 변하지 않습니다. 절대적인 수행 속도의 차이는 있을 수 있으나, input n에 따른 수행함수 T(n)는 변하지 않습니다.

 

2) 수행시간의 중요성

 수행시간 함수 T(n)은 생각보다 중요한 차이를 만들어냅니다. log함수의 경우, input이 n만큼 증가하더라도 runtime은 그리 커지지 않습니다. 하지만 n^2함수라면, input값이 두 배가 될시 runtime은 4배로 뛰게 됩니다.