[알고리즘] 시간복잡도

시간복잡도

개요

자료구조와 알고리즘을 구현한 실제 코드는 컴퓨터에서 동작합니다. 이 때, H/W와 S/W환경에 따라 동작되는 시간이 달라지고 코드에 입력되는 값에 따라도 시간이 달라지게 됩니다.

이러한 모든 요소를 고려할 때, 코드가 동작되는 시간을 보편적으로 구하기 위해 가상환경을 만듭니다.

가상환경은 가상컴퓨터(Virtual Machine) + 가상언어(Pseudo Language) + 가상코드(Pseudo Code)로 구성됩니다.

가상컴퓨터(Virtual Machine)는 컴퓨터가 동작될 때, 필요로한 요소로 CPU, Memory, 기본연산으로 이루어집니다.

이 때 기본연산은 다음과 같이 존재합니다.

• 배정,대입,복사연산 $ex) A=B$

• 산술연산 $ex) +, -, *, /$

• 비교연산 $ex)>, >=, <, <=, ==, !=$

• 논리연산 $ex)AND, OR, NOT$

• 비트연산 $ex)\&(bit-and), |(bit-or),\backsim(bit-not)$

그리고 이러한 기본연산은 모두 1단위시간에 완료되는 연산으로 가정합니다.

가상언어(Pseudo Language)는 가상컴퓨터에서 제공하는 기본연산을 표현할 수 있는 언어입니다.

• 배정, 산술, 비교, 논리, 비트 연산

• 비교: $if, else if$

• 반복: $for, while$

• 함수: 정의, 호출, return

가상코드(Pseudo Code)는 가상언어로 작성한 코드를 의미합니다.

다음과 같은 가상코드의 예를 살펴보겠습니다.

 //input: n개의 정수를 갖는 배열 A
 //output: A에서 최대값 리턴
 
algorithm ArrayMax(A,n):
  currentMax = A[0]
  for i =1 to n-1 do
    if currentMax < A[i]:
        currentMax = A[i]
  return currentMax

배열 A에서 최대값을 찾는 함수입니다.

만약 배열 A가 아래와 같이주어진다면,

A

3

-1

9

2

12

총 기본연산 횟수를 세어보면 모두 7회 발생합니다.

만약 이런 함수에 입력된 배열 A의 원소개수가 많아져 무한에 값이 가까워지면 과연 총 기본연산 횟수를 알 수 있을까요?

그럴 경우에는 물론 모든 기본연산 횟수를 알기는 어려울 것입니다.

---

시간복잡도

이를 해결하기 위해 2가지 방법을 먼저 생각해봅니다.

1. 모든 입력에 대해 기본연산 횟수를 더한 후 평균 (현실적으로 불가능)

2. 가장 안좋은 입력(Worst Case Input)에 대한 기본 연산횟수를 측정

➜ 어떤 입력에 대해서도 Worst Case Input보다 수행시간이 크지 않으므로 보통 2번을 선택하여 구합니다.

즉, 알고리즘 수행시간 = 최악의 입력에 대한 기본연산 횟수로 생각합니다.

 //input: n개의 정수를 갖는 배열 A
 //output: A에서 최대값 리턴
 
algorithm ArrayMax(A,n):
  currentMax = A[0]
  for i =1 to n-1 do
    if currentMax < A[i]:
        currentMax = A[i]
  return currentMax

위에서 살펴본 함수를 다시 살펴보겠습니다.

    if currentMax < A[i]:
        currentMax = A[i]

이 경우에, 아래 대입 연산은 if조건문을 만족할 때, 발생됩니다.

그러므로 배열A의 값이 오름차순으로 정렬된 경우에 가장 안좋은 입력이 주어진 경우로 볼 수 있습니다.

따라서 입력크기가 N이고 오름차순으로 정렬된 배열 A가 주어졌을 때, 총 기본연산 횟수를

$T(n) = 2n-1$과 같은 식으로 식으로 표현 할 수 있습니다.