성능과 점근적 분석법
🗃️ 강의
K-MOOC 자료구조
성능이란 무엇인가?
🔸 성능 또는 효율 : 일 잘함 + 소요 시간 적음
같은 기능을 가진 어플이어도 처리 성능이 빠른 어플이 성능이 좋다고 할 수 있다. (즉, 요구하는 자원을 최소로 사용)
🔸 성능
- 성능 또는 효율
- 동일한 성과를 도출하기 위해서 요구되는 자원의 크기는 다음과 같다. (성과를 자원으로 나눈 것)
🔸 성능의 세가지 측면
- 최선의 경우
- 평균의 경우
- 최악의 경우
집에서 학교까지 가는 경우(등교 시간 9시)를 성능으로 간단하게 설명해 보자!
▶ 최선 : 최대한 빨리 도착해! (1시간 전 도착)
▶ 평균 : 학교에 보통 이 시간에 도착해! (30분 전 도착)
▶ 최악 : 아무리 늦어도 지각은 안 한다! (1분 전 도착)
최악의 경우는 보장의 의미를 가지고 있다. 그래서 성능을 이야기할 경우 반드시 최악의 경우를 정하고 성능을 말해야 한다.
🔸 자원의 두 가지 측면 : 공간과 시간
- 공간 복잡도 : 특정한 프로그램을 수행하는 데 요구되는 메모리
- 시간 복잡도 : 특정한 프로그램을 수행하는 데 요구되는 시간
컴퓨터에서 메모리가 공간 복잡도이면 CPU는 시간 복잡도이다.
메모리의 성능이 뛰어나도 CPU 처리 능력이 뒤처지면 무용지물이다. 마치 로스트 아크를 설치할 공간은 있지만 실행할 능력이 안 되는 것처럼..ㅠㅠ
즉, 시간이 공간보다 더 소중한 자원이다.
점근적 분석법
🔸 성능은 입력의 크기에 따라 결정된다.
입력의 크기는 n, 시간 복잡도를 n의 함수로 표현하면 f(n)으로 작성하면 다음과 같다.
- 입력이 증가하면 시간도 증가 ▶ 일반적
- 입력이 증가해도 시간은 일정 ▶ 최고
- 입력이 증가해도 시간은 감소 ▶ 없음
🔸 점근적 분석법
- 시간 복잡도는 매우 큰 입력에 대해서 측정한다.
작은 입력에서는 의미가 없기 때문에 점근적인 분석을 하기 위해선 매우 큰 입력을 가정하고 측정해야한다.
🔸 g(n)을 이용한 f(n)의 성능 표현
g(n)은 항상f(n)보다 커야 한다.g(n)은f(n)보다 성능이 나쁨- 최악의 경우에도
f(n)은g(n)보다 좋음 f(n)의 상한은g(n)f(n)≤g(n)g(n)은f(n)의 성능을 나타내는 척도로 사용- 많이 사용되는 표준 함수 사용 ▶ 1, n, n^2, 2^n, log n
미지의 공간🌙