자료구조 준비

자료구조와 추상데이터 타입

자료구조(Data Structure)는 일련의 동일한 타입의 데이터를 정돈하여 저장한 구성체를 의미한다.

추상데이터타입(Abstract Data Type)은 데이터와 그 데이터에 대한 추상적인 연산들로써 구성된다. 또는, 데이터의 집합과 데이터에 가해지는 연산들의 수학적인 명세이다.

자료구조는 자료를 효율적으로 활용하기 위한 자료들의 집합이다. 예로는 리스트, 연결리스트, 스택, 큐, 트리, 해시테이블, 그래프 등이 있다.

수행시간의 분석

자료구조의 효율성은 자료구조에 대해 수행되는 연산의 수행시간으로 측정할 수 있다. 측정 방식은 알고리즘의 경우와 동일하다.

알고리즘 성능은 수행시간을 나타내는 시간복잡도(Time Complexity)와 알고리즘이 수행하는 동안 사용되는 메모리 공간의 크기를 나타내는 공간복잡도(Space Complexity)에 기반하여 분석한다.

보통 시간 복잡도로 측정하는데 이는 언어의 종류, 컴퓨터의 성능 등의 요인이 관여하기 때문에 정확하지 않다. 따라서, 알고리즘의 시간복잡도는 알고리즘이 실행되는 동안에 사용된 기본적인 연산 횟수를 입력 크기의 함수로 나타낸다. 이때 기본 연산이란 데이터간 크기 비교, 데이터의 읽기 및 갱신, 숫자 계산 등과 같은 단순한 연산을 의미한다.

알고리즘의 수행시간(시간복잡도)은 다음과 같이 세 가지의 방법으로 분석한다.

1. 최악경우 분석(Worst-case Analysis)
2. 평균경우 분석(Average-case Analysis)
3. 최선경우 분석(Best-case Analysis)

일반적으로 알고리즘 수행시간은 최악경우 분석으로 표현한다. 이는 어떠한 일이 있어도 수행시간이 이를 넘기지 않는다는 '상한(Upper)'의 의미를 갖는다.

수행시간의 점근표기법

수행시간은 알고리즘이 수행하는 기본 연산 횟수를 입력 크기에 대한 함수로 표현한 것이다. 이러한 함수는 주로 여러 개의 항을 가지는 다항식으로 표현되므로 이를 입력의 크기에 대한 함수로 표현하기 위해 점근 표기법(Asymptotic Notation)이 사용된다.

점근표기법에 대해서는 여기 참조

쉽게 말해, 점근표기법에 의하면 주어진 함수의 최고차항만 고려한다. 알고리즘의 수행시간은 대개 O-표기(Big-Oh)를 이용하지만, 보다 정확히 표현하기 위해 Θ-표기(Theta)를 사용하기도 한다. 아래는 자주 사용되는 함수의 O-표기이다.

• O(1) 상수시간(Constant Time)
• O(logN) 로그(대수)시간(Logarithmic Time)
• O(N) 선형시간(Linear Time)
• O(NlogN) 로그선형시간(Log-Linear Time)
• O($N^2$) 제곱시간(Quadratic Time)
• O($N^3$) 세제곱시간(Cubic Time)
• O($2^N$) 지수시간(Exponential Time)
  

내용 출처 : 파이썬과 함께하는 자료구조의 이해(양성봉 저)