ch 7. Heap Sort & NP Theory

• 계산 복잡도 (Çomputational Complexity)
• 알고리즘의 분석
• 특정 알고리즘의 효율 efficiency측정
• 시간 복잡도 time complexity
• 공간 복잡도 space/memory complexity
• 문제의 분석
• 일반적으로 계산복잡도 분석이라 하는 경우,
• 어떤 문제에 대해 그 문제를 풀수 있는 모든 알고리즘의 하한(lower bound)을 결정

• 힙정렬 (Heapsort) 알고리즘
• 완전 이진 트리 ( complete binary tree)
• 트리 내부의 모든 노드에는 2개의 자식 노드가 존재하는 이진 트리
• 모든 잎의 depth는 동일
• 실질적 완전 이진트리
• depth(깊이) d-1까지는 완전이진트리이고,
• d의 노드는 왼쪽 끝애서부터 채워진 이진 트리
• 힙의 성질 (heap property) : 어떤 마디에 저장된 값은 그 마디의 자식 마디에 저장된 값보다 크거나 같다.
• 힙(heap) : 힙의 성질을 만족하는 실질적 완전 이진 트리

• 힙트리 예
• 초기
  
  
  
• (ex) makeheap
  
  
  
• (ex) shiftdown
  
  
  
  
• 힙정렬 알고리즘

void siftdown(heap& H){          node parent, largerchild;         parent = root of H;         largerchild = parent’s child containing larger key;         while(key at parent is smaller than key at largerchild){                 exchange key at parent and key at largerchild;                 parent = largerchild;                 largerchild = parent’s child containing larger key;         } } keytype root(heap& H){         keytype keyout;         keyout = key at the root;         move the key at the bottom node to the root;         delete the bottom node;         siftdown(H);         return keyout; } void removekeys(int n, heap H, keytype S[]){ index i;         for(i=n; i>=1; i--)                 S[i] = root(H); } void makeheap(int n, heap& H){         index i;         heap Hsub;         for(i=d-1; i>=0; i--)                 for(all subtree Hsub whose roots have depth i)                         siftdown(Hsub); } void heapsort(int n, heap H, keytype S[]){         makeheap(n,H);         removekeys(n,H,S); }

• 완전 이진트리를 배열로 표현
  
  
  

struct heap {         keytype S[1..n];         int heapsize; }; void siftdown(heap& H, index i) {         index parent, largerchild;         keytype siftkey;         bool spotfound;         siftkey = H.S[i];         parent = i;           spotfound = false;         while (2*parent <= H.heapsize &&! Spotfound){                  if(2*parent < H.heapsize && H.S[2*parent] < H.S.[2*parent+1])                         largerchild =2*parent+1;                 else                          largerchild=2*parent;                  if(siftkey<H.S[largechild]){                         H.S[parent]=H.S[largerchild];                         parent=largerchild;                 } // end of if                 else spotfound=true;          } // end while         H.S[parent]=siftkey;  } // end of shiftdown keytype root(heap& H) {          keytype keyout;         keyout=H.S[i];         H.S[I]=H.S[heapsize];         H.heapsize=H.heapsize-1;         Siftdown(H,1);         return keyout;  } // end of root void removekeys(int n, heap& H, keytype S[]) {          index i;         for (i=n;i>=1;i--)                 S[i]=root(H); } // end removekeys void makeheap(int n, heap& H){         inde i;         H.heapsize=n;         for (i=lowerbound(n/2);i>=1;i--)siftdown(H,i); } // end of makeheap

• 정렬 알고리즘의 분류
• 선택하여 정렬하는 부류
• 순서대로 항목을 선택하여 적절한곳에 위치
• 교환, 삽입, 선택, 힙정렬
• 공간복잡도 1. 모두 제자리 정렬 알고리즘
• 자리를 바꾸어 정렬하는 분류
• 버블소트, 머지소트, 퀵소트
• 버블을 제외하고는 모두 제자리 정렬이 아님

• 외부정렬
• 정렬할 대상의 자료가 너무 커서 주기억장치에 모두 저장할 수 없는 경우, 전체자료를 보조기억 장치에 두고 일정한 단위(run) 만큼 읽어서 정렬 한 다음 합병하는 과정을 반복함에 의하여 정렬 하는 방법
  
  
• Polyphase merge sorting
• Run reconstruction and distribution: arrange the keys in runs on two or more tapes or files
• Polyphage merge : repeatedly merge the runs until there is only one.

• NP Theory 요약
• Polynomial-time Algorithm (다차 시간 알고리즘)
• - 입력의 크기가 n일 때, 최악의 경우 수행시간이 W(n) < (p(n)) “다루기 힘들다(intractable)”
• -  다차시간으로 시간복잡도가 표시되는 알고리즘으로 찾을 수 없는 문제
• Optimization problem (최적화 문제) : 최적의 해를 찾아야 함
• Decision problem (결정 문제)
• - 대답이 “예” 또는 “아니오”로 이루어지는 문제  이론을 전개하고 이해하기 쉬움
• P는 다차시간 알고리즘으로 풀 수 있는 결정 문제들의 집합
• Polynomial-time nondeterministic algorithm(다차시간 비결정적 algo.) 
• - 검증단계가 다차시간에 수행되는 비결정적 알고리즘
• - Guessing state (추측단계)는 비결정적임
• set NP (Nondeterministic Polynomial)
• - 다차시간비결정적알고리즘에의해서풀수있는모든결정문제의 집합  다루기 힘들다고 증명되지 않았고,다차시간 알고리즘도 찾지 못한 문제
• - NP-Complete, NP-easy, NP-Hard, NP-equivalent