[알고리즘] 신찬수 교수님 2. 알고리즘 시간복잡도

프로그램을 측정하는 기준이 필요

프로그램을 측정할 때

• 하드웨어와 소프트웨어 환경이 상이

• 다양한 크기의 입력이 존재

이런 것들에 영향을 받지 않고 객관적으로 알고리즘이 어느 정도 성능을 보이는지 측정하고 비교하는 방법을 필요로 하게 되었다.

객관적인 측정을 위해 가상컴퓨터(RAM) + 가상언어 + 가상코드의 조건에서 성능을 측정한다.

가상컴퓨터(RAM)

기본 연산이 1단위 시간내에 수행된다고 정의한 가상의 컴퓨터

기본연산

1. 배정연산, 대입연산, 복사연산 : a = b
2. 산술연산 : +, -, *, /, % 등
3. 비교연산 : <, <=, >, >=, ==, !=
4. 논리연산 : and, or, not
5. 비트연산 : bit별 and, or, not

가상언어

가상컴퓨터 위에서 돌아가는 언어, 아래와 같은 사항을 만족하는 가상의 언어

• 기본연산을 표현할 수 있어야한다.
• 비교를 할 수 있어야한다. (if, elif, else)
• 반복문을 사용할 수 있어야한다. (for, while)
• 함수를 정의, 호출, return을 할 수 있어야 한다.

가상코드

실제 컴퓨터에서 돌아가는 코드가 아닌 가상컴퓨터 위에서 돌아가는 코드, 의미만 통하면 된다.

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

시간복잡도(time complexity)

위 같은 가상코드에는 무한히 많은 입력(n)이 들어올 수 있다. 알고리즘의 성능을 알아보기 위해서 무한히 많은 입력에 대한 기본연산 횟수를 일일이 셀 수는 없으므로 연산이 얼마나 걸리는지 알아낼 방법이 필요하다.

이 알고리즘의 기본 연산 횟수를 어떻게 구해야할까?

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

2. 가장 안 좋은 입력(기본연산횟수를 최대한 많이 필요로 하게 만드는 입력, worstcase input)에 대한 기본 연산 횟수를 측정한다.(worstcase time complexity) -> 정확하지는 않지만 어떤 입력에 대해서도 wtc보다 수행시간이 크지 않다.

시간복잡도 = 알고리즘 수행시간 = 최악의 입력에 대한 기본 연산 횟수
입력에 대한 알고리즘의 기본연산 수행시간을 측정한 것이 시간 복잡도이다.

Big-O 표기법

시간복잡도에서 최고차항이 함수값을 결정하는 가장 큰 요인이다. 이를 간단하게 표현한 것이 Big-O 표기법이다.

수행시간 T(n) = 함수 값을 결정하는 최고차항 만으로 간단하게 표기

T1(n) = 2n - 1   ->   T1(n) = O(n)
T2(n) = 3/2n**2 - 3/2n + 1   ->   T2(n) = O(n**2)

최고차항 n만 남기고 계수는 생략한다. 그리고 간단하게 표기했다는 것을 알려주기 위해서 O를 표기하고 최고차항을 괄호로 묶어준다.