자료구조의 효율성은 자료구조에 대해 수행되는 연산의 수행시간으로 측정할 수 있다. 자료구조에 대한 연산 수행시간 측정 방식은 알고리즘의 성능을 측정하는 방식과 동일하다.
알고리즘의 성능은 수행시간을 나타내는 시간복잡도(Time Complexity) 와 알고리즘이 수행되는 동안 사용되는 메모리 공간의 크기를 나타내는 공간복잡도(Space Complexity) 에 기반하여 분석한다. 대부분의 경우 시간복잡도만을 사용하여 알고리즘의 성능을 분석하는데, 주어진 문제를 해결하기 위한 대부분의 알고리즘들이 비슷한 크기의 메모리 공간을 사용하기 때문이다.
하지만 실제 측정된 시간으로 알고리즘의 성능을 객관적으로 평가하는 데는 한계가 존재한다. 언어의 종류, 컴퓨터의 성능, 프로그래머의 숙련도 등이 변수로 작용하기 때문이다.
따라서 알고리즘의 시간복잡도는 알고리즘이 실행되는 동안에 사용된 기본적인 연산 횟수를 입력 크기의 함수로 나타낸다. 기본 연산(Elementary Operation)이란 탐색, 삽입이나 삭제와 같은 연산이 아닌, 데이터간 크기 비교, 데이터 읽기 및 갱신, 숫자 계산 등과 같은 단순한 연산을 의미한다. 알고리즘의 수행시간은 다음과 같이 4가지의 방법으로 분석할 수 있다.
- 최악경우 분석(Worst-case Analysis)
- 평균경우 분석(Average-case Analysis)
- 최선경우 분석(Best-case Analysis)
- 상각분석(Amortized Analysis, 분할 상환하다, 보상하여 갚아주다.)
일반적으로는 알고리즘의 수행시간을 최악경우 분석으로 표현한다. 최악경우 분석은 "어떤 입력이 주어지더라도 알고리즘의 수행시간이 얼마 이상은 넘지 않느다"라는 상한(Upper Bound)의 의미를 갖는다. 평균경우 분석은 입력의 확률 분포를 가정하여 분석하는데, 일반적으로 균등분포(Uniform Distribution)를 가정한다. 즉, 입력이 무작위로 주어진다고 가정한다. 최선경우 분석은 거의 사용되지 않지만 최적 알고리즘을 찾는데 활용되기도 한다. 상각분석은 일련의 연산을 수행하여 연산 횟수를 합하고 이를 연산 횟수로 나누어 수행시간을 분석하는 방법으로서 특정한 상황에서 최악경우 분석보다 현실적인 분석 방법이다.