1-2. 시간 복잡도 분석

1. 알고리즘 분석

이번 게시글도 저번 게시글에서 이어진다.

1. 시간 복잡도

 시간 복잡도(Time Complexity)란 연산의 실행 횟수를 입력 크기 n에 대한 함수로 표기한 것을 말한다. 알고리즘 내에서 실행되는 기본 연산의 횟수라고도 볼 수 있는 시간 복잡도는 T(n)(n은 입력의 크기)으로 표시한다. 알고리즘에서 시간 복잡도를 분석하기 위해서는 몇 가지 가정을 해야 한다.

1. 알고리즘은 가상 컴퓨터에서 가상 언어로 작성되어야 한다.
 - 가상 컴퓨터: 하드웨어의 용량 제한이 없는 RAM, 폰 노이만 구조를 따름
 - 가상 언어: 실제 프로그래밍 언어보다 간단하고 융통성 있음. 
 - 가상 코드: 가상 언어로 작성된 코드로, 의사 코드(Pseudo Code)라고도 함.

2. 최악의 경우 입력을 가정해 알고리즘의 수행 시간을 측정한다. - 최악의 수행 시간 T(n)

3. 알고리즘의 실제 수행 시간 = 연산 횟수 X 상수

 

2. 시간 복잡도 분석

 시간 복잡도를 어떻게 분석할 수 있을까? 카드 놀이에서의 삽입 정렬을 예로 들어보자.

 

• 테이블에 카드가 뒤집힌 채 쌓여 있고, 가장 위의 카드를 한 장씩 가져와 정렬하고자 한다.
• 왼손에 들고 있는 카드와 앞에서 한 장씩 비교해 정렬된 위치를 찾는다.
• 따라서 왼손에는 항상 카드가 정렬되어 있고 이 카드는 원래 테이블에 쌓여 있던 카드의 윗쪽에 있던 카드이다.
• 이 과정을 테이블에 쌓여 있는 모든 카드에 대해 반복하면 전체 카드가 정렬된다.

이제 이러한 상황에서 삽입 정렬에 대한 가상 코드를 작성해보았다.

INSERTION-SORT(A)					# 주의: index가 1부터 시작되는 것으로 가정되어 있음

for j = 2 to A:length
	key = A[j]
	// Insert A[j] into the sorted sequence A[1 .. j - 1]
	i = j - 1
	while i > 0 and A[i] > key
		A[i + 1] = A[i]
		i = i - 1
	A[i + 1] = key

 이 코드를 실행할 때 최악의 수행 시간은 아래와 같을 것이다.

INSERTION-SORT(A)					# cost: times

for j = 2 to A:length					# c1: n
	key = A[j]					# c2: n-1
	// Insert A[j] ~				# 0: n-1
	i = j - 1					# c4: n-1
	while i > 0 and A[i] > key			# c5: σ 𝑗=2 to n tj (tj = j)
		A[i + 1] = A[i]				# c6: σ 𝑗=2 to n (tj-1) (tj = j)
		i = i - 1				# c7: σ 𝑗=2 to n (tj-1) (tj = j)
	A[i + 1] = key					# c8: n-1

즉, 삽입 정렬에서 알고리즘의 수행 시간을 간단히 정리하면 다음과 같을 것이다.

t_j = ∑ⁿ_j=2 j = n(n+1)/2 - 1 ∑ⁿ_j=2 (j-1) = ∑^n-1_j=1 j = n(n-1)/2 이므로

T(n) = (c5/2 + c6/2 + c7/2)n² + (c1 + c2 + c4 + c5/2 - c6/2 - c7/2 + c8)n
- (c2 + c4 + c5 + c8)

 

3. 점근적 표기법

 연산의 횟수를 정확히 세는 건 귀찮고 까다로운 편이기 때문에 시간 복잡도를 추상화하거나, 추상화한 것을 단순화한다. 이것을 점근적 표기법(Asymptotic Notation)이라 한다.

추상화	추상화의 단순화
T(n) = an2 + bn + c a = (c5/2 + c6/2 + c7/2) b = (c1 + c2 + c4 + c5/2 - c6/2 - c7/2 + c8) c = - (c2 + c4 + c5 + c8) cost를 추상화함	O(n2 ) Rate of growth of f(n): 입력의 크기 n에 대해 수행 시간이 증가하는 정도, 최고 차수 항만 남기고 나머지 생략 Rate of growth가 중요

다음 게시글에서는 Big-O 표기법을 다룬다!