SImpAS

Typescript로 자료구조(Data-Structure)직접 구현해보기: :Intro (2) 본문

Algorithm/자료 구조

Typescript로 자료구조(Data-Structure)직접 구현해보기: :Intro (2)

잡다한 것들은 다 해보겠다 simpas 2020. 3. 27. 22:40

지난 0.3절과 0.4절에서는 자료구조, 자료구조와 알고리즘의 관계에 대해 어느 정도 알아봤습니다. 이번 시간에는 알고리즘을 직접 구현한다면, 어떻게 이 알고리즘이 좋은지, 좋지 않은지 판단할 수 있는 기준시간 복잡도에 대해서 알아보겠습니다. 

0. 5 시간 복잡도

시간 복잡도는 결국 프로그램이 주어진 기능을 얼마나 빠르게 수행할 수 있는지를 나타냅니다. 이름에 '시간'이 들어간다는 사실과 알고리즘 효율을 결정하는 데에 사용된다는 사실을 바탕으로 추측할 수 있죠.  단, 일반적인 시간의 개념과는 다르죠. 

 

일반적인 관점에서 보면, 시간은 모두에게 공평하게 흐릅니다. 하지만 컴퓨터 프로그램은 컴퓨터 성능에 영향을 받아서, 같은 프로그램이라도 컴퓨터의 성능에 따라서 속도에 차이가 나게 됩니다. 이 때문에, 일반적인 관점에서 바라본 시간의 개념을 도입할 수 없는 거죠.

 

컴퓨터 프로그램 또한, 모든 컴퓨터에게 공평하게 작용할 수 있는 잣대가 필요해서 시간 복잡도라는 개념이 등장하게 된 겁니다.

 

그럼 모든 컴퓨터가 납득할만한 시간의 잣대가 뭘까요?

모든 컴퓨터가 납득할만한 시간의 잣대를 배우기 이전에, 우선 이걸 짚고 넘어갑시다. 알고리즘의 효율성을 따지기 위해서는 적당히 많은 데이터가 필요합니다 그리고 이런 데이터들을 수정하거나 삭제, 또는 비교 등의 데이터 연산을 진행해야 합니다.

 

0.4절에서 사용된 UpDown 게임을 예로 들어보겠습니다.

룰은 다음과 같습니다.

  1. UpDown게임과 룰이 같다.
  2. 단 숫자가 1부터 2까지다.

위와 같은 UpDown게임을 진행하게 되면, 그 어느 누가와도 최소 2번 안에는 맞추게 됩니다. 이렇게 되면 심리학을 사용하든 반반 규칙을 사용하든 아무 의미가 없어져버리죠.

 

따라서, 알고리즘의 효율성을 따지기 위해서는 충분히 많은 데이터를 필요로 합니다.

자, 그럼 충분히 많은 데이터를 처리할 때 좋은 알고리즘이 더욱 효율적으로 처리할 수 있다는 사실을 알게 됐습니다.

 

그럼 이제 모든 컴퓨터가 납득할만한 시간의 잣대에 대해 생각해봅시다. 주어진 데이터를 알고리즘을 통해 정제할 때에, 결국 모든 데이터들에 대해 똑같은 작업을 수행할 겁니다. 이를 프로그래밍에서는 반복문을 통해 제어하죠.

 

각 반복문은 데이터마다 어떤 작업들을 실행하게 되는데, 그 어떤 작업들로는 데이터 비교, 수정, 삭제, 삽입이 있을 수 있습니다. 그리고 그 작업들이 일어나는 횟수는 데이터가 변하지 않는 한, 결국 컴퓨터마다 똑같게 되겠죠. 즉, 반복문 안에서 데이터마다 실행하는 작업들의 총횟수를 모든 컴퓨터가 납득할만한 시간의 잣대로 삼은 것입니다.

 

시간 복잡도는 즉, 데이터가 주어졌을 때, 데이터에 실행하는 작업들의 총횟수입니다. 하지만 데이터마다 실행되는 작업이 있을 수 있고, 일부 데이터에서만 실행하는 작업이 있을 수 있습니다.

 

예를 들어 배열이 주어졌을 때, 배열에 들어 있는 짝수들을 모아 새로운 배열로 만들어주는 프로그램을 만든다고 생각해 봅시다. 이런 경우, 배열을 반복문으로 순회할 때, 홀수인 데이터는 새로운 배열에 넣는 작업을 하지 않게 되죠.

 

이렇게 되면 홀수만 들어있는 배열과, 짝수만 들어있는 배열에서 시간의 차이가 생길 수밖에 없습니다.

 

이런 다양한 상황을 고려하기는 힘들기 때문에, 시간 복잡도는 N개의 데이터가 주어졌을 때, 모든 작업들이 실행되는 최악의 상황을 고려하여 표기하게 됩니다. 그리고 이를 빅 오 표기법이라고 부릅니다. 위의 예시에서는 시간이 가장 오래 걸릴 때인, 배열의 모든 요소가 짝수 일 때를 고려하여 빅 오 표기법으로 표기하게 되는 거죠.

 

0. 6 빅 오 표기법

우선 빅 오의 형태는 다음과 같습니다: O(시간)

빅 오 표기법의 특성에 의해 시간의 자리에는 1, N, logN, Nm (m ≥ 2), 그 외 이렇게 다양하게 올 수 있지만, 그중에서도 비교적 간단한 1, N, logN, Nm 에 대해 알아보도록 합시다.

0. 6. 1 상수 시간

우선 시간의 자리에 1이 들어와서 시간 복잡도가 O(1)인 경우를 생각해봅시다. 시간 복잡도가 O(1)과 같은 상수 시간이라면 데이터의 개수와 상관없이 걸리는 시간이 똑같다는 뜻입니다.

 

보통 상수 시간은 객체에 값을 삽입한다거나, 배열의 특정 인덱스에 값을 삽입하거나 새로운 값을 추가할 때 걸리는 시간입니다. 둘 다 값을 저장할 공간의 주소를 알고 그 주소에 해당하는 위치에 찾아가서 값을 수정하는 일이기 때문에 상수 시간이 걸립니다.

 

상수 시간은 이번에 비교할 네 가지 시간 복잡도 중 가장 빠른 시간 복잡도에 해당합니다.

0. 6. 2 로그 시간

O(logN)에 해당하는 로그 시간은 데이터의 개수가 두배 늘어날 때마다 수행하는 작업이 1회 추가되는 시간 복잡도입니다. UpDown게임에서 반반 규칙으로 게임을 진행한 것이 바로 그 예시에 해당합니다. 로그 시간에서의 logN은 log2N에서 밑인 2를 생략한 것입니다.

 

UpDown 게임에서 데이터의 개수가 N이었고, log100 < 7 이기 때문에 최소 7번이면 정답까지 도달할 수 있게 된 겁니다.

 

로그 시간은 이번에 비교할 네 가지 시간 복잡도 중 두 번째로 빠른 시간 복잡도에 해당합니다.

0. 6. 3 선형 시간

선형 시간은 데이터의 개수가 한 개 추가될 때마다 수행하는 작업도 1회 추가된다는 뜻입니다. 일반적으로 배열에 있는 데이터의 길이만큼 반복문을 돌리게 되면 걸리는 시간입니다.

 

선형 시간은 이번에 비교할 네 가지 시간 복잡도 중 세 번째로 빠른 시간 복잡도에 해당합니다.

0. 6. 4 지수 시간

지수 시간은 데이터의 개수가 한 개 추가될 때마다 수행 횟수가 m제곱(m ≥ 2)만큼 늘어나는 시간 복잡도입니다. 일반적으로 반복문을 여러 개 중첩해서 데이터를 처리할 때 걸리는 시간입니다.

 

지수 시간은 이번에 비교할 네 가지 시간 복잡도 중 가장 느린 시간 복잡도에 해당합니다.


이번 0.5절과 0.6절에서는 시간 복잡도와 시간 복잡도의 표기법인 빅 오 표기법에 정말 간략하게 알아봤습니다. 아무래도 실제 코드는 없고 긴 문장들로만 이루어져서 이해하기 힘들 수 있었다고 생각합니다.

그래서 다음 시간에는 각 시간 복잡도에 해당하는 코드를 실제로 구현해보고, 같은 시간 복잡도로 표기된 알고리즘들의 효율을 분석하는 법을 배워보도록 하겠습니다.

0 Comments
댓글쓰기 폼