[자료구조] 수행시간 측정

이전 정리글 ↓

[자료구조] 5. 포인터(Pointer)

앞서 순환구조에 대해 알아봤는데, 이런 알고리즘들의 성능은 어떻게 될까? 그리고 어떤 알고리즘이 가장 우수할까?

 

알고리즘의 복잡도 분석하기

 

출처 : https://pin.it/7cbeere

 

여러분이 오랜만에 장을 보러 시내에 나간다고 가정하자.

방법이 여러가지 있을 것이다.

 

1) 버스를 타는 방법

2) 지하철을 타는 방법

3) 택시를 타는 방법

4) 자차를 이용하는 방법

 

우선 어떤 알고리즘이 좋다 안좋다 말하기 전에, 무엇을 기준으로 평가할지 정해야 한다.

가격이 저렴한 방법, 최단시간에 가는 방법. 혹은 둘다 평균이거나 한쪽이 지나치게 높지 않아야 한다는 등의 기준.

 

알고리즘의 복잡도를 분석하는 것은, 

도로의 교통상황이나 대중교통의 가격, 택시의 기본요금 등 여러 요소를 고려해 

여러분이 정한 기준에 어떤 방법이 적합한지를 고르는 것이랑 같다. 

 

---

시간 복잡도 함수

알고리즘 분석엔 2가지 관점이 있다.

 

1) 알고리즘의 수행시간 = 시간복잡도(Time complexity)

2) 알고리즘을 수행하는 데 필요로 하는 공간 = 공간 복잡도(Space Complexity)

 

대개는 시간복잡도를 기준으로 산정하고 말한다. 

평가항목이 수행능력이다보니, 보통은 수행하는 데에 걸리는 시간을 기준을 잡기 때문이다.

 

예를 들어보자.

양의 정수 n을 n번 더하는 문제를 3개의 알고리즘으로 축약해보자.

	알고리즘 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;
해석	n*n을 계산	n을 n번 더함	1을 n * n번 더함
대입연산	1	n	n * n
덧셈연산		n	n * n
곱셉연산	1
나눗셈연산
전체 연산 수	2	2n	2n^2