자료구조(2) - 알고리즘 성능 분석

이제 어떤 자료구조가 사용하기 좋은 자료구조인지 판단하는 방법을 알아보자

---

 

자료구조의 효율성은 자료구조에 대해 수행되는 연산의 수행 시간으로 측정할 수 있습니다.

자료구조에 대한 수행 시간 측정 방식은 알고리즘의 성능을 측정하는 방식과 동일합니다.

 

☞ 알고리즘 성능 측정 방식

수행 시간을 나타내는 시간 복잡도(Time Complexity)와 수행 동안 사용되는 메모리 공간의 크기를 나타내는 공간 복잡도(Space Complexity)에 기반하여 분석을 합니다.

※ 대부분의 경우 시간 복잡도만 사용하여 분석(공간 복잡도 사용 X) 

 

"시간 복잡도 = 연산 횟수"로 볼 수 있다.

연산들의 수행횟수는 주어지는 입력의 개수 n에 따라 값이 변하는 상수로 고정된 숫자가 아니라 n에 대한 함수가 된다.

→ 연산의 수를 입력의 개수 n의 함수로 나타낸 것을 시간복잡도 함수라고 하고 T(n) 이라고 표기

---

예시) 양의 정수 n을 n번 더하는 문제

알고리즘 A : n x n

알고리즘 B : n + n + n+ ... + n

알고리즘 C : 1을 n x n 번 더하기

알고리즘 A	알고리즘 B	알고리즘 C
sum <- n*n;	for i <- 1 to n do                          sum <- sum +n;	for i <- 1 to n do                       for j<-1 to n do                           sum <- sum +1;

	알고리즘 A	알고리즘 B	알고리즘 C
대입 연산	1	n	n*n
덧셈 연산		n	n*n
곱셈 연산	1
나눗셈 연산
전체 연산 수	2	2n	2n²
T(n) 표기	T(1)	T(n)	T(n²)

 

예시 처럼 알고리즘들을 비교하여 효율적인 알고리즘을 파악할 수 있다.