[자료구조] 자료구조와 O-표기

자료구조란?

일련의 동일한 타입의 데이터를 정돈하여 저장한 구성체.

추상 데이터타입(ADT)

자료구조를 구현할 때, 데이터 저장할 구조를 생성한 이후, 실제 저장되는 데이터를 처리하기 위한 연산을 정의해야 하는데, 이러한 관계를 정형화시킨 개념
[ADT]

public interface Intf{ }

[자료구조]

public class ds implement Intf {}

즉, 추상데이터 < 자료구조 < 알고리즘 포함관계로 정의할 수 있다.

수행시간

시간복잡도와 공간복잡도에 기반하여 분석하지만, 대개 시간복잡도만을 사용하여 성능을 분석함.
최악경우분석, 평균경우분석, 최선경우분석, 상각분석 네가지로 나뉜다.

점근표기법

1. Big O - 최악의 경우
2. Big Ω - 최선의 경우
3. Big θ - O와 Ω를 둘 다 만족하는 경우(평균)