Data Structure and Algorithm Introduction

Data Structure

Data Structure는 데이터를 효율적으로 저장하고 관리하기 위한 특별한 포맷이다. Array, File, Linked list, Stack, Queue, Tree, Graph 등이 있다.

자료 구조는 element의 구조에 따라 두 종류로 분류된다.

Linear data structure(선형 자료구조)

element 들이 sequential order로 접근되지만 모든 elemnt가 순차적으로 저장되지는 않는다.

ex) linked list, stack, queue

Non-linear data structure(비선형 자료구조)

elment 들이 non-linear order로 저장/접근된다.

ex) tree and graph

 

Abstract Data Types(ADTs)

ADTs는 컴퓨터 과학에서 데이터의 선언과 연산의 선언으로 구성된다. 일반적으로 사용되는 ADTs로 Linked Lists, Stacks, Queues, Priority Queues, Binary Trees, Dic tionaries, Disjoint Sets (Union a nd Find), Hash Tables, Graphs 등이 있다.

예를 들어, Stack은 LIFO 메커니즘을 이용해 자료를 저장하며, push, pop, size, top 등의 연산자를 가진다.

ADTs는 실제로 사용할 때 구현이 되기 때문에, 구체적인 구현이 필요가 없다. 

 

Algorithm

알고리즘이란 주어진 문제를 해결하기 위한 step-by-step instructions 이다.

컴퓨터 과학에서 같은 문제를 해결하는데 여러가지 알고리즘이 사용 가능하다. 알고리즘의 분석은 어떤 알고리즘이 시간과 공간을 가장 효과적으로 사용하는지 결정하는 데 도움을 주며 알고리즘 분석의 목표는 알고리즘의 실행 시간과 다른 요소들(메모리, 개발자의 노력 등)을 비교하는 것이다. 

알고리즘 분석의 종류에는 다음 세 가지가 있다.

• Worst case : 알고리즘이 가장 느리게 실행되는 입력. 가장 오랜 시간이 걸리는 알고리즘의 입력
• Best case : 알고리즘이 가장 빠르게 실행되는 입력. 가장 적은 시간이 걸리는 알고리즘의 입력
• Average case : 임의의 입력이라 가정한다. 알고리즘의 실행 시간에 대한 예측을 제공한다.

 

Rate of Growth

알고리즘을 비교하기 위한 객관적인 수치로 성장률(Rate of Growth)를 사용한다. 성장률이란 함수의 입력에 따른 실행 시간 증가량의 비율을 뜻한다. 함수의 형태로 나타낼 수 있으며 상대적으로 중요하지 않은 낮은 차수는 무시한다. 

예를들어, n^4 + 2*n^2 + 100*n + 500 은 n^4이 가장 높은 차수이기 때문에 n^4 으로 근사한다.

다음 표는 대표적인 growth rate 들이다. 

 

Asymptotic Notation

best, average, worst cases에 대해 upper bound(상한)와 lower bound(하한)를 알아야 한다. 이러한 bound를 표현하기 위한 방법으로 Asymptotic Notation(점근 표기법)을 사용한다.  Asymptotic Notation의 종류로 Big-Ο Notation, Omega-Ω Notation, Theta-Θ Notation 이 있다. 

 

Big-O Notation

Big-Ο Notation은 주어진 함수에 tight upper bound 를 부여한다. 적당히 큰 n에서 f(n) 의 upper bound가 g(n) 이라는 뜻으로 f(n) = O(g(n))으로 표현된다. 정확한 정의는 다음과 같다.

[추가예정]

예를 들어 f(n) = n^4 + 100*n^2 + 50 일때, 0 <= f(n) <= 2*n^4 for all n >= 11 이므로,g(n) = n^4 이다.

따라서 f(n) = Ο(n^4) with c >=2 and n0 = 11 로 표현한다. 

 

Omega-Ω Notation

Big-Ο Notation과 비슷하지만, 주어진 함수에 대해 tight lower bound를 부여한다. 적당히 큰 n에서 f(n)의 lower bound가 g(n)이라는 뜻으로 f(n) = Ω (g(n))으로 표현된다. 정확한 정의는 다음과 같다.

[추가예정]

예를들어 f(n) = 5*n^2 일때, f(n) >= n^2 >= 0 for all n>= 1 이므로, g(n) = n^2 이다.

따라서 f(n) = Ω (n^2) with c = 1 and n0 = 1 로 표현한다.

 

Theta-Θ Notation

주어진 함수의 upper bound와 lower bound가 같은지 결정한다. average running time은 항상 upper bound 와 lower bound 사이에 존재한다. upper bound와 lower bound가 같다면 Theta-Θ Notation 또한 같은 성장률을 가지고, 다르다면 Theta-Θ Notation 은 다른 값을 가지게 되어 모든 경우의 복잡도를 고려해야 한다. 정확한 정의는 다음과 같다.

[추가예정]

예를 들어  f(n) = n^2/2 - n/2 일때, n^2/5 <= f(n) <= n^2 for all n>=1 이므로, g(n) = n^2 이다.

따라서 f(n) = Θ(n^2) with c1 = 1/5, c2 = 1 and n0 = 1 로 표현한다.

 

Guidelines for Asymptotic Analysis

알고리즘의 실행시간을 결정하는 일반적인 규칙들은 다음과 같다.

• Loop : 루프의 크기
• Nested loops : 모든 루프의 크기들의 곱
• Consecutive statements : 모든 statement의 complexity의 합
• if-then-else : Worst-case 에 대한 실행 시간으로 모든 경우에 대한 complexity의 합
• Logarithmic complexity : 문제의 크기를 분수(usually by 1/2)로 줄이는데 일정한 시간이 걸린다면 O(logn)이다. 

 

참조
Data Structure and Algorithmic Thinking with Python Data Structure and Algorithmic Puzzles ( PDFDrive )