Tree2 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. 이전 1 다음