자료구조 이론 요약
1단원 : Arrays & Linked Lists (순서가 있다)
⁃ Array
- index (0 ~ n-1)로 접근 : 특정 index값 접근시 유용
- fixed size
- insertion : 1. 크기를 비교하며 들어갈 위치 i 구하기, 2. i+1부터 뒤에값들을 뒤로 미루기, 3. i에 넣기
- insertion - time : O(n)
- deletion : 1. i번째 내용 remove, 2. i+1번째부터 앞으로 이동(i+1 ~ n-1)
- deletion - time : O(n)
⁃ Dynamic Array : 사이즈 능동 (Vector, ArrayList, List)
⁃ Singly Linked List : 단방향 링크드 리스트
- Node (T element, Node* next)
- LinkedList(Node* head, Node* tail)
- addFront(element) : 1. 새로운 노드 v 생성, 2. element 입력, 3. next : head 설정, 4. head : v 설정
- addFront - time : O(1) : 4번 수행 (constant time)
- removeFront() : 1. 삭제될 head : temp로 저장, 2. head : head->next로 이동, 3. temp 삭제
- removeFront - time : O(1) : 3번 수행 (constant time)
- addTail(element)
- 1. 새로운 노드 v 생성, 2. element 입력, 3. next : null 설정
- 4. tail->next위치에 v설정, 5. tail : v 설정
- addTail - time : O(1) : 4번 수행 (constant time)
- removeTail() : 1. 삭제될 tail : temp로 저장, 2. tail : n-2번째의 노드로 설정, 3. tail->next : null 설정, 4. temp 삭제
- removeTail - time : O(n) : O(1) + O(n) : i=0부터 n-2번째까지 반복되기 때문 + O(1) + O(1)
⁃ Doubly Linked List : 양방향 링크드 리스트
- Node(T element, Node* next, Node* prev)
- DLinkedList(Node* header, Node* tailer)
- add(Node* p, element) : Node p의 위치에 새로운노드를 생성하여 넣는다 (p -> p의 next로 이동)
- 1. 새로운 노드 v 생성, 2. element 입력, 3. p의 이전노드를 u로 저장한다. : Node*u = p->prev
- 4. u의 next를 v로 수정한다 (->) : u->next = v
- 5. v의 이전노드를 u로 저장한다 (<-) : v->prev = u
- 6. p의 이전노드를 새로운 v로 수정한다 (<-) : p->prev = v
- 7. v의 다음노드를 p로 저장한다 (->) : v->next = p
- add - time : O(1) : 7번 수행 (constant time)
- add(header->next, element) : addFront(element) 동일
- add(tailer,element) : addTail(element) 동일
- remove(Node* p) : Node p를 삭제한다 (p->next : p로 이동)
- 1. p의 이전노드를 u로 저장한다 : Node* u = p->prev
- 2. p의 다음노드를 w로 저장한다 : Node* w = p->next
- 3. u의 다음노드를 w로 수정한다 : u->next = w
- 4. w의 이전노드를 u로 수정한다 : w->prev = u
- 5. p를 삭제한다 : delete p
- remove - time : O(1) : 5번 수행 (constant time)
- remove(header->next) : removeFront() 동일
- remove(tailer->prev) : removeTail() 동일
- remove time : O(1) : 5번 수행 (constant time)
⁃ ADT : Abstract Data Types : “What”, class 선언부분 (how는 선언되지 않은 부분)
⁃ List ADT
- size()
- empty()
- begin()
- end()
- next()
- insertFront(e)
- insertBack(e)
- removeFront()
- removeBack()
- insert(p,e)
- remove(p)
⁃ Iterators : 집합체로부터 정보를 얻어오는 도구
- for(p = c.begin(); p != c.end(); p = c.next())
- begin() : index로는 0
- end() : index로는 n (정보가 저장안되어있다, p.end()->data 접근 불가)
- next() : i+1
⁃ LinkedList
- begin() : head
- end() : null
- next() : p.next()
⁃ DoubleLinkedList
- begin() : header.next()
- end() : tailer
- next() : p.next()
2단원 : Stacks
⁃ Stack ADT
- LIFO (Last in first out)
- size()
- empty()
- top() : Exception 고려
- push(object)
- pop() : Exception 고려
⁃ Use Stack
- 1. history
- 2. undo
- 3. chain
⁃ Stack (based Array)
- Stack(E* S, max, t)
- E* S : array
- max : capacity
- t : index of top
- size() : return t+1
- pop() : if(!empty()) : t=t-1, return S[t+1]
- push(E& e) : if(t+1 >= max) : throw stackFull / else : t=t+1, S[t] = e
- empty() : return (t == -1)
- “(“, “{“, “[“, “]”, “}”, “)” 사용시 stack이 쓰인다
- Parentheses Matching Algorithm : 닫고 여는 stack 알고리즘
for(i=0 to n-1)
if(X[i] : open -> S.push(X[i])
else
if(S.empty() -> return false
if(S.pop() : not match -> return false
if(S.empty()) : return true / else return false
⁃ Stack (based LinkedList)
- Stack(Linked* L, header, tailer)
- peak() : return L->head->element
- pop() : temp=L->head->element / L->removeFront() / return temp
- push() : L->addFront(element)
- peak - time : O(1)
- pop - time : O(1)
- push - Time : O(1)
- Stack - Space : O(n)
⁃ Algorithm for Evaluating expressions : 숫자,연산자 조합으로 입력된 값 계산
⁃ valStack, opStack 두가지 스택이 존재 (숫자, 연산자 각각 스택으로 입력)
while(char z)
if(z : number) : valStack.push(z) // 만약 문자가 숫자인 경우 숫자스택에 입력
else
repeatOps(z)
//문자인 경우 현재문자와 문자스택의 상단의 우선순위를 비교하여
//스택상단의 우선순위가 큰경우 (* > +) 계산을 하여 숫자스택에 넣는다
opStack.push(z) //연산을 더이상 할수없는경우 연산자 스택에 문자를 입력한다
repeatOps($) //마지막 문자입력을 넣는다
return valStack.top() //숫자스택의 상단에 연산된결과가 저장되어있기에 반환한다
⁃ repeatOps(newOp)1*2+ : “*” >= “+” : 2+
while(valStack.size() > 1 && prec(newOp) <= prec(opStack.top()) : doOp()
// 숫자 스택에 2개이상 있으며 현재 스택상단의 연산자 우선순위가 더 높은경우 연산진행
⁃ doOp() : 1+2 -> 3
x = valStack.pop() //최상단 숫자 x로 저장
y = valStack.pop() // 두번째 상단 숫자 y로 저장
op = opStack.pop() //최상단 연산자 저장
valStack.push(y op x) //연산 후 숫자스택에 넣는다
3단원 : Analysis of algorithms : 알고리즘 분석
⁃ Pseudocode : 알고리즘을 설명하는 방식
- More structured than English
- Less detailed than a program
⁃ Basic operations 기본 연산들 : 한정된 시간 소요
- 1. memory access
- 2. arithemetic operations (+,-,*,/,%)
- 3. assignment (=)
- 4. return, allocation (반환, 할당)
- 5. comperation (<,<=,>,>=,!=) (비교연산)
⁃ Counting primitive operations : 알고리즘의 최대 회수를 알 수 있다
⁃ Estimating running time : T(n) : n개의 자료에 대한 시간 : worst case time을 기준으로 측정한다
⁃ which one is faster? (8n-2) : (5n) -> worst case로 예측한거기 때문에 모른다 -> Big-Oh Notation 사용
⁃ Big-Oh Notation
- f(n) = O(g(n)), f(n) <= c*g(n) 즉 g(n)이 f(n)보다 작으며 g(n)을 상수배 했을때 f(n)보다 큰 경우이다
- upperbound가 적용된다 (크지않다! : 상한선)
⁃ Common functions
- O(1) : Constant
- O(log n) : Logarithmic
- O(n) : Linear
- O(n log n) : N-Log-N
- O(n^2) : Quadratic
- O(n^3) : Cubic
- O(2^n) : Exponential
⁃ Relatives of Big-Oh
⁃ Big-Omega : 하한선
- f(n) >= c*g(n) : 성공확률, 즉 최대치를 의미한다
⁃ Big-Theta : 같은값들
- c1*g(n) <= f(n) <= c2*g(n)
⁃ Big-Oh : 작거나 같다 (상한선 아래)
⁃ Big-Omega : 크거나 같다 (하한선 위)
⁃ Big Theta : asymptotically 하게 같다
4단원 : Queue : FIFO (First in First out)
⁃ Queue ADT : “what”
- enqueue(object)
- dequeue() : Exception 고려
- size()
- front() : Exception 고려
- empty()
⁃ Applications of Queue
- waiting list
- multiprogramming
- level order
⁃ Queue (based Array) : 단점으로 크기제한이 있다
- Queue(n, f, r, MAX) : number of items, index of front, index of rear, max of size
- f : 맨앞 index
- r : 실제 마지막값 + 1위치
- size() : return n
- empty() : return (n==0)
- enqueue(val)
if(size() == n-1) : return QueueFull : n개칸에 n-1개의 자료가 있고 마지막에 r이 위치하고 있는경우 : QueueFull
else Q[r] = val, r++; r %= MAX (배열끝이 다 찬경우 배열앞으로 이동)
- dequeue()
if(empty()) : return QueueEmpty
else f++; n—; f %= MAX; return Q[f-1]
⁃ 두개의 queue를 사용하여 stack을 만들자
- 1. push(O(1)), pop(O(n))
- push(val) : Q1.enqueue(val)
- pop()
- 1. while(Q1.size() > 1) : Q2.enqueue(Q1.dequeue))
- 2. 그러면 Q1에 하나의 값만 남게된다 -> swap(Q1,Q2) (Q2 : 1개만)
- 3. return Q2.dequeue()
- 2. push(O(n)), pop(O(1))
- push(val)
- 1. Q2.enqueue(val)
- 2. while(Q1.size() >= 1) : Q2.enqueue(Q1.dequeue())
- 3. 그러면 Q1에 아무값도 없게된다 -> swap(Q1,Q2) (Q2 : 0개)
- pop() : return Q1.dequeue()
⁃ 두개의 stack을 사용하여 queue를 만들자
- enqueue(val) : S1.push(val)
- dequeue()
- 1. if(S2.empty()) : while(!S1.empty()) : S2.push(S1.pop()) // S2가 비어있지 않은경우는 그대로 패스한다
- 2. 그러면 S1에 아무값도 없게된다. -> return S2.pop()
5단원 : Recursion 재귀
⁃ Factorial : 펙토리얼 함수 (재귀)
⁃ factorial(n)
if(n == 0) : return 1
else return n * factorial(n-1)
⁃ Time : O(n)
⁃ Space : O(n)
⁃ 반목문으로 제작시 Time : O(n), Space : O(1)로 제작이 가능하다
⁃ Recursive Method의 구성요소
- BaseCase : 탈출조건
- RecursiveCalls : 재귀를 부르는 내용
⁃ Linear Recursion : 선형 재귀 : 재귀를 한번만 부른다
⁃ Recur Once : if(case 1: return A) else return B : A또는 B중 한번만 반환되기 때문에 선형재귀가 맞다
⁃ LinearSum(A,n) : 배열 A의 각 요소 n개의 합 : Sum(A,n-1) + A[n-1] 즉, 사이즈를 줄인 배열과 함께 끝자료를 더한다
if(n==1) : return A[0];
else return LinearSum(A,n-1) + A[n-1]
⁃ ReverseArray(A, i, j) : 배열 순서 바꾸기 (A : 배열, i : 시작 인덱스, j : 끝점 인덱스)
if(i<j) : swap(A[i],A[j]), ReverseArray(A,i++, j—) : 시작과 끝내용을 바꾼다음 시작++, 끝— 하여 다시 시작한다
⁃ BinarySum(A, i, n) : 바이너리트리 A의 시작인덱스 i부터 n개의 값을 더한다
if(n==1) : return A[i] //개수가 1개이며 i위치이기 때문에 A[i]값을 반환한다 (리프노드일때 반환한다)
else return BinarySum(A, i, n/2) + BinarySum(A,i + n/2, n/2) //개수가 2개이상인 경우 반으로 쪼개어 i부터 n/2개, i+n/2부터 n/2개씩 더한다
- 높이 k : 총 데이터 수 n / 2^k승 = 1이 되는 k번째 -> n = 2^k승 -> k = log2 n이 된다!
- B(n) = 2 * B(n/2) + C = 4 * B(n/4) + 3C -> 2^k * B(1) + a*C = 2^k * a + b -> O(2^k) = O(n)
- BinarySum - Time : O(n) = O(2^k), k = log2 n
- BinarySum - Space : O(log n) : 높이 k (n = 2^k)
⁃ Fibonacci(k) : 1부터 k개의 숫자를 피보나치로 더한값을 반환한다, k위치값 = k-1위치값 + k-2위치값
- F(0) = 0, F(1) = 1 로 시작값을 저장한다음 시작한다
if(k <= 1) : return k
else return Fibonacci(k-1) + Fibonacci(k-2)
- 시간(n) >= 2*시간(n-2) >= 4*시간(n-4) >= 8*시간(n-6) -> 2^k * 시간(n-2k) = 2^k시간 : n = 2k -> k = n/2
- Fibonacci - Time : O(2^n)
- Fibonacci - Space : O(n)
⁃ LinearFibonacci(k) : (i+j,j) : (k-2+k-1,k-1) 식으로 이전, 두번이전의 값을 한번에 반환하여 linear 방식으로 변환
if(k==1) : return (k,0)
else (i, j) = LinearFibonacci(k-1), return (i+j,i) : i=현재 k번째 위치의 값, j=k-1번째 값
6단원 : Tree : parent-child 관계
- Organization charts
- File Systems
- Programming environments
- Root : parent가 없는 최상단 노드
- Internal node : 자식이 하나이상 있는 노드
- External node : 자식이 없는 노드 : leaf 노드
- Ancestors of node : 자신을 포함한 위에있는 노드들
- Depth of a node : 최상단 노드 = 0을 기준으로 얼마나 내려와있는지, 부모노드의 개수
- Time : O(depth of node) : 자신의 depth 만큼 시간이 걸린다
- Space : O(depth of node) : 자신의 depth 만큼 공간을 사용한다
- Height of a node : 리프노드 = 0을 기준으로 얼마나 올라가는지, 자식들의 Height의 Max + 1
- Time : O(자식노드의수)
- Space : O(Height of node): 자신의 height 만큼 공간을 사용한다
- Height of a tree : Maximum of depth (최고 레벨)
- Descendant of a node : 자신을 포함한 아래방향의 자식들 (subTree의 모든요소들)
- Subtree : Descendant of a node로 이뤄진 트리 (자신이 Root 이고 자식들이 요소인 새로운 트리)
⁃ Tree ADT : “What” : class 틀 (tree의 어떤 기능들이 있니)
- size()
- empty()
- root()
- nodes()
- parent()
- children()
- isRoot()
- isExternal()
⁃ Tree (based LinkedList)
- Node(E element, Node* parent, List<Node*> Children) : 각 노드는 값, 부모노드, 자식노드들을 가진다
- Tree(Node* root, List<Node*> Nodes) : 트리는 root노드와 노느들의 리스트를 가진다, 각 리스트에 노드가 있으며 노드의 부모, 노드의 자식을을 접근하는 식으로 구성된다
⁃ Tree Traversal : 노드를 방문하는 순서
⁃ DFS (Depth first search)
- 1. Preorder : 노드에 방문했을시 수행 후, 자식들의 노드를 방문한다
preorder(v)
visit(v) //print(v.data)
for each child w of v
preorder(w)
- Time : O(n)
- Space : O(Height of v)
- 2. Postorder(v) : 노드에 방문하여 자식들의 노드를 방문 후 수행한다
postorder(v)
for each child w of v
postorder(w)
visit(v) // print(v.data)
- Time : O(n)
- Space : O(Height of v)
- Preorder : 목차에 사용, html의 헤더에 사용
- Postorder : html의 헤더닫기에 사용
⁃ Binary Tree : 자식이 최대 두개밖에 없는 트리
⁃ Proper Binary Tree : 모든 자식이 두개인 트리, 자식노드의 순서를 부여할 수 있다 (왼쪽, 오른쪽)
⁃ Full Binary Tree : Proper Binary Tree와 같은개념
⁃ Complete Binary Tree : 노드가 왼쪽 -> 오른쪽 순으로 채움을 만족하는 트리
⁃ Proper Binary Tree = Complete Binaty Tree : 항상 만족한다
⁃ Complete Binaty Tree != Proper Binaty Tree : 왼쪽 노드만 있는 경우도 있기 때문에 항상 같지는 않다
⁃ Binary Search Tree : 위와 전혀다른 개념, 착각하지 말자
⁃ Proper Binary Tree : Left, Right 노드 존재
- m : non-leaf 노드의 개수
- l : leaf 노드의 개수
- 1. l = m+1 (leaf 노드의 수는 non-leaf 노드의 수 + 1개이다)
- 2. m = l-1 (non-leaf 노드의 수는 leaf 노드의 수 - 1개이다) : n개의 축구팀의 토너먼트 : n-1 경기수
⁃ Properties of Binary Tree : 한쪽만 노드가 있을 수 있다!
- n : number of nodes
- m : number of internal nodes
- l : number of leaf nodes
- h : height of node
※ h <-> n의 관계 : Tree of V의 space complexity = V의 height 이다
- 1. n의 관계 (n <-> h 관계를 사용한다)
- 자식노드가 하나씩 밖에 없는경우 (일렬) : 높이 h = 개수 n-1개이다
-> h+1 <= n을 만족한다
- Proper binary인 경우 : n = 2^0 + … + 2^h -> 2^(h+1)-1 = n
-> n <= 2^(h+1) -1을 만족한다
따라서 “ h+1 <= n <= 2^(h+1) -1 “ 만족한다
- 2. h의 관계 (h <-> h 관계를 사용한다)
- 자식노드가 하나씩 밖에 없는경우 (일렬) : 높이 h = 개수 n-1개이다
-> h <= n-1을 만족한다
- Proper binary인 경우 : 2^(h+1) -1 = n -> 2^(h+1) = n+1 -> h+1 = log 2 (n+1)
-> h >= log2 (n+1) -1을 만족한다
따라서 “ log2 (n+1) -1 <= h <= n-1 “ 만족한다
- 3. m의 관계 (m = n - l) 관계를 사용한다)
- 자식노드가 하나씩 밖에 없는경우 (일렬) : 리프노드가 1 이므로 m = n-l = n-1이 된다
-> m >= n-1 = h을 만족한다
- Proper Binary인 경우 : internal node : m = 2^0 + … + 2^(h-1)이다 -> m = 2^(h)-1
-> m <= 2^h -1을 만족한다
따라서 “ n-1 <= m <= 2^h -1 “ 만족한다
- 4. l의 관계
- 노드가 단 하나인 경우 : m=1, l=0인 경우이다
-> l >= 0 or 1 을 만족한다
- Proper binary인 경우 : h번째의 노드의 수 = 2^h이므로
-> l <= 2^h 를 만족한다
따라서 “ 0 or 1 <= l <= 2^h “ 만족한다
⁃ Properties of Proper Binary Trees : 항상 자식노드가 두개씩 존재한다
- n : number of nodes
- m : number of internal nodes
- l : number of leaf nodes
- h : height of node
※ l = m+1 (리프노드의 개수 = 리프가 아닌 노드의 개수 + 1)
- 1. h의 관계
- 한쪽 방향으로 길게 뻗은경우 : 한쪽방향만 보면 h = m = n-1이 된다 (h가 최대인 경우)
-> h <= m 을 만족한다
- Proper Binary인 경우 : 리프노드의 개수 l = 2^h가 된다 -> h = log 2 (l) (h가 최소인 경우)
-> h >= log2 (l) 을 만족한다
따라서 “ log2 (l) <= h <= m “ 만족한다
- 2. n의 관계 : 두가지 식을 사용하여 구할 수 있다 (n값 비교하기)
- m + 1 = l
- m + l = n
-> n = (l-1) + l = 2l - 1
따라서 “ n = 2l -1 “ 만족한다
- 3. h의 관계 : 두가지 식, h의 관계를 사용하여 구할 수 있다(l값 비교하기)
- l = m+1 = n-m -> 2m = n-1
-> m = (n-1)/2 만족한다
- h <= m을 만족한다 (h가 최대일 때)
따라서 “ h <= (n-1)/2 “ 만족한다
- 4. l의 관계
- Proper Binary의 경우 : 리프노드의 개수 l = 2^h를 만족한다 (l이 최대일 때)
따라서 “ l <= 2^h “ 만족한다
- 5. h의 관계
- n = 2^(h+1) -1 -> 2^(h+1) = n+1 -> h+1 = log2 (n+1)
-> h = log2 (n+1) - 1 을 만족한다 (h가 최소일때)
따라서 “ h >= log2 (n+1) - 1 “ 만족한다
⁃ Binary Tree ADT
- left()
- right()
⁃ Inorder Traversal : Binary Tree의 경우 일반 Tree와 다르게 left, right 가 있기에 middle의 개념이 가능하다
⁃ inorder(v)
if(!v.isExternal()) : inorder(v.left()) //리프 노드가 아닌경우 left로 이동한다
visit(v) //left가 다 끝난 후 middle 지점에서 수행한다
if(!v.isExternal()) : inorder(v.right()) //마지막으로 right로 이동한다
⁃ Inorder 순서 활용
- ( (2 ✕ (a - 1) ) + ( 3 ✕ b) ) : 왼쪽값, 중간 오페레이터, 오른쪽값 -> 반환
if(v.isExternal()) : return v.element()
else x = evalExpr(v.left()), y = eval(Expr(v.right()), op = operator stored at v
return x op y
- Time : O(n)
- Space : O(h)
⁃ Euler Tour Traversal : DFS 방식으로 노드를 거쳐가는 루트, 항상 각 노드를 세번씩 지나치게 된다 (pre, in, post)
⁃ EulerTour(v)
visit(v) // pre
EulerTour(v.left())
visit(v) //in
EulerTour(v.right())
visit(v) //post
⁃ Tree Traversal : 노드를 방문하는 순서
⁃ BFS (Breadth first search) : 너비 우선 탐색
⁃ Level order Traversal : BFS 방식으로 탐색 : Queue를 사용하여 구현한다
⁃ levelOrder(v)
Q.enqueue(v) //Q에 v를 넣는다
while (!Q.isEmpty()) : u = Q.dequeue(), visit(u) , for each child w of u : Q.enqueue(w)
// 일단 Q에 v를 넣고 시작한다, 그리고 Q가 비어있지 않는경우 dequeue를 하며 동시에 자식 노드들을 enqueue 한다
⁃ Time : O(n)
⁃ Space : O(L)
⁃ #L : 각 level 에 있는 노드의 수들 중 Max값
⁃ Array-Based Representation of Binary Trees : 트리를 array에 저장하는 형식
⁃ 부모노드 : F(v) = 1일때
⁃ left 노드 : 2*F(v) = 2
⁃ right 노드 : 2*F(v)+1 = 3
⁃ left 노드의 left 노드 : 2*(2*F(v)) = 4
⁃ left 노드의 right 노드 : 2*(2*F(v))+1 = 5
⁃ right 노드의 left 노드 : 2*(2*F(v)+1) = 6
⁃ right 노드의 right 노드 : 2*(2*F(v)+1) +1 = 7
⁃ 따라서 F(v)의 최대수 : 2^n -1까지이다
⁃ Space : O(2^n) (빈공간이 많이 사용된다) -> List로 구현하는 경우 Space : O(n)이 소요된다
⁃ 따라서 Complete Tree 형태일 때 사용된다
7단원 : Priority Queue (PQ)
⁃ Heap을 많이 사용한다 (Heap != PQ)
⁃ Priority Queue ADT
⁃ min : key와 value 가 존재하는데, key가 작은값일수록 우선순위가 놓은 구조이다
- insert()
- removeMin() : 우선순위가 높은 값을 삭제한다
- min() : 우선순위가 높은 값을 반환한다
⁃ Total Order Relations : key 간에 순위 (level 따라, left, right 따라 등등)
- Reflective property : x <= x
- Antisymmetric property : x<=y && y<=x -> x = y
- Transitive property : x <= y && y <= z -> x <= z
- 세가지 모두 만족 : Partial order 만족
⁃ Priority Queue Sorting : 정렬
⁃ PQ-sort(list S,C) : Selection Sort : removeMin()시에 정렬된다
while(!S.empty()) : e = S.removeFront(), P.insert(e,null) //S가 빌때까지 P에 넣는다
while(!P.empty()) : e = P.removeMin(), S.addTail(e) // P에서 min값을 하나씩 찾으며 S에 넣는다
- insertTime : O(1) (한번 실행시 기준)
- removeTime : O(n) (한번 실행시 기준)
* assending(오름차순), dessending(내림차순)
⁃ 1. Selection sort : removeMin() 시에 최소값을 찾으며 정렬된다
- insert Time : O(1) * n번 = O(n)
- removeMin Time : (n-1) + (n-2) + … + 1 = O(n^2)
- Time : O(n^2)
- Space : O(n)
⁃ 2. Insertion sort : insert() 시에 정렬되며 추가된다
- insert Time : 1 + 2 + … + (n-1) = O(n^2)
- removeMin Time : O(1) * n번 = O(n)
- Time : O(n^2)
- Space : O(n)
⁃ In-place Insertion sort : 넣을 시에 기존값들과 하나씩 비교하며 swap
⁃ swap을 통해 구현이 가능하다 : 2번째 : 1번째와 비교 -> 3번째 : 1,2번째와 비교 -> 4번째 : 1,2,3번째와 비교 …
⁃ Time : O(n^2) : 1 + 2 + … + (n-1)
⁃ Space : O(1) : auxiliary space
⁃
⁃ In-place Selection sort : 넣은 후 정렬이 안된 범위내에서 최소값을 찾아 그 위치와 swap 하며 정렬을 넓혀간다
⁃ 정렬이 안된 범위내에서 가장 작은값을 찾는다 -> 맨앞위치의 값과 swap 한다
⁃ 그러면 앞에서부터 정렬된값으로 하나씩 생긴다
⁃ Time : O(n^2) : n개중 최소값 -> n-1중 최소값 -> … -> 1개중 최소값
⁃ Space : O(1) : auxiliary space
* Heap : Time(log n), Space(log n)
8단원 : Heap : Binary Tree의 일종 (complete binary tree : 왼,오 순서대로 : height가 최소)
⁃ Partial order : level별로 순서만 의미부여, level 내의 순서를 고려하지 않는다
⁃ parent의 key값 <= child의 key값 순서가 지켜져야 한다 (parent <= child)
⁃ Height of a Heap : 높이
- 개수 : 2^h <= n <= 2^(h+1) -1
- 높이 : O(log n) : h <= log2 n
⁃ Heap implementation (based Array) : Complete 형태이므로 좋은 형태이다
⁃ f(v) -> left : 2*f(v), right : 2*f(v)+1
⁃ Node(f, left, right, parent) : f : 값, 부모, left 자식, right 자식을 지닌다
⁃ left() : return A[f*2]
⁃ right() : return A[f*2+1]
⁃ parent() : return A[f/2]
⁃ upHeap() : 특정노드 <-> 부모노드와 swap 하며 노드가 위로 올라가는 메소드
⁃ downHeap() : 특정노드 <-> 자식노드(중 값이 작은노드)와 swap 하며 노드가 내려가는 메소드
⁃ Insertion into Heap (Heapify)
1. array의 마지막 위치에 insert 된다
2. 부모와 key 값을 비교하며 upHeap()을 한다
3. 최종적으로 알맞은 위치에 들어가게 된다
Time : O(log n) : insert : O(1) + upHeap : O(log n)
Space : O(1)
⁃ UpHeap(Node v) : 노드를 위로 올려 Heap으로 만든다
while(v != root() && key(v) < key(v.parent())) : swap(v.parent(),v)
v = v.parent()
- Time : O(log n) : 높이 (level의 수)
⁃ Removal Min from heap (Heapify)
1. first 노드를 last 노드와 swap 한다
2. last 노드를 delete 한다
3. DownHeap 하며 Heap을 만든다
Time : O(log n) : swap : O(1) + downHeap : O(log n)
Space : O(1)
⁃ DownHeap(Node v) : 노드를 아래로 내려 Heap으로 만든다
while(v != leaf() && key(v) > u = min{key(left(v)), key(right(v))} ) : swap(v,u)
v = u
- Time : O(log n) : 높이(level의 수)
⁃ PQ sort(used Heap)
- Space : O(n)
- Time : O(n log n) : removeMin Time(O(log n)) * n개
⁃ In-place Heap sort (in-place insertion sort와 비슷)
⁃ 1. 먼저 Max 값을 찾은 다음 UpHeap을 한다 : O(n)
⁃ 2. max 노드와 last 노드를 swap 한다
⁃ 3. 그렇게 max노드가 마지막으로 유지된다
⁃ 4. 동일 방법으로 남은 노드중 max 값을 찾아 동일하게 마지막노드와 swap 한다
⁃ Time : O(n log n) : logn + log(n-1) + … + log 1
⁃ Space : O(1)
⁃ Heap Construction by insertion
⁃ 노드가 추가될때마다 minHeap을 맞춘다
⁃ 새로 추가된 노드는 마지막 위치에 들어가며 바로 upHeap을 비교하게 된다
⁃ Time : O(n log n) : O(1) + O(2) + … + O(log n)
⁃ Bottom up Heap construction
⁃ 정렬된 양옆의 트리를 통해 상단의 노드를 아래로 내리는 식으로 정렬한다
⁃ 매 노드마다 DownHeap을 비교
⁃ level (h-1) : 2^(h-1) ✕ O(1)번
⁃ level (h-i) : 2^(h-i) ✕ O(i)번
⁃ level (h-h) : 2^(h-h) ✕ O(h)번
⁃ 따라서 합산 S = 시그마 2^(h-i) ✕ O(i) (i=1~h) 여기서 상수 2^(h)를 빼면
⁃ S = 1/2 + 2/4 + 3/8 + …
⁃ S/2 = 1/4 + 2/8 + …
⁃ S-S/2 = S/2 = 1/2 + 1/4 + 1/8 + …
⁃ 따라서 합산 S = 2로 수렴한다
⁃ 따라서 최종 O(2^h) = O(2^(log2 n)) = O(n)이 된다
⁃ Time : O(n)
'자료구조' 카테고리의 다른 글
| Stack (based Array) 실습 (0) | 2020.10.26 |
|---|---|
| Singly Linked List 실습문제 (0) | 2020.10.26 |
| Array 실습문제 (0) | 2020.10.26 |
| List 실습 (0) | 2020.10.26 |
| Array 실습 (0) | 2020.10.26 |