[자료구조] 가상 컴퓨터(Virtual machine) 과 시간 복잡도(Time Complexity) - (1)

목표

시간 복잡도를 측정하기 위한 가상 컴퓨터(Virtual Machine)의 개념에 대해서 이해한다.

 

목차                                                             클릭하면 해당 목차로 이동합니다.

1. 가상 컴퓨터

 

2. 가상 언어

 

3. 가상 코드

 

4. 정리

 

개요

가상 컴퓨터, 가상 언어, 가상 코드에 대한 개념은 자료구조와 알고리즘의 성능 평가를 위해서 필요합니다. 

성능 평가는 알고리즘을 실행하는지 얼마나 걸리는지 수행시간을 측정하는 것입니다.

이 수행시간을 각자의 컴퓨터에서 코드(C, Java ..)로 수행 시간을 측정할 수도 있지만,  개개인의 H/W 성능이 제 각각이고, S/W 경이 모두 다르기 때문에 정확한 성능을 알 수 없습니다.

 

그렇기 때문에, 자료구조와 알고리즘의 성능 평가는 가상 컴퓨터 위에서 가상 언어를 이용한 가상 코드를 이용해서 진행됩니다. 어떤 특징이 있어서 가상 컴퓨터 위에서 성능 평가를 진행하는지 알아보겠습니다.

 

1. 가상 컴퓨터(Virtual Machine)

혹시 이미테이션 게임이라는 영화를 보셨나요? 앨런 튜링의 이야기를 기반으로 만들어진 영화입니다.

이 영화에서 앨런 튜링이 튜링 머신(Turing Machine)을 만드는 내용이 나오는데요.

▲영화 이미테이션 게임(2014) 中

지금 우리가 사용하고 있는 컴퓨터는 이 튜링 머신에 기초한 폰 노이만(Von Neumann) 구조를 따릅니다.

폰 노이만 구조란 CPU(프로세서) + 메모리 + 프로그램 이 세 구조로 이루어져 있습니다.

 

우리가 사용할 가상 컴퓨터에도 위와 같은 구조를 띄게 됩니다.

대신, 자료구조와 알고리즘의 성능 평가를 하기 위해 프로그램 대신 기본 연산 있으면 충분합니다.

현재 가장 많이 사용하는 가상 컴퓨터 모델은 RAM(Random Access Machine) 모델입니다.

컴퓨터에서 흔히 볼 수 있는 RAM(Random Access Memory)랑은 다른 개념입니다.

RAM 모델은 CPU, Memory, 기본 연산(Primitive Operation)으로 구성됩니다.

RAM = CPU + Memory + 기본 연산(Primitive Operation)

그렇다면 기본 연산은 어떤 연산을 뜻하는 것일까요?

기본 연산(Primitvie Operation)

기본 연산이란 연산을 진행하는데 있어서 1단위시간이 걸리는 것을 뜻합니다.

초, 분과 같은 시간 대신, 1단위시간이라는 기준을 이용하는 것입니다.

기본 연산에는 다음과 같은 연산자들이 존재합니다.

기본 연산자

배정, 대입, 복사 연산 : A = B, · · ·      (A=B의 경우 B를 읽고 A에 쓰는 대입연산입니다. 이 과정을 1단위시간동안 진행하는 것입니다.)

산술 연산      : +, -, *, %, /, · · ·    (*, /, 올림 등과 같은 연산은 1단위시간에 해결할 수 없다. RAM 모델에서는 이를 가능하다고 가정함)

논리 연산      : AND, OR, NOT, · · ·    (비교 연산도 뺄셈의 결과를 이용해서 비교하기 때문에 1단위연산입니다.)

비교 연산      : >, <, <=, >=, ==, !=, · · ·

비트 연산      : bit-AND, bit-OR, <<, >>, · · ·

 

이렇게 기본 연산을 정의한 가상 컴퓨터를 RAM 모델이라고 합니다.

RAM 모델 위에서 알고리즘의 수행시간을 측정해서 성능 평가를 진행할 수 있습니다.

 

2. 가상 언어(Virtual Language)

가상 컴퓨터 위에서 알고리즘의 성능을 평가할때는 의미만 이해할 수 있으면 충분합니다. 실제로 동작하지 않고 시뮬레이션을 진행하기 때문에 영어나 한국어같은 실제 언어보다 간단 명료하고 C, Python과 같은 프로그래밍 언어보다 융통성 있는 언어로 알고리즘을 정의합니다.

 

가상 언어는 문법을 엄격하게 지켜야 할 필요가 없습니다. 많은 기능도 필요가 없기 때문에 기본 명령어면 충분합니다. 기본 명령어는 위에서 정의한 기본연산과 아래의 명령어가 포함됩니다.

기본 명령어

기본 연산자

비교문 : if, if .. else, elif, · · · 

반복문 : while, for, · · ·

함수 정의·호출

return 문 

 

위와 같은 기본 명령어를 이용해서 문법적으로 느슨하고 의미는 확실한 가상 언어를 이용해 가상 컴퓨터를 동작합니다.

 

3. 가상 코드(Virtual Code)

가상 언어는 흔히 "슈도 코드"라고 들어보셨을겁니다. 가상 언어로 작성된 코드를 뜻합니다.

사람이 보기에 의미를 알 수 있고 문법적으로 느슨한 코드입니다.

 

예를 들면 다음과 같은 코드를 뜻합니다.

algorithm ArrayMax(A,n):
    currentMax = A[0]
    for i = 1 to n-1 do
        if currentMax < A[i]:
            currentMax = A[i]
    return currentMax

함수명만 봐도 배열의 최대값을 구하는 함수라는 것을 짐작할 수 있습니다.

n개의 정수를 갖는 배열 A가 입력값으로 들어오면, 배열 A의 값 중 최대값을 출력값으로 갖는 함수입니다.

 

이 함수의 성능 평가는 어떻게 이루어질까요?

성능은 시간 복잡도(Time Complexity)로 나타낼 수 있습니다.

 

시간 복잡도란 알고리즘을 수행하는데 얼만큼의 단위시간이 필요한지 나타내는 것입니다.

하지만, ArrayMax 함수를 보면 입력 값의 경우의 수가 무수히 많습니다.

배열 A 안에 [1, 2, 3]이 들어 있을 수도 있고 [-2 , 10, 3, 11]이 들어 있을 수도 있습니다. 혹은 [1, 4, 8 · · ·]과 같이 무수히 많은 수가 들어 있을 수도 있습니다.

 

이렇게 무수히 많은 입력 값이 존재하는데 어떤 입력을 기준으로 성능을 평가해야할까요?

이에 대한 내용은 다음 게시글에서 다루도록 하겠습니다.

 

정리

시간 복잡도에 대한 내용은 중요하기 때문에, 게시글이 길어질 것 같아서 가상 컴퓨터에서 한 번 끊고 다음 게시글에서 다루겠습니다. 안드로이드에 있는 JVM(Java Virtual Machine)이나 리눅스 수업을 듣다보면 가상 컴퓨터보다는 Virtual Machine이란 말이 더 익숙한 것 같네요. 

 

다음 포스팅은 가상 컴퓨터 위에서 자료구조와 알고리즘의 성능 평가를 어떻게 하는지 알아보겠습니다.

 

*한국외대 신찬수 교수님의 Data Structures with Python 강의를 참고하여 포스팅하였습니다.