알고리즘 시간복잡도

본 포스팅은 한국외대 신찬수 교수님의 자료구조 (Data structure w Python) 중 3강,4강,5강을 바탕으로 핵심 내용을 정리한 글입니다.

 

<자료구조를 활용한 알고리즘의 성능을 측정하고 비교하는 척도>

 

1) 기술한 코드가 컴퓨터에서 동작할 때 HW/SW 환경에 따라 다른 성능을 보인다. -> 환경에 구애받지 않고 객관적으로 평가하는 방법?

2) 다양한 크기의 입력에 대응할 수 있어야한다. -> 다양한 크기의 입력에 대한 코드의 실행 속도 측정?

 

🌟 가상의 환경에서 독립적으로 작동하여 객관적인 평가가 가능해지는 상태에서 알고리즘을 평가하는 것이 필요하다.

 

가상 컴퓨터(virtual machine) + 가상 언어(pseudo language) + 가상 코드(pseudo code)

 

• 가상 컴퓨터(Virtual Machine/RAM)

- RAM(Random Access Machine) = CPU(계산 수행 unit) + Memory + Code(기본 연산; 1 단위 시간에 수행되는 연산들의 모음)

 

• 가상 언어(Pseudo/Virtual Languages)

- 기본 연산 표현, 비교 연산, 반복문, 함수 정의, 호출 및 값 return 등의 표현이 가능해야한다.

 

• 가상 코드(Pseudo Code)

- 가상 언어로 작성된 코드로, RAM에서 돌아가는 코드이다.

- 실제 동작하는 programming language 문법보다 느슨한 형태로 기술된다.

 

ex) A=[3,-1, 9, 2, 12], n=5인 입력에 대해서 다음의 pseudo code를 실행한다고 했을 때 총 기본 연산 7 단위 시간이 필요하다.

algorithm ArrayMax(A, n):
	input: n개의 정수를 갖는 배열 A
    output: A의 수 중에서 최댓값 리턴
    
    CurrentMax = A[0]  #대입 -> 기본 연산 1회
    for i=1 to n-1 do;  #반복문 내부 i관련 기본 연산(대입,증가,비교)은 고려 x
    	if CurrentMax < A[i]: # *
        	CurrentMax = A[i] 
    return CurrentMax

 

배열 A에 들어갈 수 있는 수 = 1,2,3, ... , ∽ / n = 1,2,3, ... , ∽  <== T(n) = 2n-1

 

모든 입력의 경우의 수에 대하여 기본 연산의 횟수를 모두 계산할 수 없으므로 다양한 입력에 대응되는 알고리즘의 평가 척도를 설정하는 것이 중요하다.

 

<Time Complexity>

 

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

2) 가장 안 좋은 입력(Worstcase input)에 대한 기본 연산 횟수를 측정 "Worstcase time complexity"

 

📍 알고리즘 수행 시간 = 최악의 입력에 대한 기본 연산 횟수

• 어떤 입력에 대해서도 W.T.C 보다 수행시간이 크지 않다는 것이 보장된다.

ArrayMax 함수는 입력 배열 A가 오름차순 정렬되어 있는 경우가 worst case이다. (*비교문을 n-1회 실행하기 때문에. / T(n)=2n-1)

 

ex) 

algorithm Sum1(A, n):
    sum = 0
    for i = 0 to n-1 do;
    	if A[i]%2==0: #짝수  # *
        	sum += A[i]  
	return sum

 

Sum1 함수는 입력 배열 A의 모든 값이 짝수인 경우가 worst case이다. (T(n) = 4n+1)

algorithm Sum2(A, n):
    sum = 0
    for i = 0 to n-1 do;
    	for j = i to n-1 do;
            sum += A[i] * A[j] #기본 연산 횟수 : 3회
    return sum

 

Sum2 함수는 입력에 상관 없이 이중 for문을 반복한다. 모든 경우의 수가 worst case이다. (T(n) = (3/2)*n*(n+1)

 

Sum1은 n이 커질 수록 수행시간이 n에 비례하여 커지고, Sum2는 n^2에 비례하여 커진다.

 

<Big-O>

 

위 세 예제의 Time complexity로 알 수 있는 것은 다음과 같다.

 

0) Algo1과 Algo는 최고차항이 n으로, 선형적으로 증가한다. 반면 Algo3는 최고차항이 n^2으로, 제곱으로 증가한다.

1) Algo2가 Algo1보다 2배 느리다.

2) Algo3는 n<3/5면 Algo2보다 빠르다. n>3/5면 항상 Algo2보다 느리다.

3) 모든 n에 대해서 Algo3은 Algo1보다 느리다.

 

🌟 표기법

증가율인 최고차항만 남기며, 최고 차항의 계수는 생략한다.

 

n->∽ 일 때 최고차항에 비례하여 시간이 소모된다.

 

즉, T1(n) = O(n) / T2(n) = O(n) / T3(n) = O(n^2) 으로 표기할 수 있다.