알고리즘7 Heapsort Heap 구조((left) Complete binary tree)와 순서(부모 key값 >= 자식 key값)를 만족하는 binary tree HeapSort insert() -> upHeap() : 리프에서 루트까지 swap. O(logn) removeMax() -> deleteMax() : 끝값을 루트에 덮어씌운 뒤 리프까지 swap. findMax() : 루트노드의 키값 리턴. O(1) heapSort(E, n): 배열 E로부터 힙 H를 만든 뒤 max값을 빼서 E에 순서대로 넣는 과정을 n번 반복한다. deleteMax(H): 가장 마지막 노드 값을 가장 첫번째 값에 덮어씌움-> 마지막 노드 삭제-> fixHeap fixHeap(H, K): downHeap. 왼쪽 자식과 오른쪽 자식 중 더 큰 것과.. 2021. 4. 8. Abstract Data Type (ADT) Abstract Data Type Structures/Funtions C++이나 Java의 Class와 같은 것 알고리즘을 디자인하고 정확도를 개선 Tree Root: 부모노드가 없는 노드 Degree: 자식노드의 수 External node(leaf): 자식노드가 없는 노드 Internal node: 자식노드가 있는 노드 Ancestor of a node x: 루트까지의 simple path의 노드들 (x 포함, proper ancestor: 자기 자신 제외) Descendant: ancestor의 반대 개념. 자신 아래에 있는 모든 노드들. Subtree rooted at a node x: x의 descendant들을 모은 트리. 루트는 x Depth: 0부터 시작하여 자식으로 내려갈수록 1씩 증가 .. 2021. 3. 26. Array search알고리즘의 Optimality n개 원소를 갖는 배열 E와 정수 K가 주어진다. K=E[index]인 인덱스를 찾고, 없으면 -1을 리턴하라. 1. A: unsorted Array일 때, 순차적 탐색 W(n) = n (Worst case) A(n) = q[(n+1)/2]+(1-q)n (Average case. q:탐색에 성공할 확률) unsorted일 때 F(n)=n 이므로 알고리즘 A는 optimal 2. B: 오름차순 정렬된 배열일 때, 순차적 탐색 W(n) = n A(n) = q[(n+1)/2]+(1-q)n 배열이 정렬되었다는 정보를 이용하지 않음. optimal X 3. C: 오름차순 정렬된 배열일 때, 순차적 탐색하다가 K보다 큰 원소를 만나면 -1 리턴 (찾는 원소가 없다) W(n) = n+1 => n Asucc(n) = .. 2021. 3. 24. Analysis of the Algorithm 3 Worst-Case Complexity Average Complexity - Pr(I): input I가 발생할 확률 - t(I)는 알고리즘 분석으로 결정할 수 있지만, Pr(I)는 분석적으로 계산 불가능 Optimality - 알고리즘 복잡도 2021. 3. 24. Analysis of the Algorithm 2 Proof (증명법 1. Counterexample - 반례 2. Contraposition - 대우 3. Contradiction - 모순, 귀류: 결론을 부정하고 모순임을 보임 4. Mathematical Induction - 수학적 귀납법 : i가 초기값에 대해 참, i가 k에 대해 참이라고 가정할 때 k+1일 때도 참임을 증명 Analyzing Algorithms and Problems - Correctness 증명하기 1. if the precondition(input data) are satisfied, ex) 정수정렬문제면 인풋이 정수인지 2. then the postcondition(output data) will be true, 3. whe the algorithm terminates A.. 2021. 3. 24. Analysis of the Algorithm 1 Analysis of the Algorithm 실험적 분석: 구현 필수, 실험하지 않은 인풋에 대한 결과를 알 수 없음, 비교할 때 환경이 동일해야 함 이론적 분석: 구현 전 파악, 수행시간을 n함수로 정의, 모든 인풋에 대해 고려, 환경과 상관없는 평가 가능 Worst-Case Analysis - W(n): 최대 basic operation 수를 n으로 표현한 함수. - Analysis Tool 1. Mathematics - Series : the sum of a sequence 2. Logic A => B ㄱA v B ㄱ(A ^ B) ㄱA v ㄱB 드모르간의 법칙 ㄱ(A v B) ㄱA ^ ㄱ 2021. 3. 24. 이전 1 2 다음
