알고리즘 ch 1~2

알고리즘

- Computer Algorithm 알고리즘이란? 컴퓨터를 이용하여 문제를 해결하는 순서적인 절차를 만들어 놓은 것.

- 컴퓨터를 이용하여 문제를 해결하는 6단계

1) Problem: 문제 파악, 문제의 input과 output확인

2) Strategy: 전략 구성

3) Algorithm: 알고리즘 설계

Input, output에 따라 step별로 어떻게 할 것인지 설계

4) Analysis: 알고리즘 분석

   기준: correctness(정확성), time&space(효율성), optimality(최적화된 방법인가)

5) Implementation: 수행

6) Verification: 확인

- Analysis of the Algorithm 알고리즘 분석방법

1. 실험적 방식 : 실제 해당 알고리즘을 기계에서 구현하여 실행해서 결과를 얻는 방식/

  알고리즘 구현 필수, 실험에 포함되지 않는 input에 대해 알고리즘 수행 시간 모름, 수행시간 비교시 소프트웨어와 하드웨어의 스펙이 동일해야함 즉, 환경이 같아야함

2. 이론적 방식 : 실제로 구현하는 방식이 아님/

알고리즘을 상위레벨에서 서술 가능 즉 의사코드 작성해서 서술, 수행시간을 함수로 표현 가능, 모든 input 고려 가능, 소프트웨어와 하드웨어 환경에 독립적으로 수행시간 분석 가능

-> 우리가 앞으로 다룰 방식은 이론적 분석 방식이다.

이론적 분석방식 예

1) Correctness

Input(preconditions)이 output(postconditions)이 되는 과정을 증명함으로 알고리즘이 정확하게 동작함을 확인.

2) Amount of work done : Time & Space used = Complexity

시간복잡도 : 수행시간

공간복잡도 : 메모리 사용량

시간복잡도의 경우 basic operation의 횟수를 말하는데. 여기서 basic operation이란

Basic operation : 알고리즘 내의 어떤 명령문이나 명령문 군을 선정하여 알고리즘이 수행한 총 작업의 양을 이 명령문이나 명령문 군을 수행한 횟수에 비례하도록 한다. 이 명령문 또는 명령문 군을 basic operation이라 한다.

예를 들어) 정렬알고리즘 설계시, 비교연산 없이 만들 수 없으므로 비교 연산이 정렬알고리즘의 basic operation

이론적인 방식은 알고리즘 내에서 필요한 basic operation의 개수를 이용해 알고리즘의 수행 시간을 측정한다.

    

basic operation 개수 카운팅 경우

(1) Worst-case analysis : 최악의 경우에 대한 분석

(2) Average-behavior analysis : 평균 case에 대한 분석

A(n) = Pr(succ)Asucc(n) + Pr(fail)Afail(n)

: input size가 n인 문제에서 

연산 수 = 문제를 성공할 확률*성공했을 때 필요한 연산 수 + 문제를 실패할 확률*실패했을 때 필요한 연산 수

Pr(n): 인풋 사이즈 n이 발생할 확률

평균 연산 수 = [0,N]의 범위의 n에 대하여 Pr(n)*A(n)의 합.

+Space Usage And Simplicity : Time과 Space는 Tradeoff 관계(반비례관계)

+In-place algorithm : input에 대한 space 외에 O(1)만큼 space를 더 사용한 algorithm 혹은 O(log n)을 더 쓴 algorithm

+알고리즘의 Simplicity시에 장점 : correctness 증명이 쉬움, 프로그램 작성 수정 디버깅이 쉬움

3) Optimality (Simplicity)

Complexity와 실제 필요한 일의 양을 비교함으로써 효율성을 확인.

Complexity: 문제를 풀기 위한 최소한의 일의 양(연산 수)

예) n개의 수 중에서 특정 값을 찾는 문제. Complexity = n

Optimal: 가장 최적의 알고리즘. 이보다 더 뛰어난 것은 존재할 수 없음.

문제의 complexity와 알고리즘의 worst-case complexity가 같을 때 optimal algorithm.

- Asymptotic Growth Rate 

: 두 개의 함수를 비교할 때 상수나 작은 크기의 입력데이터는 무시하는 방법.

 이를 이용하여 알고리즘의 복잡도를 점근적으로 분석한다.

점근적 분석법을 통해 각 알고리즘이 주어진 데이터의 크기를 기준으로 수행시간 혹은 사용공간이 얼마나 되는지를 객관적으로 비교할 수 있다.

점근적 분석 표기법은 3가지가 있다

함수 g가 있다고 할 때

1.빅오메가 Ω(g) : g보다 같거나 빠른 함수들의 집합

      점근적 하한, 최선의 경우

2.빅세타 θ(g) : g와 같은 함수들의 집합, 점근적 평균 , O(g) ∩ W(g) 

3.빅오 O(g): g보다 같거나 빠르지 않은 함수들의 집합

       점근적 상한, 최악의 경우

알고리즘의 최악의 경우 어느정도 걸리는 지 구할때 사용 -> 주로 사용하는 방법

점근적 표기법에 대해 더 쉽게 구별하려면 limit이용하면 된다.

함수 f와 g가 있을시

값으로 비교.

< ∞ 이면 f ∈ O(g): big-O

> 0 이면 f ∈ Ω(g): big-Omega

= c and 0 < c < ∞ 이면 f ∈ θ(g): big-Theta

= 0 이면 f ∈ o(g): little oh

= ∞ 이면 f ∈ w(g): little omega

+ θ(g) 읽는법 : Big theta of g

+ f ∈ θ(g): 일때 읽는법 : f is asymptotic order g or f is order g

예시문제들

+ 빅오메가, 빅세타, 빅오의 성질

1. Transitive 이행성(전이성) : f ∈O(g) and g ∈O(h) then f ∈O(h)   

2. Reflexive 반사성 : f ∈ Q(f) 

3. Symmetric 대칭성 : f  ∈Q(g) ⇔ g  ∈Q(f)  

4. f ∈O(g)⇔ g ∈ Ω(f)  

5. O(f+g) = O(max(f,g))

+ 분류

1. O(1) = O(c) = O(0) : 상수들의 set

2. f ∈ Q(n) 일때 f는 linear라고 한다.

3. f ∈Q(n^2) 일때 f는 quadratic이라고한다.

4. f ∈Q(n^3) 일때 f는 cubic이라고 한다.

- Abstract data type

  ADT(Abstract Data Type): 컴퓨터 과학에서 자료들과 자료들에 대한 연산들을 명기한 것.

                                    자료구조의 추상화

     : Structure(data structure declarations), Function(operation definitions)을 구성

  1. Tree : 계층적 구조를 가짐, 노드간 부모-자식 관계

     관련용어

1) Root : tree에서 부모가 없는 최상위 노드

2) Degree : 한 노드에서 자식노드의 수

3) External node(leaf) : 자식이 존재하지 않는 node로 leaf를 뜻한다.

4) Internal node: 1개 이상의 자식 node가 존재하는 node

5) Ancestors of a node: 한 노드의 부모를 포함한 조상 노드들

6) Descendant of a node: 한 노드의 바로 연결된 자식과 그 밑 자식들

    Proper Ancestor, Proper Descendant : 자기자신 불포함

7) Subtree : tree의 한 노드와 그 후손들로 구성된 하나의 트리 (트리안에 트리)

8) Depth : 한 노드의 조상의 수

9) Level : 같은 depth를 가지는 node 수

10) Height : 노드들의 depth중 가장 큰 depth로, tree의 높이다.

   2. Binary Tree : 트리 중 모든 노드가 최대 두개의 자식 노드를 가진 트리

   3. Stack : LIFO원칙에 따라 자료를 삽입 또는 삭제하는 자료구조

top() : 맨 마지막으로 삽입된 원소를 가리킴

n개의 원소를 가진다면 공간복잡도 O(n), push()와 pop()연산의 시간복잡도 O(1)

   4. Queue :  FIFO원칙에 따라 자료를 삽입 또는 삭제하는 자료구조

front() : 맨 처음으로 삽입된 원소를 가리킴

enqueue()와 dequeue()연산의 시간복잡도 O(1)

   5. Priority queue : 우선순위에 의해 데이터가 정렬되기 때문에 queue에 삽입되는 요소의 순서가 중요하지 않으며 데이터 속성에 따라 제거가 가능하다.

구현 방식 3가지

   6. Heap :  최대값, 최소값을 찾아내는 연산을 쉽게 하기 위해 고안된 자료구조

   Heap-Order와 (Almost) Complete Binary Tree조건을 만족하는 binary tree이다.

* heap-order: 모든 노드에 대해 각 노드의 키값이 자식 노드의 키값보다 작지 않거나(max heap, 이때 root의 키값이 가장 크다) 자식노드의 키값보다 크지않은(min heap, root의 키값이 가장 작다)을 만족해야 한다.

   7. Dictionary : Entry가 (key, value)쌍으로 이루어진 자료구조로 데이터 검색 시 유용하다. map과 달리 중복된 Key 허용

  dictionary 구현 방법

① List-based: 단순히 linked list로 key와 value를 entry로 한 list. Put에는 O(1)이 걸리고 find, erase에는 O(n)이 걸린다.

② Hash Table: Array-based. 같은 key값이 존재하므로 value들의 저장 방법에 차이를 둬야함.

③Search Table: key값을 정렬한 search table을 만드는 방법. (STL의 방법)

 이 방법에서 binary search를 사용하여 key값을 검색하도록 함.