[자료구조] 알고리즘의 성능평가와 ADT

공간 복잡도(Space Complexity)

: 알고리즘의 메모리 사용량을 평가하기 위한 척도.

 

시간 복잡도(Time Complexity)

: 알고리즘의 수행속도를 평가하기 위한 척도. 

데이터 수의 증가에 따른 연산횟수의 변화 정도를 판단할 수 있다.

최악의 경우를 기준으로 핵심 연산의 횟수를 계산한다. 일반적으로 '빅-오 표기법'을 이용한다.

 

빅-오 표기법(Big-Oh Notation)

데이터 수의 증가에 따른 연산횟수 증가율의 상한선을 표현하는 표기법이다.
▶증명 : "두 개의 함수 f(n)과 g(n)이 주어졌을 때, 모든 n≥K에 대하여 f(n)≤Cg(n)을 만족하는 두 개의 상수 C, K가 존재하면, f(n)의 빅-오는 O(g(n))이다."

 

대표적인 빅-오 표기들의 성능 비교(오른쪽으로 갈 수록 성능하락)
O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(n^3) < O(2^n)

 

추상 자료형(ADT, Abstract Data Type)

: 알고리즘이 가지는 순수한 기능만을 나열한 것.

ex)지갑에 대한 추상 자료형 : 동전의 삽입, 동전의 추출, 지폐의 삽입, 지폐의 추출, 카드의 삽입, 카드의 추출