좋은 알고리즘을 평가하는 요소(시간복잡도, 공간복잡도)

 

좋은 알고리즘을 평가하는 요소(시간복잡도, 공간복잡도)

 

지금 잠시 차🚗를 새로 구입한다고 생각해보세요. 

 

1) 집에서 회사까지 이동만 할 수 있는 차

2) 집에서 회사까지 소음 적고, 연비 좋고, 오르막 길에서 기를 쓰지 않아도 속도내며 이동할 수 있는 차 

 

둘 중에 어느 차를 선택하실 겁니까?

아마 대부분이 2번을 고를 겁니다. 

우리는 잘 동작하는 것은 물론이고 성능까지 보장받기 원하니까요. 

---

알고리즘에도 똑같이 적용됩니다. 그저 잘 동작하는 자료구조와 알고리즘(이하 '알고리즘'으로 총칭)을 찾는다면 필요한 기능만 보면 되겠죠. 하지만 성능도 따지고 싶기 때문에 알고리즘을 분석할 줄 알아야 합니다.  크게 두 가지 요소가 있습니다. 

 

특정 상황에서 

1) 어떤 알고리즘이 더 빠른가?

2) 어떤 알고리즘이 메모리를 적게 쓰는가?

 

 

네, 여기서 나오는 개념이 

1) 어떤 알고리즘이 더 빠른가?

시간 복잡도 Time Complexity - 속도

2) 어떤 알고리즘이 메모리를 적게 쓰는가?

공간 복잡도 Space Complexity - 메모리 사용량

입니다.

 

특정 상황을 제외하고 일반적으로 속도를 따지기 때문에 이 글에서는 시간복잡도만 다루겠습니다.

---

알고리즘의 시간 복잡도 즉, 속도를 어떻게 평가할 수 있을까요? 결과값이 나올 때까지 시간을 재면 될까요?

아니죠. 연산의 횟수를 통해서 수행속도를 평가할 수 있습니다.

연산의 횟수가 많으면 느린 알고리즘, 연산의 횟수가 적으면 빠른 알고리즘으로 볼 수 있죠. 

 

또한 둘 이상의 알고리즘을 비교하기 위해 식을 구성하는데요.

데이터의 수 n에 대한 연산횟수의 함수 T(n)를 구성합니다. 

이 말은 즉슨 데이터의 수를 함수에 넣으면 연산의 횟수가 바로 계산이 되는 식을 만들겠다는 겁니다. 

그래서 데이터 수의 증가에 따른 연산횟수의 변화 정도를 파악할 수 있죠. 

 

 

---

 

이해를 돕기 위해 아래 그래프에 나오는 두 알고리즘를 비교해보겠습니다.

 

동일한 기능을 제공하는 알고리즘 두 개가 있습니다. 

 

 

 

📣 데이터 수가 적을 때는 알고리즘B가 빠릅니다. 

📣 데이터 수가 많아지면 알고리즘A가 훨씬 더 빨라집니다. 

 

여기서 나올 수 있는 결론

: 그럼 데이터 수가 적을 B를  많을 때는 A를 쓰면 되겠네요. 

 

음..나쁘지 않은 판단이기는 한데 알고리즘에서 중요한 요소는 위에서 언급한 연산의 횟수였다는 점을 다시 생각해봅시다.

따져봐야할 점은 데이터의 수가 많아짐에 따른 연산횟수의 증가 정도입니다. 

 

즉 알고리즘 A가 훨씬 좋다고 할 수 있습니다. 

---

그럼 알고리즘B는 그냥 없애면 될까요?

 

아닙니다. 

안정적인 성능을 보장하는 알고리즘A 같은 경우는 B에 비해 구현하기 까다롭습니다. 그래서 성능에 덜 민감한 경우라면 B를 사용하기도 하죠. 따라서 알고리즘은 상황에 맞게 선택하면 됩니다.

 

 

 

 

------------------------------

알고리즘 개념 모아보기 

------------------------------