[자료구조] 02. 성능분석

본 내용은 필자가 학부 자료구조 수업내용을 공부하기 위해 정리한 것임을 알려드립니다.

2-1. 성능이란 무엇인가?

어떤 자료구조가 좋은 자료구조인지 쉽게 생각해보려면 내가 여러 지도 앱에서 원하는 경로를 검색할 때를 생각해보면 편하다. 만약 카카오 맵 앱에서 서울역부터 집까지 가는 경로를 검색할 때는 0.1초가 걸리고 네이버 지도 앱에서 동일한 경로를 검색할 때는 0.2초가 걸린다고 가정하자. (물론 예시일 뿐 네이버 앱이 안좋은 서비스라는 것은 아니다.)

동일한 입력(출발지: 서울역, 도착지: 우리 집)을 주었을 때 빠른 시간 내에 정답(가장 빠른 경로)을 출력하는 앱이 가장 좋은 앱이 되고, 카카오 맵 앱은 좋은 자료구조로 짜여있다고 말할 수 있다. 결과적으로 성능이 좋다

• (재차 강조하지만 네이버 지도 앱을 비하하려는 목적이 아니다.)

그럼 성능이란 무엇일까?

• 성능(Performance) 또는 효율(Efficient)이라고 말할 수 있다.
• 동일한 성과(Soluton)를 도출하기 위해서 요구되는 자원(Resource)의 크기
• Performance = solution / resource

효과적(effective)이란

• 투입하는 자원(Resource)이 같을 때 얼마나 많은 solution을 도출하는가?

성능의 세가지 측면

• 최선의 경우 (Best Case)
• 평균의 경우 (Average Case)
• 최악의 경우 (Worst Case)
  • 시스템에 과도한 입력(사용자의 요청)이 들어와도 적어도 ‘해당 시간’에 처리한다.
  • '보장'의 의미

성능은 솔루션/자원이다. 그 중 분모에 해당하는 자원(리소스)은 컴퓨터의 자원을 뜻하는데,

컴퓨터의 자원이라 함은 메모리와 CPU가 있다. 무어의 법칙의 한계가 올 정도로 기술은 급속도로 변화되면서 공정 세밀화와 실리콘 기반 반도체에 한계가 찾아왔다.

20nm 이후로는 기술적 구현 측면보다는 경제성의 측면에서 무어의 법칙이 멈출거라고 보는 전문가들이 많기 때문에 CPU의 성능은 좋아져도 가격이 어마무시하게 뛰게 될것이다. 반대로 메모리는 용량은 기하급수적으로 커지고 가격은 점점 싸지고 있다.

공간 복잡도 (Space-Complexity)

“특정한 프로그램을 수행하는 데 요구되는 메모리”

• 공학적으로 생각해볼 때 메모리의 Cost는 낮아지고 용량은 커지고 있으므로 공간복잡도는 성능을 측정할 때 고려할 요소가 되지 않는다.

시간 복잡도 (Time-Complexity)

“특정한 프로그램을 수행하는 데 요구되는 시간”

• 시간복잡도로 시스템의 성능을 측정한다.

---

2-2. 점근적 분석법 (Asymptotic Complexity)

• 성능은 입력의 크기에 따라에 결정됨
• 실제로 프로그램의 성능을 공정하게 판단하기 위해서는 입력의 크기만으로 판단한다.
• n : 입력의 크기
• 시간 복잡도를 n(입력)의 함수로 표현 : f(n)
• 시간 복잡도는 매우 큰 입력에 대해서 측정한다.
  

동일한 크기의 입력 처리 시 같은 성능 함수 g(n)을 통한 f(n)의 성능 표현

• g(n) >= f(n)
• g(n) 함수가 f(n) 함수보다 증가율이 크다면 g(n)은 f(n)보다 성능이 나쁘다.
• g(n)은 f(n)보다 시간이 더 많이 걸린다.
• 최악의 경우에도 f(n)은 g(n)보다 좋다.
• f(n)의 upper bound(상한)는 g(n)이다.
• f(n)의 최악의 경우는 g(n)이다.