자료구조 2주차 - 자료구조를 배우기 위한 준비

서울여대 이병걸 교수님의 자료구조 수업을 들은 뒤 복습용으로 작성한 글입니다.

교재: 파이썬과 함께하는 자료구조의 이해

 

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

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

데이터를 정돈하는 목적은 프로그램에서 저장하는 데이터에 대해 탐색, 삽입, 삭제 등의 연산을 효율적으로 수행하기 위함이다. 그래서 자료구조를 설계할 때 데이터와 데이터 관련 연산들도 함께 고려하여 설계 해야 한다.

 

추상 데이터 타입은 데이터 저장 구조 생성 후 실제 저장되는 데이터를 처리하기 위한 연산을 정의하는 관계를 정형화  한 것으로 데이터와 그 데이터에 대한 추상적* 연산들로 구성된다.

 

*추상적: 연산을 구체적으로 어떻게 구현해야 한다는 세부 명세를 포함하고 있지 않다는 의미

 

추상 데이터타입을 구체적(실제 프로그램)으로 구현한 것을 자료구조라고 하며, 자주 사용되는 자료구조의 예로 리스트, 연결리스트, 스택, 큐, 다양한 트리, 해시테이블, 그래프 등이 있다.

특정 문제를 해결하기 위해 이용해 알고리즘을 설계할 때 추상데이터타입에 기반하여 효율적으로 자료구조를 만들어야 효율적인 알고리즘 설계가 가능하다.

2. 수행시간의 분석

자료구조의 효율성은 연산의 수행시간으로 측정한다. 측정 방식은 알고리즘의 성능 측정 방식과 동일한데, 수행 시간을 나타내는 시간복잡도와 알고리즘이 수행되는 동안 사용되는 메모리 공간의 크기를 나타내는 공간복잡도 두가지가 있다.

과거에는 공간복잡도 또한 이용하였으나 최근의 컴퓨터들은 성능이 비슷하여 알고리즘이 사용하는 메모리 공간의 크기가 비슷하다. 그래서 대부분의 경우 시간복잡도만 사용하여 성능을 분석한다.

 

같은 알고리즘이라도 sw, hw, 프로그래밍 언어, 코드환경에 따라 알고리즘 실행 성능이 달라진다. 이때 알고리즘의 수행시간을 측정하는 경우 상황에 따라 달라지기 때문에 객관적으로 평가할 기준이 필요하다. 이를 위해 가상컴퓨터에서 가상언어, 가상코드를 기준으로 동일한 조건에서 비교를 할 필요가 있다. 가상언어(코드)는 가상 컴퓨터의 기본 언어를 가정한 것으로 기본, 조건, 반복, 함수 등의 연산을 표현하는 언어(코드)이다. 다른 용어로 유사언어, 수도코드(Pseudo Code(Language))라고 한다. 여기서 기본 연산은 배정(대입)연산, 산술연산, 비교연산, 논리연산을 주로 이야기한다. 

 

시간복잡도를 통한 성능 분석은 총 세가지 종류가 있다. 최악의 경우분석, 평균경우 분석, 최선의 경우 분석이 있으며, 입력에 따라 수행시간에 차이가 있을 수 있기 때문에 일반적으로 수행시간은 최악의 경우 분석으로 표현한다. 최악의 경우 분석은 '어떤 입력이 주어지더라도 알고리즘의 수행시간이 얼마 이상은 넘지 않는다'는 상한(Upper Bound)를 의미하며 뒤에 나올 표기법으로 봤을 때는 O-표기법(빅오 표기법)으로 나타낼 수 있다. 평균 경우 분석은 입력의 확률분포를 가정하여 분석하는데, 일반적으로 균등분포(Uniform Distribution)를 가정하며 표기법으로 봤을 때 θ-표기법(세타 표기법)으로 나타낼 수 있다. 최선의 경우 분석은 가장 빠른 수행시간을 분석하는 것으로 거의 사용되지 않으나 최적 알고리즘을 찾는데 활용되기도 한다. 점근 표기법으로 나타냈을 때 Ω-표기법(빅오메가 표기법)으로 나타낼 수 있다.

3. 수행시간의 점근 표기법

점근 표기법이란 기본 연산 횟수를 입력 크기에 대한 함수로 표현하기 위한 방법으로 주로 여러개의 항을 가진 다항식으로 표현한다. 위에서 이야기한 것처럼 점근 표기법은 O-표기법, θ-표기법, Ω-표기법 세종류가 있다. 

 

1) O-표기법

모든 N>=N0에 대해서 f(N)<=cg(N)이 성립하는 양의 상수 c와 N0이 존재하면, f(N)=O(g(N))이다.

예를 들어 f(N)=2N^2+3N+5 라는 식이 있을 때 O-표기법으로 나타내보자. 먼저 f(N)에서 최고차항만 취한 뒤 그 항의 계수를 제거한다. 그리고 c값은 2보다 큰 4로 택한다. 이때 2N^2+3N+5 <= 4N^2이 성립하므로 f(N)=O(N^2)이다. 이때 g(N)을 f(N)의 상한(upper bound)라고 한다.

 

이때 g(N)은 정의를 만족하는 차수가 가장 낮은 함수를 선택하는 것이 바람직한데, 그 이유는 과장된 표현을 피하기 위함이다. 

 

2) Ω-표기법

모든 N>=N0에 대해서 f(N)>=cg(N)이 성립하는 양의 상수 c와 N0이 존재하면, f(N)=Ω(g(N))이다.

위의 예시처럼 f(N)=2N^2+3N+5 라는 식이 있을 때 Ω-표기법으로 나타내보자. 마찬가지로 먼저 f(N)에서 최고차항만 취한 뒤 그 항의 계수를 제거한다. 그리고 c값은 f(N)의 최고차수보다 작은 수인 1로 택한다. 이때 2N^2+3N+5 <= N^2이 성립하므로 f(N)=Ω(N^2)이다. 이때 g(N)을 f(N)의 하한(lower bound)라고 한다.

 

3) θ-표기법

모든 N>=N0에 대해서 cg(N)>=f(N)>=cg(N)이 성립하는 양의 상수 c와 N0이 존재하면, f(N)=θ(g(N)) 이다.

이는 수행시간의 O-표기와 Ω-표기가 동일한 경우 사용되는 표기법이다. 위와 같은 f(N)식과 함께 봤을 때 

2N^2+3N+5=Ω(N^2)=O(N^2) 이므로 2N^2+3N+5=θ(N^2)이다. 이때 2N^2+3N+5와 N^2은 유사한 증가율을 가진다. 

 

4) 자주사용되는 함수의 O-표기

알고리즘의 수행시간은 주로 O-표기를 사용하는데, 보다 정확한 표현을 위해 θ-표기를 사용하기도 한다. 

아래의 내용들은 자주 사용되는 O-표기이다.

• O(1): 상수시간(Constant Time), N이 변하더라도 항상 일정한 시간이 소요된다는 의미
• O(logN): 로그(대수)시간(Logarithmic Time)
• O(NlogN): 로그 선형시간(Log-linear Time)
• O(N^k): 다항식 시간(Polynomial Time)
  • O(N^2): 제곱시간(Quadratic Time)  
  • O(N^3): 세제곱시간(Cubic Time)
  • O(N): 선형시간(Linear Time)
• O(2^N): 지수시간(Exponential Time)